Pólya's urn - Probability first ball is blue given subsequent draws

324 Views Asked by At

I refer to the solution contained in this post here.

I know it must be simple but I cannot deduce why

$$ \begin{align*} P(B_1|B_2\cap \dots \cap B_{n+1})&=P(B_{n+1}|B_1\cap\dots\cap B_n) \end{align*} $$

I presume it is using the fact that $P(B_1|B_2)=P(B_2|B_1)$ so there might be some inductive argument being made but can't seem to get this one. Any help would be appreciated.

2

There are 2 best solutions below

1
On

I think you can show it by induction on the number of $B_k$ events in the condition, with the induction step mirroring the derivation in the preceding equation – but it’s more fun and provides more insight to show it without any calculation like this:

Pólya’s urn is equivalent to drawing a probability $p$ uniformly randomly from $[0,1]$ and then independently drawing balls with probability $p$ to be red and $1-p$ to be blue (see How to prove the rule of succession without calculus?). This formulation reveals the symmetry among the balls: The only information they carry about each other, irrespective of when they were drawn, lies in the information they carry about $p$, so any probability involving the $B_k$ is invariant under permutations of the indices.

5
On

The answer you have linked is incomplete, it lacks some important details. In particular, you cannot conclude that $P(B_1 \mid B_2 \cap \cdots \cap B_{n+1}) = P(B_{n+1} \mid B_1 \cap \cdots \cap B_n)$ simply from the information that $P(B_n)$ is constant (independent of $n$). All you can do is conclude that $P(B_1 \mid B_2) = P(B_2 \mid B_1)$, as is given.

Here's a counterexample: consider a coin which flips heads or tails fairly until it flips two heads (tails) in a row, following which it will always flip heads (tails). By symmetry, one can conclude that $P(H_n) = \frac{1}{2}$. Indeed, we also have $P(H_2 \mid H_1) = P(H_1 \mid H_2) = \frac{1}{2}$ since the first two flips cannot influence each other. However, $P(H_3 \mid H_1 \cap H_2) = 1$ and $P(H_1 \mid H_2 \cap H_3) < 1$ since the flips $THH\cdots$ are certainly possible. That being said, Polya's urn has something more special. One way to argue this is somewhat categorically: enter image description here Each arrow has a certain probability. The important detail is that each square "commutes" in the sense that if you compose the two arrows on the left, you get the same probability as composing the two arrows on the right. This immediately tells you (this is an exercise in induction) that the whole diagram "commutes" in the sense that all possible route from one vertex in the tree to a descendant has the same probability.

How do we get what we want from here? Well, we can first prove that $P(B_{i_1} \cap B_{i_2} \cap \cdots \cap B_{i_n})$ is independent of the pairwise distinct $i_k$ (but dependent on $n$ itself). Consider some other choices of pairwise distinct $j_1, j_2, \ldots, j_n$ and let $N > \max(\{i_k : 1 \leqslant k \leqslant n\} \cup \{j_k : 1 \leqslant k \leqslant n\})$. Look at the two events in the set of all possible routes of size $N$ from the root.

In the event $B_{i_1} \cap \cdots \cap B_{i_n}$, we impose blue on steps $i_k$, but the other steps are free to be either red or blue, and similarly for the other event. However, it is clear that the number of possibilities with a fixed number of reds are equal for both events since we don't care about which steps are imposed to be blue. But this immediately tells us that the probabilities are the same since our diagram tells us that the probability of any route only depends on the number of reds and blues. Now, what you want follows immediately since: $$P(B_{i_1} \mid B_{i_2} \cap \cdots \cap B_{i_{n+1}}) = \frac{P(B_{i_1} \cap B_{i_2} \cap \cdots \cap B_{i_{n+1}})}{P(B_{i_2} \cap \cdots \cap B_{i_{n+1}})}$$