I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can achieve nearly 0 probability of error when using $O( \log \log M)$ bits, where $M$ is the total number of messages. Instead, deterministic encoding would require us to use at least $O(\log M)$ bits instead.
Can anyone give an intuitive explanation of why stochastic encoding is so effective? One possible idea which opposes the result is that the stochastic code would result in many possible codes for a single message which should make it more difficult for the decoder as the codes are now more 'tightly packed', i.e., there are many more valid codes possible for the same number of bits transmitted.