1
$\begingroup$

Alice and Bob play a coin tossing game. A fair coin (that is, a coin with equal probability of landing heads and tails) is tossed repeatedly until one of the following happens.

$1.$ The coin lands "tails-tails" (that is, a tails is immediately followed by a tails) for the first time. In this case Alice wins.

$2.$ The coin lands "tails-heads" (that is, a tails is immediately followed by a heads) for the first time. In this case Bob wins.

Who has more probability of winning the game?

My attempt $:$

Let $X$ be the random variable which counts the number of tosses required to obtain "tails-tails" for the first time and $Y$ be the random variable which counts the number of tosses required to obtain "tails-heads" for the first time. It is quite clear that if $\Bbb E(X) < \Bbb E(Y)$ then Alice has more probability of winning the game than Bob$;$ otherwise Bob has more probability of winning the game than Alice. Let $X_1$ be the event which denotes "the first toss yields heads", $X_2$ be the event which denotes "tails in the first toss followed by heads in the second toss", $X_3$ be the event which denotes "tails in the first toss followed by tails in the second toss". Then $X_1,X_2$ and $X_3$ are mutually exclusive and exhaustive events. Let $\Bbb E(X) = r.$ So we have $$\begin{align} r & = \Bbb E(X \mid X_1) \cdot \Bbb P(X_1) + \Bbb E(X \mid X_2) \cdot \Bbb P(X_2) + \Bbb E(X \mid X_3) \cdot \Bbb P(X_3). \\ & = \frac {1} {2} \cdot (r+1) + \frac {1} {4} \cdot (r+2)+ 2 \cdot \frac {1} {4}. \\ & = \frac {3r} {4} + \frac {3} {2}. \end{align}$$ $\implies \frac {r} {4} = \frac {3} {2}.$ So $\Bbb E(X) = r = 6.$

But I find difficulty to find $\Bbb E(Y).$ Would anybody please help me finding this?

Thank you very much for your valuable time.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ "It is quite clear that...": I don't see this at all. $\endgroup$ – TonyK Mar 23 '19 at 19:25
  • $\begingroup$ If you can't see leave it @TonyK. $\endgroup$ – math maniac. Mar 23 '19 at 19:37
  • $\begingroup$ Well, in this case it's true, because the set-up is so simple: for any $n$, $\Bbb P(X=n)=\Bbb P(Y=n)$, as Ethan Bolker's answer explains. But for general $X$ and $Y$, I don't think it's true. (And if you can't take criticism, then you shouldn't be posting here.) $\endgroup$ – TonyK Mar 23 '19 at 19:56
  • $\begingroup$ Which is true and which is not true @TonyK? $\endgroup$ – math maniac. Mar 23 '19 at 19:59
1
$\begingroup$

To calculate $E=E[Y]$:

We work from states. There's $\emptyset$, the starting state, or the state in which you've thrown nothing but $H$, there's $T$ in which the string has been $H^aT^b$ with $b>0$, and of course there's the end state.

From the start, you either stay in the starting state or you move to state $\mathscr S_T$. Thus $$E=\frac 12\times (E+1)+\frac 12\times (E_T+1)$$

From state $\mathscr S_T$ we either stay in $\mathscr S_T$ or we end. Thus $$E_T=\frac 12\times (E_T+1)+\frac 12\times 1\implies E_T=2$$

It follows that $$E=4$$

Just to stress: this certainly does not imply that $B$ has a greater chance of winning. The intuitive failure comes from the fact that if you have a $T$ already, and you throw an $H$ next, it takes you at least two turns to get $TT$ whereas if you have a $T$ and throw another $T$ you can still get your $TH$ on the next turn. Indeed, the two have an equal chance of winning, since the first toss after the first $T$ settles the game (as was clearly explained in the post from @EthanBolker).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yeah! This is exactly what I have got @lulu some times ago. $\endgroup$ – math maniac. Mar 23 '19 at 20:16
  • 2
    $\begingroup$ To be clear, this in no way means that Bob has a greater chance of winning, not sure where that idea came from. It's quite clear that the two players have equal chances of victory. @EthanBolker 's argument is on point for that aspect. $\endgroup$ – lulu Mar 23 '19 at 20:23
  • $\begingroup$ Then is the problem wrong? $\endgroup$ – math maniac. Mar 23 '19 at 20:30
  • 2
    $\begingroup$ Well, the problem is fine, but your intuition was wrong. The inequality on expectations does not settle the question of who has the greater chance of winning. I have edited my posted solution to include a brief discussion of why intuition fails in this case. As a general point, it's never a great idea to use expectation as a surrogate for straight probability. $\endgroup$ – lulu Mar 23 '19 at 20:31
  • $\begingroup$ There's a nice paradox here. The expected number of tosses to get TT is indeed greater than the expected number of tosses to get TH, But each participant has the same win probability. My comment on my answer asserting that the two expectations are the same was wrong but my answer is right. $\endgroup$ – Ethan Bolker Mar 23 '19 at 20:33
8
$\begingroup$

Perhaps I am missing some subtlety, in which case someone here will tell me. That said:

The coin is tossed repeatedly. Alice and Bob watch bored until the first tail appears. The next toss will settle the game. Each has an equal chance to win.

The game is more interesting if Bob wins on the first "heads-tails". In that game suppose a head appears before anyone has won. Then Bob will win as soon as the first tail appears, which will happen eventually. Since the first flip is heads with probability $1/2$ Bob wins with at least that probability. If the first flip is tails then Alice wins with tails on the second toss. Bob wins eventually if the second toss is heads. So overall Bob wins with probability 3/4.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is my reasoning not ok @Ethan Bolkar? $\endgroup$ – math maniac. Mar 23 '19 at 19:21
  • $\begingroup$ @mathmaniac. Your reasoning so far might be right - I haven't checked. But you haven't calculated $E(Y)$.. When you do it will turn out to be the same as $E(X)$ so the weak inequality that's "clear" will be an equality. $\endgroup$ – Ethan Bolker Mar 23 '19 at 19:34
  • $\begingroup$ No $\Bbb E(Y) = 4.$ I have just calculated it. So $\Bbb E(X) > \Bbb E(Y).$ So Bob has more probability of winning this game than Alice. My intuition works fine so far @Ethan Bolker. $\endgroup$ – math maniac. Mar 23 '19 at 19:41
  • $\begingroup$ @mathmaniac. Until someone convinces me that my answer is wrong I think yours must be. $E(X) = E(Y) = $ one more than the expected number of tosses to get the first tail. That's $1 + (1 + 1/2 + 1/4 + \cdots) = 1+2=3$. $\endgroup$ – Ethan Bolker Mar 23 '19 at 19:42
  • $\begingroup$ Then what's wrong in my computation of $\Bbb E(X)$? $\endgroup$ – math maniac. Mar 23 '19 at 19:45
1
$\begingroup$

There is 1 fundamental problems with the attempted solution by math maniac:

The comparison of expected values may give a hint, but can be totally misleading and is not an equivalent of who is more likely to win first.

Consider another game, again played with a sequence of fair coin tosses. Alice wins after 5 tosses, no matter what actually comes up. Bob wins after 2 coin tosses if those first 2 tosses are $HH$, otherwise he wins after 6 coin tosses. Who will win first?

The expected number of coin tosses for Alice to win is easy:

$$E(W_A)=5$$

For Bob, there are two cases: The first 2 tosses are $HH$ (probability $\frac14$), or not (probability $\frac34$). With the given number of tosses until the win, this means

$$E(W_B)=\frac14\times2 + \frac34\times 6 = \frac{2+18}4 = 5$$

So the expected number of tosses until the win is $5$ in both cases. Nevertheless, Alice will win in $\frac34$ of all duels, Bob only in $\frac14$. That's because Bob only wins if the sequence of coin tosses starts with $HH$.

The calculation of the expected value for Bob is weighting the outcomes (2 tosses or 6 tosses) with the probabilities ($\frac14,\frac34$). Because $2$ tosses is much smaller than $6$ tosses, the expexted value for Bob is reduced by $1$ from the $6$ tosses is has for the 'majority case' that the sequence does not start with $HH$.

But for the calculation of who will likely win first, it doesn't matter that Bob wins in only 2 tosses if he wins at all. The fact that $2$ is a much smaller number than $5$ (the number of tosses Alice will always need to win) is irrelevant here.

In other words, the fact that if Bob wins, he will use a much smaller number of tosses than Alice is only relevant for the expected value of coin tosses, but not for the win probability itself. That's the reason why the expected value of coin tosses until the win is not the arbiter of who wins first.

| cite | improve this answer | |
$\endgroup$

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.