Two Birthday Problem Modifications: Non-Uniform Case

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

Abstract


Background. The scheme of random allocation of particles in cells is studied both in probability theory and mathematical statistics. In probability theory usual study is concerning limit theorems, in mathematical statistics – construction statistical criteria’s. Birthday problem is one of main questions in this theory.

Objective. Two modifications of the birthday problem are considered in the paper. One was formulated in Fermi statistic scheme, another – in non-uniform and independent random allocation scheme. In both cases the objective was to solve a 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.

Conclusion. For both modifications main asymptotic values coincide, as in the formula for probability calculation, as in the formula for the group size. But second terms from their asymptotic series are already different.

 


Keywords


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

References


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

T. Nunnikhoven, “A birthday problem solution for nonuniform birth frequencies”, The American Statistician, vol. 46, pp. 601–606, 1992.

F. Mathis, “A generalized birthday problem”, SIAM Rev., vol. 33, pp. 265–270, 1991.

G.A. Heuer, “Estimation of a certain probability problem”, Am. Math. Monthly, vol. 66, pp. 704–706, 1959.

P. Yendovytskij, “Two birthday problem modifications”, Naukovi Visti NTUU “KPI”, vol. 4, pp. 47–55, 2015 (in Ukrainian).

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

V. Ivanov et al., “Some limit theorems in the non-uniform allocation scheme”, Teorija Verojatnostej i ee Primenenija, vol. 3, pp. 643–650, 1978 (in Russian).

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

P. Yendovytskij, “Exact asymptotic approximation of the group size in generalization of birthday paradox”, Naukovi Visti NTUU “KPI”, vol. 4, pp. 55–60, 2010 (in Ukrainian).


GOST Style Citations


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

  2. Nunnikhoven T. A birthday problem solution for nonuniform birth frequencies // The American Statistician. – 1992. – 46. – P. 601–606.

  3. Mathis F. A generalized birthday problem // SIAM Rev. – 1991. – 33, № 2. – P. 265–270.

  4. Heuer G.A. Estimation of a certain probability problem // Am. Math. Monthly. – 1959. – 66. – P. 704–706.

  5. Єндовицький П.О. Дві модифікації задачі про дні народження // Наукові вісті НТУУ “КПІ”. – 2015. – № 4. – С. 47–55.

  6. DasGupta A. The matching, birthday and strong birthday problem: a contemporary review // J. Statist. Planning Inference. – 2005. – 130. – P. 377–389.

  7. Иванов В.А., Теребулин С.Ю. Некоторые предельные теоремы в неравновероятной схеме размещения частиц комплектами // Теория вероятностей и ее применения. – 1978. – 3. – С. 643–650.

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

  9. Єндовицький П.О. Точна асимптотична оцінка розміру групи в узагальненні парадоксу днів народжень // Наукові вісті НТУУ “КПІ”. – 2010. – № 4. – С. 55–60.




DOI: https://doi.org/10.20535/1810-0546.2016.4.76267

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 NTUU KPI