0
$\begingroup$

Two players A and B play a game in which they alternately flips a coin. Player A starts the game. If a player gets T and another player got H before, he/she is the winner. What is the expected no. of flips for A to win ?

Ex:-

Game-1: HT --> B wins

Game-2: HHT --> A wins

$\endgroup$
  • 2
    $\begingroup$ You must share your thoughts on the problem. $\endgroup$ – StubbornAtom Aug 26 '17 at 16:34
  • $\begingroup$ What I can think is to find probability for A to win in n flips and then use the formula of expectation to find the expected no. of flips. But this method is quite lengthy. Is there any better solution? $\endgroup$ – Sumit Kumar Aug 26 '17 at 16:38
  • $\begingroup$ So the person who wins is the first person to get tails after someone has gotten heads, is that right? $\endgroup$ – Arthur Aug 26 '17 at 16:41
  • $\begingroup$ If B wins, presumably A never wins $\endgroup$ – Henry Aug 26 '17 at 16:43
  • $\begingroup$ @Arthur A player who get tails wins if and only if another player has gotten heads in the previous flip i.e. a sequence HT occurs $\endgroup$ – Sumit Kumar Aug 26 '17 at 16:43
0
$\begingroup$

We expect four coin flips. That's because we first expect two flips to get the first heads, and then we expect two flips to get the first tails.

More detailed: as a player is about to throw, the game is in one of two states: either there hasn't been any heads yet, or there has been at least one head (and since the game isn't over, the last throw must've been a head). Let's call the expected number of throws left until the game is over if we're in the first state $E_1$, and the expected number of throws left if we're in the second state $E_2$.

First we calculate $E_2$. If a player is about to throw, and the last throw was a heads, then there's a probability of $0.5$ of the game ending in one more throw, and a probability of $0.5$ of the game continuing to the next player still in the same state, which means that after that we expect another $E_2$ throws. This implies $$ E_2=0.5\cdot1+0.5(1+E_2)\\ E_2=2 $$ Now we get to $E_1$. If a player is about to throw, and there hasn't been any heads yet, then there is a probability of $0.5$ that the player throws heads, and the game continues in state two, which means that we expect another $E_2=2$ throws, and there is a probability of $0.5$ of the player throwing tails, which means that the game continues in the first state, and we expect another $E_1$ throws. This gives $$ E_1=0.5(1+E_2)+0.5(1+E_1)\\ E_1=4 $$ which is our answer.

$\endgroup$
0
$\begingroup$

Given that $A$ wins, we have an odd number of flips.

Last flip is $T$ and others consist of a possible run of tails, followed by a definite run of heads.

Let $N$ be the number of flips total.

$$P(N=n)=\frac{1}{2}\sum_{k=1}^{n-1}\left(\frac{1}{2}\right)^{n-1}=\frac{n-1}{2^n}$$ $$P(A)=P(N\equiv 1\mod 2)=\sum_{k=1}^\infty P(N=2k+1)=\sum_{k=0}^\infty\frac{k}{4^k}=\frac{4}{9}$$.

$$E(N|A)=\frac{9}{4}\sum_{k=1}^\infty\frac{k(2k+1)}{4^k}=\frac{13}{3}$$

The $E(N)=4$ result above is wrong since it is the total expectation $E(N)$ of coin flips until endgame. The total expectation $E(N)$ is, however, an interesting quantity as well, since it is equivalent to a special case of the following theorem involving a typing monkey:

Let a monkey type letters on a typewriter that has some alphabet $\Sigma$ and let $w\in\Sigma^*$. Also let $\{w_1,\cdots,w_n\}$ be the set of those strings that are both a prefix and suffix of $w$.

If the monkey types until the last letters typed form $w$ and then stops typing, let $X$ be the total number of letters typed. Then $$E(X)=\sum_{k=1}^n|\Sigma|^{|w_k|}$$

The theorem is provable with Martingale Theory.

Example:

Typewriter alphabet: $\{A,B,\cdots,Z\}$ (Standard English).

Monkey's Goal: $ABRACADABRA$.

Prefix-Suffix Strings: $\{A,ABRA,ABRACADABRA\}$ of sizes $1,4,11$.

So the monkey will on average type $26+26^4+26^{11}=3670344487444778$ letters.

$\endgroup$
  • $\begingroup$ I have done exactly the same except that i have not multiplied 9/4 as you did in the last equation. Can you please explain why have you done that? $\endgroup$ – Sumit Kumar Aug 27 '17 at 6:11
  • $\begingroup$ We are only concerned with expected value $E(N|A)$ of coin flips given that $A$ wins. $A$ wins if $N$ is odd, and loses if $N$ is even. We know how to easily get the total expectation $E(N)$ and the probability of $A$ winning. It is known that if $N$ is a random variable and $A$ is any event, then $E(N|A)$ is given as the weighted arithmetic mean of $E(N|X=x)$ with weights being probabilities of those outcomes $X=x$ that make $A$ happen. Recall that in the discrete case, the weighted mean is $\frac{w_1x_1+\cdots+w_nx_n}{w_1+\cdots+w_n}$ $\endgroup$ – Roman Chokler Aug 27 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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