  As an attempt to bridge the gap between the probabilistic world of classical
information theory and the combinatorial world of zero-error information
theory, this paper studies the performance of randomly generated codebooks over
discrete memoryless channels under a zero-error list-decoding constraint. This
study allows the application of tools from one area to the other. Furthermore,
it leads to an information-theoretic formulation of the birthday problem, which
is concerned with the probability that in a given population, a fixed number of
people have the same birthday. Due to the lack of a closed-form expression for
this probability when the distribution of birthdays is not uniform, the
resulting expression is not simple to analyze; in the information-theoretic
formulation, however, the asymptotic behavior of this probability can be
characterized exactly for all distributions.
