Refining the asymptotic approximation of the group size in the birthday paradox
- PDF / 97,125 Bytes
- 5 Pages / 595.276 x 793.701 pts Page_size
- 109 Downloads / 159 Views
REFINING THE ASYMPTOTIC APPROXIMATION OF THE GROUP SIZE IN THE BIRTHDAY PARADOX UDC 519.2
P. A. Endovitskii
Abstract. Two theorems on the asymptotic behavior of the group size in the birthday paradox are proved. Theorem 1 gives asymptotically unimprovable estimates for the group size if particles are arranged in cells uniformly and independently. Theorem 2 gives asymptotically unimprovable estimates for the group size if two equal sets of particles are arranged in cells uniformly and independently. The results may be applied in cryptography to estimate the complexity of finding collisions of hash functions. Keywords: random arrangement, birthday paradox, asymptotic inequalities, Stirling formula for gamma functions, collision method for hash functions. The birthday paradox is as follows [1, 2]. Let there be a group of n people (n £ 365) and let each person from the group be born on one of the 365 days with equal probabilities. Then the probability that there exist at least two persons in the group whose birthdays coincide is P ( n ) = 1-
( 365) n 365
n
= 1-
365 × 364 × K × ( 365 - n + 1) 365n
.
The size of the group where at least two persons have the same birthday with probability p = 1 is 366, and it is much 1 smaller for p < 1: P( 23) = 0. 507 ... , P( 57) = 0. 990 ... , etc. (i.e., in a group of 23 people, there is more than probability that 2 some pair of them will have the same birthday). The paradox consists in the apparent contradiction to the small group size for given p Î ( 0; 1) . For more details see [2]. The estimates of the probabilities and group size in the birthday problem have important applications in authentification, constructing hash functions, coding, cryptoanalysis, in solving systems of equations over finite algebraic structures. 1. Let us formulate the group size problem in birthday paradox in the general case (in terms of the arrangement of particles in cells). Let the numbers m Î N and p Î ( 0; 1) be given, m is the number of cells, m = 365 in the paradox. Let also Pm ( n ) be the probability that in the arrangement of n particles in m cells, at least two particles will appear in one cell (each particle is assumed to be placed independently of others and equiprobably in m cells): Pm ( n ) = 1-
( m) n m
n
= 1-
m × ( m - 1) × K × ( m - n + 1) mn
º 1- Qm ( n ), n = 0, m + 1,
(1)
where Qm ( n ) = 1- Pm ( n ) is the probability that all the particles will appear in different cells. Then P ( n ) increases with respect to n for fixed m, P ( 0) = P (1) = 0 , P ( m + 1) = 1 (to simplify the notation, we will write P ( n ) instead of Pm ( n )). Let us define a natural number n = n( m ) Î [1; m + 1] dependent on m and p from the following condition: P ( n - 1) < p £ P ( n ) ,
(2)
National Technical University “Kyiv Polytechnic Institute,” Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 185–188, May–June 2010. Original article submitted November 17, 2009. 516
1060-0396/10/4603-0516
©
2010 Springer Science+Business Media, Inc.
i.e.,
Data Loading...
