2
$\begingroup$

Alice and Bob are playing a game. Each of them have 2 candies. Here's how the game goes like:

Alice and Bob flip a coin. If it is heads then Bob gives a candy to Alice. If it is tails then Alice gives a candy to Bob. The player who has all the candies wins.

If $P(heads)=2/3$ and $P(tails)=1/3$ find the probability the Alice wins the game.

$\endgroup$

closed as off-topic by TMM, user91500, SchrodingersCat, BLAZE, user223391 Dec 23 '15 at 5:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TMM, user91500, SchrodingersCat, BLAZE, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ "the player who has the most candies wins" Does the game end once someone has no candies? After one turn? After 10 turns? $\endgroup$ – JMoravitz Dec 16 '15 at 16:15
  • $\begingroup$ It ends when one person has no candy. $\endgroup$ – Sophia Dec 16 '15 at 16:16
  • $\begingroup$ What have you tried? Have you considered analyzing all the games where Alice wins and adding probabilities? $\endgroup$ – Anguepa Dec 16 '15 at 16:22
  • $\begingroup$ You can describe this problem using an absorbing Markov Chain. See similar question here. You will have five states: 4-0(alice wins), 3-1, 2-2, 1-3, 0-4(bob wins). If in state 4-0 or 0-4 then it will remain in that state with probability 1. Otherwise, it will be $\frac{2}{3}$ probability or $\frac{1}{3}$ probability for alice or bob to take another candy respectively. $\endgroup$ – JMoravitz Dec 16 '15 at 16:23
  • $\begingroup$ I'm really confused in this problem, i know the different ways possible sale 4-0,3-1,2-2,1-3 and 0-4 so my belief was that the answer should be 1/5. But then there must be something about P(heads)=2/3 right? $\endgroup$ – Sophia Dec 16 '15 at 16:26
3
$\begingroup$

It is reasonably clear that with probability $1$, one of Alice or Bob must win. Let $p$ be the probability Alice (ultimately) wins.

We look at the result of the first two tosses. Alice wins outright if these are HH. If the results are HT, or TH, then they are tied after two rounds, and the probability Alice ultimately wins, given that they are tied after two rounds, is $p$.

Note that the probability of HH is $\frac{4}{9}$, and the probability of HT or TH is $\frac{4}{9}$. Thus $$p=\frac{4}{9}+\frac{4}{9}p.$$ Solve this linear equation for $p$. We get $p=\frac{4}{5}$.

Another way: If Alice is to win, it must be after an even number of tosses. So divide the sequence of tosses into pairs. Let D be the event two heads, and let M (mixed) be the event head then tail or tail then head. Each of D and M has probability $\frac{4}{9}$.

The ways Alice wins are D, MD, MMD, MMMD, and so on. So the probability Alice wins is $$\frac{4}{9}+\left(\frac{4}{9}\right)^2+\left(\frac{4}{9}\right)^3+\left(\frac{4}{9}\right)^4+\cdots.$$ This infinite geometric series has sum $\frac{4}{5}$.

Remark: We can use either analysis to find the probability Alice wins if the probability of head is $h$, where $0\lt h\lt 1$.

$\endgroup$
3
$\begingroup$

There are 5 possible states for this game: \begin{align} (C_A, C_B)= \begin{cases} (2,2)\\ (1,3)\\ (3,1)\\ (4,0)\\ (0,4)\\ \end{cases} \end{align}

This writes a Markov Chain with

\begin{align} P((C_A, C_B) \mapsto (C_A, C_B)+(i,j))= \begin{cases} 2/3 \qquad &\text{if } (i,j)=(1,-1) \;\&\&\; C_B \geq 1\\ 1/3 \qquad &\text{if } (i,j)=(-1,1) \;\&\&\; C_A \geq 1\\ 1 \qquad &\text{if } i=j \;\&\&\; (C_A =0 || C_B=0) \\ 0 \qquad &\text{Otherwise} \end{cases} \end{align}

Which writes \begin{align} P=\left( \begin{matrix} 1 & 0 & 0 & 0 & 0 \\ \frac{1}{3} & 0 & \frac{2}{3} & 0 & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 \\ 0 & 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ 0 & 0 & 0 & 0 & 1 \\ \end{matrix} \right) \end{align}

We can calculate the invariant measure of this Chain as $\pi = \lim_{k\to\infty} P^k = U^{-1} \Sigma^k U,$. However, as it's periodic, we need to input $v(0)=(0,0,1,0,0)$ where the matrix $U$ is composed by the eigenvectors of $P$ and $\Sigma$ is the diagonal matrix with the eigenvalues of $P$. And the nice thing about $\Sigma$ is that $\Sigma^m= \left(\sigma_{i,j}^m \;;\; (i,j) \in |s|^2\right),$ where $\sigma_{i,j} = 0$ if $i \neq j$. It writes: \begin{align} \lim\limits_{k \to +\infty} P^k=\left( \begin{matrix} 1. & 0 & 0 & 0 & 0 \\ 0.466667 & 0 & 0 & 0 & 0.533333 \\ 0.2 & 0 & 0 & 0 & 0.8 \\ 0.0666667 & 0 & 0 & 0 & 0.933333 \\ 0 & 0 & 0 & 0 & 1. \\ \end{matrix} \right) \end{align}

So, we have $\pi = v(0) \lim\limits_{k \to +\infty} P^k = (0.2, 0., 0., 0., 0.8)$.

This result shows that Alice wins 80% of times they play, and Bob only 2o%, due to the bias in the coin.

$\endgroup$
  • $\begingroup$ What if P(heads)=3/5 and P(tails)=2/5 ? $\endgroup$ – Sophia Dec 16 '15 at 16:58
  • $\begingroup$ It just inverts probabilities of winning and losing of bob and Alice $\endgroup$ – Guilherme Thompson Dec 16 '15 at 19:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.