In 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. Similarly 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
n
(x+n1)
(y+n2)
\binom{n}{n | ||||||||||||||
|
More generally, if the urn starts with
ai
i
i=1,2,...,k
n
(ai+ni)
i
Conditional on the urn ending up with
(ai+ni)
i
n
\binom{n}{n1, … ,nk}
\binom{n}{n1, … ,
-1 | |
n | |
k} |
One of the reasons for interest in this particular rather elaborate urn model (i.e. with duplication and then replacement of each ball drawn) is that it provides an example in which the count (initially x black and y white) of balls in the urn is not concealed, which is able to approximate the correct updating of subjective probabilities appropriate to a different case in which the original urn content is concealed while ordinary sampling with replacement is conducted (without the Pólya ball-duplication). Because of the simple "sampling with replacement" scheme in this second case, the urn content is now static, but this greater simplicity is compensated for by the assumption that the urn content is now unknown to an observer. A Bayesian analysis of the observer's uncertainty about the urn's initial content can be made, using a particular choice of (conjugate) prior distribution. Specifically, suppose that an observer knows that the urn contains only identical balls, each coloured either black or white, but they do not know the absolute number of balls present, nor the proportion that are of each colour. Suppose that they hold prior beliefs about these unknowns: for them the probability distribution of the urn content is well approximated by some prior distribution for the total number of balls in the urn, and a beta prior distribution with parameters (x,y) for the initial proportion of these which are black, this proportion being (for them) considered approximately independent of the total number. Then the process of outcomes of a succession of draws from the urn (with replacement but without the duplication) has approximately the same probability law as does the above Pólya scheme in which the actual urn content was not hidden from them. The approximation error here relates to the fact that an urn containing a known finite number m of balls of course cannot have an exactly beta-distributed unknown proportion of black balls, since the domain of possible values for that proportion are confined to being multiples of
1/m
This basic Pólya urn model has been generalized in many ways.
n
n
k
w+nw
w+nw | |
w+b+n |
n=1,2,3,...
\alpha
Polya's Urn is a quintessential example of an exchangeable process.
Suppose we have an urn containing
\gamma
\alpha
i
Xi
Xi=1
Xi=0
i
Xj=1
j<i
Xi=1
The sequence
X1,X2,X3,...
To show exchangeability of the sequence
X1,X2,X3,...
n
n
k
n-k
\gamma+\alpha
\gamma+\alpha+1
i
\gamma+\alpha+i-1
k
n-k
P\left(X1=1,...,Xk=1,Xk+1=0,...,Xn=0\right)=
\alpha | |
\gamma+\alpha |
x
\alpha+1 | |
\gamma+\alpha+1 |
x … x
\alpha+k-1 | |
\gamma+\alpha+k-1 |
x
\gamma | |
\gamma+\alpha+k |
x
\gamma+1 | |
\gamma+\alpha+k+1 |
x … x
\gamma+n-k-1 | |
\gamma+\alpha+n-1 |
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
i
\gamma+\alpha+i-1
If we see
j
t
Xt=1
\alpha+j-1 | |
\gamma+\alpha+t-1 |
\alpha+j-1
x1,x2,x3,...
1
k
0
n-k
k
n-k
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
\beta\left( ⋅ ;\alpha,\gamma\right)
\pi( ⋅ )
\beta\left( ⋅ ;\alpha,\gamma\right)
p(X_1=x_1,X_2=x_2,...,X_n=x_n) &= \int \theta^\left(\right)\times \left(1-\theta\right)^\left(n - \right)\,\beta\left(\theta; \alpha,\, \gamma\right)d\left(\theta\right)\\&= \int \theta^\left(\right)\times \left(1-\theta\right)^\left(n - \right)\,\dfrac\theta^(1-\theta)^d\left(\theta\right)\\&= \int \theta^\left(\right)\times \left(1-\theta\right)^\left(n + \gamma -1 -\right)\,\dfracd\left(\theta\right)\\&= \int \theta^\left(\right)\times \left(1-\theta\right)^\left(n -k - 1+ \gamma\right)\,\dfracd\left(\theta\right)\\&= \dfrac \int \theta^\left(\right)\times \left(1-\theta\right)^\left(n-k+\gamma- 1\right)\,d\left(\theta\right)\\&= \dfrac \dfrac\\ &= \dfrac
\end
In this equation
k=
n | |
\sum | |
i=1 |
xi