How to verify by induction that that the probabilities of all sample points add to unity?

I have this question.

An urn contains b black and r red balls. A ball is drawn at random. It is replaced and moreover, c balls of the color drawn and d balls of the opposite color are added. A new random drawing is made from the urn (now containing r+b+c+d balls) and this procedure is repeated. Here c and d are arbitrary integers and may be chosen negative.

Now the event "black at first drawing" has probability $\frac{b}{b+r}$. Similarly, the absolute probability of the sequence black, black is therefore $\frac{b}{b+r}.\frac{b+c}{b+r+c+d}$

The question is how to verify by induction that the probabilities of all sample points add to unity.

• What exactly is your sample space? – jflipp Jan 10 '15 at 12:44

Consider the situation where $n$ balls are drawn. Then there are $2^n$ distinct outcomes (i.e. ways to choose an $n$-length string of B's and R's). We can partition these into the following

$n+1$ events. With $i=0,1,\ldots,n$:

$$A_{n,i} = \text{i of the n balls drawn are black.}$$

So we need to show that for all $n\geq 1,\; \sum_{i=0}^{n}{P(A_{n,i})}=1$.

We use induction. The initial case with $n=1$:

\begin{eqnarray*} P(A_{1,0}) + P(A_{1,1}) &=& \dfrac{r}{b+r} + \dfrac{b}{b+r} = 1. \end{eqnarray*}

Now assume the claim is true for $n$ and look at the case for $n+1$. Firstly, define further events for $k=1,2,\ldots$,

\begin{eqnarray*} B_k &=& \text{the $k^{th}$ ball drawn is black} \\ R_k &=& \text{the $k^{th}$ ball drawn is red.} \\ \end{eqnarray*}

For any $i=0,1,\ldots,n+1$:

\begin{eqnarray*} P(A_{n+1,i}) &=& P(B_{n+1} \mid A_{n,i-1})\;P(A_{n,i-1}) + P(R_{n+1} \mid A_{n,i})\;P(A_{n,i}) \\ && \\ &=& \dfrac{b+c(i-1) + d(n-i+1)}{b+r+n(c+d)}P(A_{n,i-1}) + \dfrac{r+c(n-i) + d(i)}{b+r+n(c+d)}P(A_{n,i}) \end{eqnarray*}

Similarly, we have

$$P(A_{n+1,i+1}) = \dfrac{b+c(i) + d(n-i)}{b+r+n(c+d)}P(A_{n,i}) + \dfrac{r+c(n-i-1) + d(i+1)}{b+r+n(c+d)}P(A_{n,i+1}) .$$

Note that we define $P(A_{k,j})=0$ if $j\lt 0$ or $j \gt k$.

We can now sum the $P(A_{n+1,*})$ in terms of $P(A_{n,*})$:

\begin{eqnarray*} \sum\limits_{i=0}^{n+1}{P(A_{n+1,i})} &=& \sum\limits_{i=0}^{n}{ \dfrac{P(A_{n,i})}{b+r+n(c+d)} \left[(b+c(i) + d(n-i)) + (r+c(n-i) + d(i)) \right]} \\ && \\ &=& \sum\limits_{i=0}^{n}{ \dfrac{P(A_{n,i})}{b+r+n(c+d)} \left[b+r+n(c+d) \right]} \\ && \\ &=& \sum\limits_{i=0}^{n}{P(A_{n,i})} \\ && \\ &=& 1 \qquad\text{by assumption and we are done.} \end{eqnarray*}