Polya's Urn is a quintessential example of
an exchangeable process. Suppose we have an urn containing \gamma white balls and \alpha black balls. We proceed to draw balls at random from the urn. On the i-th draw, we define a
random variable, X_i, by X_i = 1 if the ball is black and X_i = 0 otherwise. We then return the ball to the urn, with an additional ball of the same colour. For a given i, if we have that X_j = 1 for many j , then it is more likely that X_i =1, because more black balls have been added to the urn. Therefore, these variables are not
independent of each other. The sequence X_1, X_2, X_3, \dots 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 X_1, X_2, X_3, \dots, assume that n balls are picked from the urn, and out of these n balls, k balls are black and n-k are white. On the first draw the number of balls in the urn is \gamma+\alpha; on the second draw it is \gamma+\alpha+1 and so on. On the i-th draw, the number of balls will be \gamma+\alpha+i-1. The probability that we draw all k black balls first, and then all n-k white balls is given by \mathbb P \left( X_1 = 1, \dots, X_k =1, X_{k+1} =0, \dots, X_n = 0 \right) = \frac{\alpha}{\gamma+\alpha}\times \frac{\alpha+1}{\gamma+\alpha+1}\times \cdots \times \frac{\alpha+k-1}{\gamma+\alpha+k-1} \times \frac{\gamma}{\gamma+\alpha+k}\times \frac{\gamma+1}{\gamma+\alpha+k+1}\times \cdots \times \frac{\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 ith denominator will always be \gamma+\alpha+i-1, since this is the number of balls in the urn at that round. If we see j-th black ball in round t, the probability X_t = 1 will be equal to \frac{\alpha+j-1}{\gamma+\alpha+t-1}, i.e. the numerator will be equal to \alpha+j-1. With the same argument, we can calculate the probability for white balls. Therefore, for any sequence x_1, x_2, x_3, \dots in which 1 occurs k times and 0 occurs n-k times (i.e. a sequence with k black balls and n-k 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:\begin{align} \mathbb P(X_1=x_1,X_2=x_2,...,X_n=x_n) &= \frac{\prod_{i=1}^k \left(\alpha+i-1\right)\times \prod_{i=1}^{n-k} \left(\gamma+i-1\right)}{\prod_{i=1}^{n}\left(\gamma+\alpha+i-1\right)} \\ &= \frac{\left(\alpha+k-1\right)!\times \left(\gamma+n-k-1\right)!\times \left(\alpha+\gamma-1\right)!}{\left(\alpha-1\right)!\times \left(\gamma-1\right)!\left(\alpha+\gamma+n-1\right)!} \end{align}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(\cdot; \,\alpha,\, \gamma\right). In De Finetti's theorem, if we replace \pi(\cdot) with \beta\left(\cdot; \,\alpha,\, \gamma\right), then we get the previous equation:\begin{align} p(X_1=x_1,X_2=x_2,...,X_n=x_n) &= \int \theta^\left({\sum_{i=1}^n x_i}\right)\times \left(1-\theta\right)^\left(n - {\sum_{i=1}^n x_i}\right)\,\beta\left(\theta; \alpha,\, \gamma\right)d\left(\theta\right)\\ &= \int \theta^\left({\sum_{i=1}^n x_i}\right)\times \left(1-\theta\right)^\left(n - {\sum_{i=1}^n x_i}\right)\,\dfrac{(\alpha+\gamma-1)!}{(\alpha-1)!\,(\gamma-1)!}\theta^{\alpha-1}(1-\theta)^{\gamma-1}d\left(\theta\right)\\ &= \int \theta^\left({\alpha -1 +\sum_{i=1}^n x_i}\right)\times \left(1-\theta\right)^\left(n + \gamma -1 -{\sum_{i=1}^n x_i}\right)\,\dfrac{(\alpha+\gamma-1)!}{(\alpha-1)!\,(\gamma-1)!}d\left(\theta\right)\\ &= \int \theta^\left({\alpha + k - 1}\right)\times \left(1-\theta\right)^\left(n -k - 1+ \gamma\right)\,\dfrac{(\alpha+\gamma-1)!}{(\alpha-1)!\,(\gamma-1)!}d\left(\theta\right)\\ &= \dfrac{(\alpha+\gamma-1)!}{(\alpha-1)!\,(\gamma-1)!} \int \theta^\left({\alpha + k - 1}\right)\times \left(1-\theta\right)^\left(n-k+\gamma- 1\right)\,d\left(\theta\right)\\ &= \dfrac{(\alpha+\gamma-1)!}{(\alpha-1)!\,(\gamma-1)!} \dfrac{\Gamma(\gamma+n-k)\Gamma(\alpha+k)}{\Gamma(\alpha+\gamma+n)}\\ &= \dfrac{\left(\alpha+k-1\right)!\times \left(\gamma+n-k-1\right)!\times \left(\alpha+\gamma-1\right)!}{\left(\alpha-1\right)!\times \left(\gamma-1\right)!\left(\alpha+\gamma+n-1\right)!} \end{align} In this equation k = \sum_{i=1}^n x_i. ==See also==