In probability theory and statistics, a Pólya urn model (also known as a Pólya urn scheme or simply as Pólya's urn), named after George Pólya, is a family of urn models that can be used to interpret many commonly used statistical models.
The model represents objects of interest (such as atoms, people, cars, etc.) as colored balls in an urn. In the basic Pólya urn model, the experimenter puts x white and y black balls into an urn. At each step, one ball is drawn uniformly at random from the urn, and its color observed; it is then returned in the urn, and an additional ball of the same color is added to the urn.
If by random chance, more black balls are drawn than white balls in the initial few draws, it would make it more likely for more black balls to be drawn later, and the same for the white balls. Thus, the urn has a self-reinforcing property ("the rich get richer"). It is the opposite of sampling without replacement, where every time a particular value is observed, it is less likely to be observed again, whereas in a Pólya urn model, an observed value is more likely to be observed again. In a Pólya urn model, successive acts of measurement over time have less and less effect on future measurements, whereas in sampling without replacement, the opposite is true: After a certain number of measurements of a particular value, that value will never be seen again.
It is also different from sampling with replacement, where the ball is returned to the urn but without adding new balls. In this case, there is neither self-reinforcing nor anti-self-reinforcing.
Questions of interest are the evolution of the urn population and the sequence of colors of the balls drawn out.
After draws, the probability that the urn contains white balls and black balls (for ) is
where the overbar denotes rising factorial. This can be proved by drawing the Pascal's triangle of all possible configurations.
In particular, starting with one white and one black ball (i.e., ) the probability to have any number of white balls in the urn after draws is the same, .
More generally, if the urn starts with balls of color , with , then after draws, the probability that the urn contains balls of color iswhere we use the multinomial coefficient.
Conditional on the urn ending up with balls of color after draws, there are different trajectories that could have led to such an end-state. The conditional probability of each trajectory is the same: .
Polya's Urn is a quintessential example of an exchangeable process.
Suppose we have an urn containing white balls and black balls. We proceed to draw balls at random from the urn. On the -th draw, we define a random variable, , by if the ball is black and otherwise. We then return the ball to the urn, with an additional ball of the same colour. For a given , if we have that for many , then it is more likely that , because more black balls have been added to the urn. Therefore, these variables are not independent of each other.
The sequence does, however, exhibit the weaker property of exchangeability. Recall that a (finite or infinite) sequence of random variables is called exchangeable if its joint distribution is invariant under permutations of indices.
To show exchangeability of the sequence , assume that balls are picked from the urn, and out of these balls, balls are black and are white. On the first draw the number of balls in the urn is ; on the second draw it is and so on. On the -th draw, the number of balls will be . The probability that we draw all black balls first, and then all white balls is given by
Now we must show that if the order of black and white balls is permuted, there is no change to the probability. As in the expression above, even after permuting the draws, the th denominator will always be , since this is the number of balls in the urn at that round.
If we see -th black ball in round , the probability will be equal to , i.e. the numerator will be equal to . With the same argument, we can calculate the probability for white balls. Therefore, for any sequence in which occurs times and occurs times (i.e. a sequence with black balls and white balls drawn in some order) the final probability will be equal to the following expression, where we take advantage of commutativity of multiplication in the numerator:This probability is not related to the order of seeing black and white balls and only depends on the total number of white balls and the total number of black balls.
According to the De Finetti's theorem, there must be a unique prior distribution such that the joint distribution of observing the sequence is a Bayesian mixture of the Bernoulli probabilities. It can be shown that this prior distribution is a beta distribution with parameters . In De Finetti's theorem, if we replace with , then we get the previous equation: In this equation .