Polya's urn scheme - Proof by induction

54 Views Asked by At

I created this proof (with the help of this post) because I was struggling with this type of problem, and I wanted to share it here in case someone else needs it.
Exercise 17

Let's describe the example 7:
The Polya's urn scheme: Suppose a box contains $r$ red balls and $b$ black balss. A ball is drawn and its color noted. Then the ball is returned to the box along with $c > 0$ additionals balls of the same color. The procedure is repeated until the number of balls drawn is $n$.
Let $R_j$ denote the set of the $j$th ball is red and $B_j$ the set of $j$th ball is black and $1 \leq j \leq n$. We can describe these events for each $j$ as

$R_1 = \{r\}$,   $B_1 = \{b\}$
$R_2 = \{(r, r), (b, r)\}$,   $B_2 = \{(b, b), (r, b)\}$
$R_3 = \{(r, r, r), (r, b, r), (b, r, r), (b, b, r)\}$,   $B_3 = \{(b, b, b), (b, r, b), (r, b, b), (r, r, b)\}$
.
.
.
$R_n = \{ \underbrace{(r, r,..., r),..., (b, b,..., r)}_{\text{n}} \}$,   $B_n = \{\underbrace{(b, b,..., b),...(r, r,...b)}_{\text{n}}\}$



and this means $R_j \cap B_j = \emptyset \; \forall \;\; 1 \leq j \leq n$

Then, we can define $\Omega$ as
$\Omega = \{(\omega_1, \omega_2, ..., \omega_n) \; | \; (\omega_1, \omega_2, ..., \omega_n) \in R_n \cup B_n\}$   as the union set of $R_n$ and $B_n$.
If we draw $k$th balls, there are $(b + r + c(k-1))$ balls and $\Omega = \{(\omega_1, \omega_2, ..., \omega_k) \; | \; (\omega_1, \omega_2, ..., \omega_k) \in R_k \cup B_k\}$. Therefore the probability of draw any particular ball at the $k$ draw is $(b + r + c(k-1))^{-1}$. So

$P(R_1)= \frac{r}{r+b}$
$P(B_1) = \frac{b}{r+b}$

$P(R_2|R_1)=\frac{r + c}{r + b + c}$
$P(R_2|B_1)=\frac{r}{r + b + c}$
$P(R_1 \cap R_2) = P(R_2|R_1) \times P(R_1)= \frac{r + c}{r + b + c} \times \frac{r}{r+b} $
$P(B_1 \cap R_2) = P(R_2|B_1) \times P(B_1)= \frac{r}{r + b + c} \times \frac{b}{r+b} $
Consenquently $P(R_2) = P(R_1 \cap R_2) + P(B_1 \cap R_2) = \frac{r + c}{r + b + c} \times \frac{r}{r+b} + \frac{r}{r + b + c} \times \frac{b}{r+b} = \frac{r}{b+r} = P(R_1)$
$P(B_2)= \frac{b}{r+b} = P(B_1)$

Now suppose that the probability of $P(R_n)$ is $$P(R_n) = P(R_{n-1} \cap R_n) +P(B_{n-1} \cap R_n)) = \frac{r_n}{b_n+r_n}$$
and
$$P(B_n) = P(R_{n-1} \cap B_n) +P(B_{n-1} \cap B_n)) = \frac{b_n}{b_n+r_n}$$
This means that $P(R_{n+1} | R_n) = \frac{r_n + c}{b_n + r_n + c}$ and $P(R_{n+1} | B_n) = \frac{r_n}{b_n + r_n + c}$ and

$$ P(R_{n+1}) = P(R_n)\times P(R_{n+1} | R_n) + P(B_n) \times P(R_{n+1} | B_n) $$
$$P(R_{n+1}) = \frac{r_n}{b_n + r_n} \times \frac{r_n + c}{b_n + r_n + c} + \frac{b_n}{b_n+r_n} \times \frac{r_n}{b_n + r_n + c} $$
$$P(R_{n+1}) = \frac{r_n}{b_n + r_n} \times \frac{r_n + c}{b_n + r_n + c} + \frac{r_n}{b_n+r_n} \times \frac{b_n}{b_n + r_n + c} $$
$$P(R_{n+1}) = \frac{r_n}{b_n + r_n} (\frac{r_n + c}{b_n + r_n + c} + \frac{b_n}{b_n + r_n + c} ) $$
$$P(R_{n+1}) = \frac{r_n}{b_n + r_n}$$