Friday, May 3, 2013

A probability game

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Question: At each turn, if Player A has $p$ coins and Player B has $n-p$ coins, then the chance of A wins to the chance of B wins is $p:n-p$ and that whoever wins gain 1 coin from the loser. The game ends if a player gets all the $n$ coins. If currently A has $n_A$ coins and B has $n-n_A$ coins, what is the probability that A is the final winner?



A B
Wealth: $p$ coins Wealth: $n-p$ coins
Winning chance: $p/n$ Winning chance: $1-p/n$




Answer: Let $P_p$ denotes the probability that A is the final winner if A has $p$ coins. Then $$P_p=\frac{p}{n}P_{p+1}+\frac{n-p}{n}P_{p-1}, P_0=0, P_n=1.$$ Then $$\frac{n-p}{n}(P_p-P_{p-1})=\frac{p}{n}(P_{p+1}-P_p)$$ and thus $$P_{p+1}-P_p=\frac{n-p}{p}(P_p-P_{p-1})=\frac{(n-p)(n-(p-1))\cdots(n-1)}{p(p-1)\cdots1}(P_1-P_0)=C_p^{n-1}P_1.$$ Sum over all $P_p$ from $p=0$ to $r-1$, we have $$P_r=\sum_{p=0}^{r-1}(P_{r+1}-P_r)=\sum_{p=0}^{r-1} C_p^{n-1}P_1.$$ Consider the case $r=n$. $$1=\sum_{p=0}^{n-1} C_p^{n-1}P_1=2^{n-1}P_1$$ and hence $$P_1=\frac{1}{2^{n-1}}.$$ The final answer is therefore $$P_{n_A}=\frac{\sum_{p=0}^{n_A-1} C_p^{n-1}}{2^{n-1}}.$$
The wealthier or more powerful A is, the higher the chance A wins each battle. A reasonable model, isn't it?