Wednesday, May 22, 2013

Probability again, a ball game.

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

Question: Player A and Player B compete in a ball game. Player A has a chance of $p$ to earn a point, and Player B has a chance $q=1-p$ to earn a point. The game ends whenever a player gets 10 points. Now Player A has 7 points and Player B has 5 points. What is the probability that Player A wins the game?

A tennis game


Answer: Player A has to win 3 more points. Before Player A wins the last point, Player B can only wins no more than 4 points.

Method 1. Let $n$ be the number of further games. $n$ can be 3,4,5,...,7. If $n=3$, then Player A wins all the games, the probability is $p^3$. If $n=4$, then Player B may win one of the first 3 games, the probability is $C_1^3p^3q$. For general $n$, Player B may win any $n-3$ of the first $n-1$ games, and the probability is $C_{n-3}^{n-1}p^3q^{n-3}$. Summing up, we have $$P(A)=\left(\sum_{n=3}^7 C_{n-3}^{n-1} q^{n-3}\right)p^3=(1+3q+6q^2+10q^3+15q^4)p^3.$$
Method 2. If we use $a$ to represent the event that Player A earns a point and we use $b$ to represent the event that Player B earns a point, then $$\begin{eqnarray*} &&(1+b+b^2+\ldots)a(1+b+b^2+\ldots)a(1+b+b^2+\ldots)a\\ &=&(1+b+b^2+b^3+b^4+\ldots)^3a^3\\ &=&(1+3b+6b^2+10b^3+15b^4+\ldots)a^3 \end{eqnarray*}$$ consists of all the cases that Player A earns 3 more points. It is easy to see that only up to $b^4$ corresponding to that Player A wins the game. Therefore we have $$P(A)=(1+3q+6q^2+10q^3+15q^4)p^3.$$
The two methods are essentially the same. In the second method, the counting is hidden behind the algebra and we do not need to consider case by case.

Sunday, May 12, 2013

Winner becomes the dealer

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

Question: There is a card game between a dealer and a non-dealer. The odds that the dealer wins to that the other player wins is $p$:$q$. In a scenario, a poor guy with $1$ coins play against a rich guy with $N-1$ coins such that (1) initially the poor guy is the dealer, (2) after each game the winner gets $1$ coin from the loser and becomes the dealer in the next game and (3) no more games if one of the guys collect all the $N$ coins. What is the probability that the poor guy gets the final laugh?




Two-player mahjong is such a winner-becomes-the-dealer game.



Answer: Just like the usual gambler's ruin, we consider the moment that the poor guy having $n$ coins and calculate the probability that he will be the final winner at this moment. However, the chance of winning the current game depends on whether he is the dealer or not, we have to separate the two sub-cases, therefore we have $P_n$ be the probability that he will be the final winner if he is now the dealer and $Q_n$ be the probability that he will be the final winner if he is not the dealer.

We have $$\begin{eqnarray} P_n&=&\frac{p}{p+q}P_{n+1}+\frac{q}{p+q}Q_{n-1}...(1)\\ Q_n&=&\frac{q}{p+q}P_{n+1}+\frac{p}{p+q}Q_{n-1}...(2) \end{eqnarray} $$ with initial conditions $P_0=Q_0=0, P_N=Q_N=1$.

Now $$\begin{eqnarray*} P_{n+1}&=&\frac{p}{p+q}P_{n+2}+\frac{q}{p+q}Q_{n}\\ &=&\frac{p}{p+q}P_{n+2}+\frac{q}{p+q}\left(\frac{q}{p+q}P_{n+1}+\frac{p}{p+q}Q_{n-1}\right). \end{eqnarray*} $$ Rearranging the terms, $$\begin{eqnarray*} \left(1+\frac{q}{p+q}\right)P_{n+1}&=&P_{n+2}+\frac{q}{p+q}Q_{n-1}\\ &=&P_{n+2}+\left(P_n-\frac{p}{p+q}P_{n+1}\right). \end{eqnarray*} $$ Hence $$2P_{n+1}=P_{n+2}+P_n.$$ Using standard technique we have $$P_n=a+bn$$ for some fixed $a$ and $b$. Substitute it back, we have $$Q_n=a+b\left(n+\frac{q-p}{q}\right).$$ Now we turn our eyes to the initial conditions, and we will find that there are no $a$ and $b$ that can satisfy all four! What happens? It turns out that in this scenario, it is not logical to the poor guy to lose all the coins but wins the last game or to win all the coins but lose the last game. Indeed $P_0$ and $Q_N$ could not enter equations (1) and (2). It means we only consider $P_N=1$ and $Q_0=0$, and so $$a=\frac{p-q}{q}\left(N+\frac{p-q}{q}\right)^{-1}, b=\left(N+\frac{p-q}{q}\right)^{-1}$$ Putting all together, $$\begin{eqnarray*} P_n&=&\frac{n+\frac{p-q}{q}}{N+\frac{p-q}{q}}\\ Q_n&=&\frac{n}{N+\frac{p-q}{q}} \end{eqnarray*} $$ The final answer is $P_1=\frac{1+\frac{p-q}{q}}{N+\frac{p-q}{q}}$.

Friday, May 10, 2013

Nine squares

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

Question: There are 9 squares, 3 black and 6 red. In each turn, a square is chosen randomly and its color is then switched. The process continues until all squares have the same color. What is the probability that all squares are red at the end?

REDREDBLACK
BLACKREDRED
REDREDBLACK


Answer: Let $P_k$ be the probability of all red at the end if currently there are $k$ red squares. Note in that turn, there are $\frac{k}9$ chance that a red square turns black and $\frac{9-k}9$ chance that a black square turns red. Therefore $$P_k=\frac{k}{9}P_{k-1}+\frac{k}{9}P_{k+1}, k=1,2,\ldots,8. P_0=0, P_9=1$$ Or in matrix notation, $$\begin{pmatrix}P_0\\P_1\\P_2\\P_3\\P_4\\P_5\\P_6\\P_7\\P_8\\P_9\end{pmatrix}= \begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/9 & 0 & 8/9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2/9 & 0 & 7/9 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3/9 & 0 & 6/9 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4/9 & 0 & 5/9 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 5/9 & 0 & 4/9 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 6/9 & 0 & 3/9 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 7/9 & 0 & 2/9 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8/9 & 0 & 1/9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix}P_0\\P_1\\P_2\\P_3\\P_4\\P_5\\P_6\\P_7\\P_8\\P_9\end{pmatrix}$$ Hence $$\begin{pmatrix}P_0\\P_1\\P_2\\P_3\\P_4\\P_5\\P_6\\P_7\\P_8\\P_9\end{pmatrix} =\begin{pmatrix}0 \\ 35/83 \\ 315/664 \\ 325/664 \\ 165/332 \\ 167/332 \\ 339/664 \\ 349/664 \\ 48/83 \\ 1\end{pmatrix}.$$ Therefore the required probability is $P_6=\frac{339}{664}$ is just barely greater than $1/2$.

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?