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}}$.