Problem
I am trying to solve the following question (3.37 from Paul Meyer's "Introductory probability and Statistics", 2nd ed.):
Urn 1, Urn 2, …, Urn n each contain $\alpha$ white and $\beta$ black balls. One ball is taken from Urn 1 into Urn 2 and then one is taken from Urn 2 into Urn 3, etc. Finally, one ball is chosen from Urn n. If the first ball transferred was white, what is the probability that the last ball chosen is white? What happens as n→∞
?
(Hint: Let $p_n$ be the probability that the nth ball transferred is white and express $p_n$ in terms of $p_{n-1}$.
My attempt of a solution
I realize the connection with the question previously asked by me that comes from the same chapter of the same book
I also know that the above problem can be modeled as a Markov Chain with appropriate transition probabilites, but this topic is out of scope of this book and the hint provided in the question by the author implies that the solution must rely on a recurrence relationship.
In general, my intuition suggests that as the numbers of urns increases, the fact that the first ball transferred was white is getting less and less relevant. Therefore, $\lim_{n→∞}p_n \approx p_{n-1}\approx \frac{\alpha}{\alpha+\beta}+\epsilon$, where $\epsilon$ represents some kind of a term that gets to zero as n increases without bound. It should look like a geometric series, since at each step (with each new urn added) we are multiplying the probability of the previous step by the factor that is necessarily less than one.
Setting up a recursive relationship is easy:
$p(w_n)=p(w_n|(w_{n-1})\cdot p(w_{n-1})+p(w_n|\bar w_{n-1})\cdot p(\bar w_{n-1})= \frac{\alpha+1}{\alpha+\beta+1}\cdot p(w_{n-1})+\frac{\alpha}{\alpha+\beta+1}\cdot (1-p(w_{n-1}))$
Now, getting back to the base cases. It is stated that $p_1=1$. Thus, $p_\color{red}{2}=\frac{\alpha+1}{\alpha+\beta+1}=\frac{\alpha^2+\beta\alpha+\alpha+\beta}{(\alpha+\beta)(\alpha+\beta+1)}=\frac{\alpha}{\alpha+\beta}+\frac{\beta}{(\alpha+\beta)(\alpha+\beta+1)^\color{red}{1}}$
If we continue with $p_3$, we get $p_\color{red}{3}=\frac{(\alpha+1)^2}{(\alpha+\beta+1)^2}+\frac{\alpha\beta}{(\alpha+\beta+1)^2}=\frac{(\alpha+\beta)(\alpha^2+2\alpha+1+\alpha \beta)}{(\alpha+\beta)(\alpha+\beta+1)^2}=\frac{\alpha}{\alpha+\beta}+\frac{\beta}{(\alpha+\beta)(\alpha+\beta+1)^\color{red}{2}}$
Hence, the pattern looks like $p_\color{red}{n}=\frac{\alpha}{\alpha+\beta}+\frac{\beta}{(\alpha+\beta)(\alpha+\beta+1)^\color{red}{n-1}}$.
This is in accordance with the solution that I found at the back of the book and the truth is that I performed algebraic manipulations in order to arrive at the formula provided in the answer. My question is whether there exists a systematic way of solving such problems? I don't get how by knowing the limiting behavior of $p_n$ and establishing $p_n$ in terms of $p_{n-1}$ helps in establishing the general formula in terms of $n$. Are there any textbooks/other resources that might shed some light onto it?
Best Answer
The hint probably wants you to first find the recursive formula, then the general formula for $p_n$; after that you can let $n$ go to infinity to see what happens.
By assumption $p_1=1$. If the $n-1$-th ball chosen is white, then there are $\alpha+1$ white balls and $\beta$ black balls before you choose the $n$-th ball, so the (conditional) probability of choosing a white one is $\frac{\alpha+1}{\alpha+1+\beta}$. Similarly, if the $n-1$-th ball chosen is black, then the probability of the $n$-th ball being white is $\frac{\alpha}{\alpha+\beta+1}$. Finally we get $p_n=p_{n-1}\frac{\alpha+1}{\alpha+1+\beta}+(1-p_{n-1})\frac{\alpha}{\alpha+\beta+1}=\frac{1}{\alpha+\beta+1}p_{n-1}+\frac{\alpha }{\alpha+\beta+1}$.
To get the formula for $p_n$ from this recursive relation is standard. You can either guess the formula (which you correctly did) and prove it using the recursive relation, or notice that $p_n-\frac{\alpha}{\alpha+\beta}=\frac{1}{\alpha+\beta+1}(p_{n-1}-\frac{\alpha}{\alpha+\beta})$.