This interactive post was written with the Idyll markup language.
Markup sources for this blog post can be found here.
The Pólya urn model is a statistical experiment in which we study the distribution of two populations of distinctly colored balls in an urn. In its simplest form, the problem can be stated as follows:
Figure 1: Simulation of a Pólya urn with initial conditions a = 1 and b = 2.
This process is a good example of a model where small imbalances are magnified over time: In fact, the more balls of one color are drawn, the more this color is likely to be drawn. As such, it has been used to model for instance propagation of epidemics in a population (Hayhoe et al.) or the correlated dynamics between novelty events (Tria et al, 2014). In the following, we study the dynamics of the model from a probabilistic point of view and its asymptotical properties, in particular with respect to the initial ratio of populations.
Basic dynamics of the model
Composition of the urn at step n
Let us first express the probability of having picked blue objects after steps of the experiment. Denoting by the number of blue balls at step , and by the sampling event at step , taking value 1 if a blue ball is sampled and 0 otherwise:
We can expand the inner term by using the probability chain rule. Moreover, the probability of drawing a ball of a certain color given the composition of the urn is simply the ratio of correspondingly colored balls in the urn, which evolves with each sampling. Therefore, the conditional probability of drawing a blue object at step can be written as:
From this expression, we can see that the probability does not depend on the time step but rather on how many blue balls have been sampled until now, as captured by the quantity . This also means that the model is Markovian, as the probability at step only depends on the urn’s composition at step .
Consequently, for any sequence of draws , we can arrange the order in which the balls have been drawn without affecting the probability of the next draw. This is sometimes called the exchangeability property. More formally, it means that Equation (1) is equivalent to:
where is a shortcut notation for from . The same analysis holds for the conditional probability of drawing an orange ball. Bringing everything together, we can thus finally write
Probability of the next draw
Following the previous result, we can now compute the probability of picking a blue ball at step , independently of the state of the urn at time :
To simplify the expression of , we can use Pascal’s triangle formula on the numerator (while isolating the terms for and ) and observe that:
By extending the relation, one can infer and finally prove by induction over , that . Plugging this expression in Equation (3), we finally get:
In other words, the overall probability of the urn composition after only depends on the initial color distribution in the urn. In particular, for the case where and we have and . In other words, all urn configurations are equiprobable when starting from a balanced urn.
Since various urn compositions can be reached from the same initial configuration ( , ), one can also wonder what the urn composition looks like asymptotically, when the number of repeats goes to .
Let us introduce , the ratio of the two colored ball populations at step . Using the previous results, we can easily see that the expected value of is equal to the initial ratio, independently of the time step:
This can also be observed in simulations. Here, blue lines ( --- ) represent the observed value of for each time step 100 for 70 different runs with the same initial conditions and . Red circles ( ● ) mark the average of these values across runs, for each time step, hence serve as an approximation of .
Figure 2: Study of the average asymptotic distribution for a Pólya urn experiment.
Link to the Dirichlet-multinomial distribution
Going further, we can also study the convergence in distribution of the random variable . First we observe that the probability distribution of is directly linked to the one of , that we expressed earlier.
Where the Gamma and Beta functions are defined as and respectively.
Note that, up to a simple rearrangement of terms in Equation (4), we observe that follows a Dirichlet-multinomal distribution with parameters . And in fact, this distribution is also known as the multivariate Pólya distribution and can be generalized to urns with more than two color populations.
To prove a convergence in distribution, we want to look at the limit of the repartition function of , defined as , when the time step . Using the previous simplified expression, we have:
Thus is the only term that depends on . Its expression is clearly linked, and similar to, a binomial expansion: More specifically, if we define the random variable with a binomial distribution of parameters and , then we have exactly that .
We can then directly apply the Demoivre-Laplace theorem, which derives from the Central Limit theorem, to which yields that, for large ,
where is the repartition function of the standard Gaussian distribution, , and, as such, is continuous and bounded. As a result, we have that:
By splitting the integral from Equation (5) at point , we conclude that
The right-side term is exactly the repartition function of a Beta distribution at point . Thus, the proportion of blue balls in the urn, , converges in distribution to the Beta distribution with parameters b and a when grows.
Figure 3: Histograms of observed values of for 10000 runs with different initial conditions (a , b), compared to the density function of the distribution (represented as --- ).
Generalized Pólya urn
We won’t study such models here, but it is possible to extend the Pólya urn experiment to more flexible frameworks: Generalized Pólya urns follow the same workflow as the one we have been working with until now, but with different replacement values. More specifically, the experiment is described as follows:
Such a model is often represented by its initial conditions (a , b), and its replacement matrix, .
It is also possible to generalize the urn to an arbitrary number of colors, leading to a replacement matrix. For instance, in the standard Pólya setting, we have and
- “A Pólya Contagion Model for Networks”, M. Hayhoe et al, 2017
- “A survey of random processes with reinforcement”, R. Pemantle, 2017
- “On generalized Pólya urn models”, M. Chen and M. Kuba, 2011
- “Pólya urn models: Lecture Notes”, N. Pouyanne, 2004
- “Rate of convergence of Pólya’s urn to the Beta distribution”, J. Drinane, 2008
- ″The dynamics of correlated novelties”, F. Tria et al, 2014
- “Urnes aléatoires, populations en équilibre et séries génératrices”, B. Mallein, 2010