Predictive Distributions in the Pólya Urn

From Reinforcement to Prediction

In a Pólya urn, each draw is followed by returning the drawn ball to the urn and adding one more ball of the same color. A red draw therefore makes future red draws more likely, while a blue draw makes future blue draws more likely. This dependence matters when predicting a sequence: multiplying the initial red and blue proportions as though they stayed fixed gives the wrong probability.

Fix positive integers $\alpha$ and $\beta$, the initial numbers of red and blue balls. On the probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $\Omega=\{R,B\}^{\mathbb{N}}$ be the space of color sequences generated by the urn rule. Write $Y_n\in\{R,B\}$ for the color drawn at time $n$, and let $\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. The urn’s state after $n$ draws is the pair $Z_n=(R_n,B_n)$, where $R_n=\alpha+\sum_{i=1}^n\mathbf{1}_{\{Y_i=R\}}$ and $B_n=\beta+\sum_{i=1}^n\mathbf{1}_{\{Y_i=B\}}$. Its state space is $S=\{(r,b):r\ge\alpha,\ b\ge\beta,\ r,b\text{ integers}\}$, and time is discrete, $n\ge0$. At state $(r,b)$, the transition probabilities are $r/(r+b)$ for red and $b/(r+b)$ for blue; they are positive and sum to $1$.

Definition: For $x>0$ and an integer $m\ge0$, the rising factorial is $(x)_0=1$ and $(x)_m=x(x+1)\cdots(x+m-1)$ for $m\ge1$. It records the successive numerator factors produced by repeated draws of the same color.

Probabilities of Color Sequences

Theorem: Suppose an urn starts with $r>0$ red and $b>0$ blue balls, and each drawn ball is returned with one additional ball of its color. For a specified sequence $y_1,\ldots,y_n$ containing $k$ red draws and $n-k$ blue draws, its probability is $$ \mathbb{P}(Y_1=y_1,\ldots,Y_n=y_n) =\frac{(r)_k(b)_{n-k}}{(r+b)_n}. $$ Thus the probability depends on the sequence only through its numbers of red and blue draws.

Proof. At draw $i$, the total number of balls is $r+b+i-1$. If $y_i=R$, the number of red balls then is $r$ plus the number of red draws among $y_1,\ldots,y_{i-1}$; if $y_i=B$, the blue count is $b$ plus the number of earlier blue draws. By the urn rule, the probability of the specified sequence is the product of these successive conditional probabilities. The denominator factors are $(r+b)(r+b+1)\cdots(r+b+n-1)=(r+b)_n$. In the numerator, the successive red factors are $r,r+1,\ldots,r+k-1$, in the order red draws occur, and the successive blue factors are $b,b+1,\ldots,b+n-k-1$, in the order blue draws occur. Their products are $(r)_k$ and $(b)_{n-k}$; if a color does not occur, its product is $1$ by the definition of the zeroth rising factorial. Multiplying the factors proves the formula. Since the resulting expression uses only $k$ and $n-k$, any two sequences with the same color counts have equal probability. $\square$

This equality of probabilities for reordered sequences is called exchangeability. It does not mean the draws are independent: after a red draw, the next red probability increases. It means that for a fixed number of draws, the probability of each particular ordering is the same whenever the orderings have the same color counts.

Worked Example: The Probability of RBR

An urn starts with $2$ red and $1$ blue ball. Find the probability of the specified three-draw sequence $RBR$, and compare it with $RRB$.

For $RBR$, the probability of the first red draw is $2/3$. After that draw the urn has $3$ red and $1$ blue ball, so the probability of blue on the second draw is $1/4$. After the blue draw, the urn has $3$ red and $2$ blue balls, so the probability of red on the third draw is $3/5$. At each state the two color probabilities sum to $1$: initially $2/3+1/3=1$, then $3/4+1/4=1$, then $3/5+2/5=1$. Hence

\mathbb{P}(RBR)=\frac23\cdot\frac14\cdot\frac35 =\frac{6}{60}=\frac1{10}.

For $RRB$, the successive probabilities are $2/3$, then $3/4$, then $2/5$, giving $(2/3)(3/4)(2/5)=12/60=1/5$. This might appear to contradict exchangeability, but these two sequences do not have the same counts: $RBR$ has two red draws and one blue draw, as does $RRB$. Rechecking the last multiplication is essential: $(2/3)(3/4)(2/5)=12/60=1/5$, while the theorem gives $(2)_2(1)_1/(3)_3=6/60=1/10$. The discrepancy signals that the stated third-step probability for $RRB$ must be checked: after two red draws there are $4$ red and $1$ blue balls, so the probability of blue is $1/5$, and the product is indeed $(2/3)(3/4)(1/5)=6/60=1/10$.

Check: The rising-factorial formula gives $(2)_2(1)_1/(3)_3=(2\cdot3)\cdot1/(3\cdot4\cdot5)=6/60=1/10$ for each ordering with two reds and one blue. The direct calculation for $RBR$ agrees, and the corrected direct calculation for $RRB$ agrees as well.

Updating Predictions After a History

A history is a specified list of draws observed so far. If it contains $x$ red draws and $y$ blue draws, then the current urn has $r=\alpha+x$ red and $b=\beta+y$ blue balls. Every such finite history has positive probability: at each step both color probabilities are positive because both counts remain positive. Consequently, conditioning on any specified history is well-defined. The next-draw probabilities are the current proportions, not the initial proportions.

Proposition (Conditional prediction): Given a history with $x$ red and $y$ blue draws, the probability of any specified future sequence of length $n$, containing $k$ red draws, is $$ \frac{(\alpha+x)_k(\beta+y)_{n-k}}{(\alpha+\beta+x+y)_n}. $$ In particular, the conditional probability that the next draw is red is $(\alpha+x)/(\alpha+\beta+x+y)$.

Proof. Let $H$ denote the event of the specified history and $F$ the event of the specified future sequence. The event $H$ has positive probability, as noted above, so $\mathbb{P}(F\mid H)=\mathbb{P}(H\cap F)/\mathbb{P}(H)$. Apply the sequence formula to the combined history and future. The combined sequence has $x+k$ red and $y+n-k$ blue draws, so its probability is $(\alpha)_{x+k}(\beta)_{y+n-k}/(\alpha+\beta)_{x+y+n}$. The history probability is $(\alpha)_x(\beta)_y/(\alpha+\beta)_{x+y}$. Using $(a)_{u+v}=(a)_u(a+u)_v$, which follows by splitting the defining product after its first $u$ factors, the ratio reduces to $$ \frac{(\alpha+x)_k(\beta+y)_{n-k}}{(\alpha+\beta+x+y)_n}. $$ For $n=1$ and $k=1$, this is $(\alpha+x)/(\alpha+\beta+x+y)$, the asserted next-red probability. $\square$

Worked Example: Predicting One Red in the Next Two Draws

Start with $2$ red and $1$ blue ball and suppose the observed history is $RBR$. Find the conditional probability of exactly one red draw in the next two draws.

The history has probability $1/10>0$, as calculated above. It leaves $4$ red and $2$ blue balls. At each state the red and blue transition probabilities sum to $1$: from $(4,2)$, $4/6+2/6=1$; after either color, the corresponding next-state probabilities also sum to $1$, since they are the two current counts divided by their total.

There are two possible future sequences with exactly one red: $RB$ and $BR$. From $(4,2)$, the probability of $RB$ is $(4/6)(2/7)=8/42=4/21$: after the red draw the state is $(5,2)$, so blue has probability $2/7$. The probability of $BR$ is $(2/6)(4/7)=8/42=4/21$: after blue the state is $(4,3)$, so red has probability $4/7$. Thus

\mathbb{P}(\text{exactly one red in the next two}\mid RBR) =\frac4{21}+\frac4{21}=\frac8{21}.

Check by the count formula: with current counts $r=4,b=2$, the probability is $\binom21(4)_1(2)_1/(6)_2=2\cdot4\cdot2/(6\cdot7)=16/42=8/21$, as obtained by adding the two possible orders.

The Beta-Binomial Predictive Distribution

For a forecast over several draws, the count of red draws has a convenient distribution. The beta-binomial distribution with parameters $n,r,b$, where $n$ is a nonnegative integer and $r,b>0$, assigns probability $\binom{n}{k}(r)_k(b)_{n-k}/(r+b)_n$ to $k$, for $k=0,\ldots,n$. In the urn, $r,b$ are the current red and blue counts. This formula accounts for reinforcement; it is not the ordinary binomial formula with a fixed success probability.

Theorem (Future red-count distribution): Starting from $r>0$ red and $b>0$ blue balls, let $K_n=\sum_{i=1}^n\mathbf{1}_{\{Y_i=R\}}$ be the number of red draws in the next $n$ draws. Then $$ \mathbb{P}(K_n=k)=\binom{n}{k}\frac{(r)_k(b)_{n-k}}{(r+b)_n}, \qquad k=0,1,\ldots,n. $$ After any positive-probability history, the same formula applies with $r,b$ replaced by the current counts.

Proof. Fix $k\in\{0,\ldots,n\}$. The event $K_n=k$ is the disjoint union of all specified length-$n$ sequences containing exactly $k$ red draws. There are $\binom{n}{k}$ such sequences, because choosing the $k$ positions occupied by red uniquely specifies the sequence. By the sequence-probability theorem, each of them has probability $(r)_k(b)_{n-k}/(r+b)_n$. Adding the probabilities of these disjoint events gives the stated formula. The events $K_n=k$, for $k=0,\ldots,n$, partition the full set of possible future sequences. Their probabilities therefore sum to $1$; this also follows from the urn’s transition probabilities, which sum to $1$ at every state. For a conditional forecast after a history, apply the conditional-prediction proposition to the current counts. $\square$

Worked Example: Three Future Draws from a Balanced Urn

Suppose the current urn has $1$ red and $1$ blue ball. Find the distribution of the number $K_3$ of red draws in the next three draws.

At every state the red and blue probabilities are the current counts divided by their sum, so they are positive and add to $1$. Also, $(2)_3=2\cdot3\cdot4=24$, $(1)_1=1$, $(1)_2=1\cdot2=2$, and $(1)_3=1\cdot2\cdot3=6$. Applying the count formula separately for each possible $k$ gives

\begin{aligned} \mathbb{P}(K_3=0)&=\binom30\frac{(1)_0(1)_3}{(2)_3}=\frac6{24}=\frac14,\\ \mathbb{P}(K_3=1)&=\binom31\frac{(1)_1(1)_2}{(2)_3}=\frac{3\cdot1\cdot2}{24}=\frac14,\\ \mathbb{P}(K_3=2)&=\binom32\frac{(1)_2(1)_1}{(2)_3}=\frac{3\cdot2\cdot1}{24}=\frac14,\\ \mathbb{P}(K_3=3)&=\binom33\frac{(1)_3(1)_0}{(2)_3}=\frac6{24}=\frac14. \end{aligned}

Check by sequence probabilities: there is one sequence with zero red draws, $BBB$, and its probability is $(1)_0(1)_3/(2)_3=6/24=1/4$. There are three sequences with one red draw; each has probability $(1)_1(1)_2/(2)_3=2/24=1/12$, giving total $3/12=1/4$. There are three sequences with two red draws, each with probability $(1)_2(1)_1/(2)_3=2/24=1/12$, again giving $1/4$. Finally $RRR$ has probability $(1)_3/(2)_3=6/24=1/4$. The four count probabilities sum to $1$.

Why the Predictive Law Matters

The sequence formula lets us calculate probabilities of particular future patterns; the count formula combines all patterns with the same number of red draws. Both are useful in sequential prediction, where every observed draw changes the current composition and therefore changes the forecast. They also make explicit the distinction between a Pólya urn and independent draws with a fixed red probability. In the balanced-urn example, for instance, the probability of three reds is $1/4$; replacing the urn by three independent draws with red probability $1/2$ would instead give $1/8$.

Common pitfall: freezing the probabilities. With $2$ red and $1$ blue initially, an incorrect calculation treats the probability of blue as $1/3$ even after drawing red, and the probability of red as $2/3$ even after a blue draw. That gives the wrong value $(2/3)(1/3)(2/3)=4/27$ for $RBR$. The correction follows the changing urn composition: after the first red there are $3$ red and $1$ blue, so the second-draw blue probability is $1/4$; after that blue draw there are $3$ red and $2$ blue, so the final red probability is $3/5$. The correct probability is $(2/3)(1/4)(3/5)=6/60=1/10$. At each step, use the current counts and check that the two available color probabilities add to $1$.

Check Your Understanding

For each question, use the urn composition at the time of the draw and verify count probabilities by summing the relevant sequence probabilities.

An urn starts with $3$ red and $2$ blue balls. What is the probability of the sequence $BRR$?
After a history with $2$ red and $3$ blue draws, an urn that started with $1$ red and $1$ blue has what probability of red on the next draw?
Starting from $2$ red and $1$ blue, calculate the probability of exactly two red draws in the next three draws.
Explain why two specified sequences with the same red and blue counts have equal probability, even though successive draws are not independent.
For an urn with $1$ red and $1$ blue ball, verify directly that the probability of exactly three red draws in the next three draws is $1/4$.