Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures

Abstract

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.