Two Birthday Problem Modifications

Павло Олександрович Єндовицький


Background. Scheme of particle allocation in cells is studied in probability theory as well as in mathematical statistics. In probability theory it goes about limit theorems, in mathematical statistics – of construction statistical criteria’s. Birthday problem is one of main questions in this theory.

Objective. In the paper two modifications of the birthday problem are considered. One was formulated in Fermi statistic scheme, another – in uniform and independent random allocation scheme. In both cases the objective was to solve birthday problem.

Methods. Standard asymptotical methods were used. At first we needed to prove one limit theorem and to estimate rapidity of convergence in it. Using these results numerical calculation of probabilities from birthday problem was made. Also formulas for the group size from birthday problem were obtained.

Results. As a result numerical estimates for birthday problem probability and group size were obtained.

Conclusions. For both modifications asymptotic main value coincides both in the formula for probability calculation and the formula for the group size. But second terms from their asymptotic series are already different.


Birthday problem; Birthday paradox; Random allocations; Fermi statistic; Uval attack


G. Szekely, Paradoxes in Probability Theory and Mathematical Statistics.Moscow,USSR: Mir, 1990, 240 p. (in Russian).

A.P. Alferov et al., Handbook of Cryptography.Moscow,Russia: Gelios, 2001, 480 p. (in Russian).

V.F. Colchin et al., Random Allocations.Moscow,USSR: Nauka, 1976, 224 p. (in Russian).

A. DasGupta, “The matching, birthday and strong birthday problem: a contemporary review”, J. Stat. Plan. Inference, vol. 130, pp. 377–389, 2005.

GOST Style Citations

  1. Секей Г. Парадоксы в теории вероятностей и мат. статистике. – М.: Мир, 1990. – 240 с.

  2. Основы криптографии / А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. – М.: Гелиос АРВ, 2001. – 480 с.

  3. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. – М.: Наука, 1976. – 224 с.

  4. DasGupta A. The matching, birthday and strong birthday problem: a contemporary review // J. Stat. Plan. Inference. – 2005. – 130. – P. 377–389.

Copyright (c) 2017 NTUU KPI