Asymptotic normality in the generalized Polya-Eggenberger urn model, with an application to computer data structures.

*(English)*Zbl 0568.60010In 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.

##### MSC:

60C05 | Combinatorial probability |

60F05 | Central limit and other weak theorems |

62E20 | Asymptotic distribution theory in statistics |

68R99 | Discrete mathematics in relation to computer science |

PDF
BibTeX
XML
Cite

\textit{A. Bagchi} and \textit{A. K. Pal}, SIAM J. Algebraic Discrete Methods 6, 394--405 (1985; Zbl 0568.60010)

Full Text:
DOI

##### References:

[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.