Anonymity means that the identity of the user performing a certain action is main- tained secret. The protocols for ensuring anonymity often use random mechanisms which can be described probabilistically. The user, on the other hand, may be selected either nondeterministically or probabilistically. We investigate various no- tions of anonymity, at different levels of strength, for both the cases of probabilistic and nondeterministic users.