Short Runs from an Urn
Here is a problem by Neetu Badhoniya, K. S. Bhanu, and M. N. Deshpande (Institute of Science, Nagpur, India) from The American Mathematical Monthly (119, March 2012, pp 249-250) with the solution by Bob Tomper (Mathematics Department, University of North Dakota).
- What Is Probability?
- Intuitive Probability
- Probability Problems
- Sample Spaces and Random Variables
- Probabilities
- Conditional Probability
- Dependent and Independent Events
- Algebra of Random Variables
- Expectation
- Probability Generating Functions
- Probability of Two Integers Being Coprime
- Random Walks
- Probabilistic Method
- Probability Paradoxes
- Symmetry Principle in Probability
- Non-transitive Dice
|Contact| |Front page| |Contents| |Induction| |Up|
Copyright © 1996-2007 Alexander Bogomolny
Solution
Solution is by Bob Tomper (Mathematics Department, University of North Dakota).
Let $E[X_{a,b}]$ and $E[Y_{a,b}]$ be the expected values of $X$ and $Y$ respectively when starting with an urn containing $a$ white balls and $b$ black balls, where $a \ge 2b + 3$.
For $a \ge 3$, we have $E[X_{a,0}]=E[Y_a,0]=0$, which agrees with the given formulae. We use induction on $b$, the number of black balls. Assume the formulae are correct up to $b - 1$, where $b \ge 1$ (and all appropriate $a$ values), and consider the case of $a$ white balls and $b$ black balls with $a \ge 2b + 3$.
The lineup begins with $B,$ $WB,$ $WWB,$ or $WWW,$ where $W$ and $B$ indicate drawing a white or a black ball, respectively. The last also ends the lineup; after each of the others, the number of white balls remaining in the urn is at least three more than twice the number of black balls, so the conditions for the induction hypothesis apply. Accounting for the isolated $W$ in $WB$ and the paired $WW$ in $WWB,$
$E[X_{a,b}]=P[B]\,E[X_{a,b-1}]+P[WB]\,E[X_{a-1,b-1}]+P[WWB]\,(1+E[X_{a-2,b-1}])$,
which gives an expression for $E[X_{a,b}]$:
$\displaystyle \frac{b}{a+b}\,\frac{b-1}{a+1}+\frac{a}{a+b}\,\frac{b}{a+b-1}\,\frac{b-1}{a}+\frac{a}{a+b}\,\frac{a-1}{a+b-1}\,\frac{b}{a+b-2}\left(1+\frac{b-1}{a-1}\right)$.
This simplifies to $\displaystyle \frac{b}{a+1}$. Similarly,
$E[Y_{a,b}]=P[B]\,E[Y_{a,b-1}]+P[WB]\,(1+E[Y_{a-1,b-1}])+P[WWB]\,(1+E[X_{a-2,b-1}])$,
and this simplifies to $\displaystyle \frac{b(a+b+1)}{(a+1)(a+2)}$.
|Contact| |Front page| |Contents| |Induction| |Up|
Copyright © 1996-2018 Alexander Bogomolny
72019503