zbMATH — the first resource for mathematics

Asymptotic normality in the generalized Polya-Eggenberger urn model, with an application to computer data structures. (English) Zbl 0568.60010
In the generalized Polya-Eggenberger urn model, an urn initially contains a given number of white and black balls. A ball is selected at random from the urn, and the number of white and black balls added to (or taken away from) the urn depends on the color of the ball selected. Let \(w_ n\) be the random variable giving the number of white balls in the urn after n draws. A sufficient condition is derived for the asymptotic normality, as \(n\to \infty\), of the standardized random variable corresponding to \(w_ n\). This result is then used for estimating the computer memory requirements of the 2-3 tree, a well-known computer data structure for storage organization.

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
62E20 Asymptotic distribution theory in statistics
68R99 Discrete mathematics in relation to computer science
Full Text: DOI
[1] Aho, AlfredV.; Hopcroft, JohnE.; Ullman, JeffreyD., The design and analysis of computer algorithms, (1975) · Zbl 0326.68005
[2] Athreya, KrishnaB.; Karlin, Samuel, Embedding of urn schemes into continuous time Markov branching processes and related limit theorems, Ann. Math. Statist., 39, 1801, (1968) · Zbl 0185.46103
[3] Athreya, KrishnaB.; Ney, PeterE., Branching processes, (1972) · Zbl 0259.60002
[4] Brown, MarkR., A partial analysis of random height-balanced trees, SIAM J. Comput., 8, 33, (1979) · Zbl 0402.05024
[5] Chow, YuanShih; Teicher, Henry, Probability theory, (1978) · Zbl 0399.60001
[6] Fisz, Marek, Probability theory and mathematical statistics, (1963) · Zbl 0123.34504
[7] Freedman, DavidA., Bernard Friedman’s urn, Ann. Math. Statist, 36, 956, (1965) · Zbl 0138.12003
[8] Friedman, Bernard, A simple urn model, Comm. Pure Appl. Math., 2, 59, (1949) · Zbl 0033.07101
[9] Hall, P.; Heyde, C. C., Martingale limit theory and its application, (1980) · Zbl 0462.60045
[10] Holst, Lars, A unified approach to limit theorems for urn models, J. Appl. Probab., 16, 154, (1979) · Zbl 0396.60027
[11] Johnson, NormanL.; Kotz, Samuel, Urn models and their application, (1977) · Zbl 0352.60001
[12] Jordan, C., Calculus of Finite Differences, (1960)
[13] Knuth, D. E., The Art of Computer Programming, Vol. 3, Sorting and Searching, (1975) · Zbl 0302.68010
[14] Milne-Thomson, L. M., The Calculus of Finite Differences, (1951) · JFM 59.1111.01
[15] Yao, A. C.-C., On random \(2-3\) trees, Acta Informat., 9, 159, (197778) · Zbl 0369.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.