8
$\begingroup$

$p$ is the probability of heads. Note if $p \le 0.5$, the answer is infinity, so assume $p > 0.5$.

What is the expected number of flips of the coin where we have 2 more heads than tails?

Note you would stop flipping the coin when you first encounter the situation where you have 2 more heads than tails.

$\endgroup$
2
  • $\begingroup$ The expected number of flips until the first time where we have 2 more heads than tails? $\endgroup$
    – Chill2Macht
    Mar 24, 2017 at 15:16
  • $\begingroup$ Yes. You would stop flipping the coin after you have 2 more heads than tails. $\endgroup$
    – Jimmy Song
    Mar 24, 2017 at 15:17

2 Answers 2

Reset to default
8
$\begingroup$

We only ever need to keep track of the difference between the number of heads, and the number of tails. Moreover, the time it takes to increase this difference by $2$ is twice the time it takes to increase this difference by $1$.

So let's call $x$ the time it takes to go from a difference of $k$ to a difference of $k+1$: for example, the time it takes from the start until you have flipped heads once more than tails.

After the very first coinflip, we're either done (with probability $p$), or we have made progress in the wrong direction and have a difference of $2$ to make up for (with probablity $1-p$). So we have $$x = 1 + (1-p) \cdot 2x$$ or $x = \frac1{2p-1}$.

The answer you want is $2x = \frac2{2p-1}$.

$\endgroup$
5
  • $\begingroup$ Bravo! Very elegant solution! $\endgroup$
    – Jimmy Song
    Mar 24, 2017 at 15:43
  • 2
    $\begingroup$ Aka, "simplest equation that is 2 at p=1 and infinity at p=0.5". $\endgroup$
    – Yakk
    Mar 24, 2017 at 20:07
  • 1
    $\begingroup$ How hard is it to show that the expected value is in fact finite when ​ 1/2 < p < 1 ? $\hspace{1.44 in}$ After all, ​ x = $\scriptsize+\normalsize \infty$ ​ also satisfies your initial equation for such p.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user57159
    Mar 24, 2017 at 21:14
  • 1
    $\begingroup$ @RickyDemer Let $r$ be the probability that you ever make it from difference $k$ to difference $k+1$. Then $r = p + (1-p)r^2$, which has solutions $r = 1$ and $r = \frac{p}{1-p}$. If $p>\frac12$, only the first of these is a probability. (It's trickier to show that when $p < \frac12$, the second of these and not the first is the correct solution.) $\endgroup$
    – Misha Lavrov
    Mar 24, 2017 at 21:28
  • 1
    $\begingroup$ Sorry, I guess that doesn't rule out the possibility that the expected value is infinite. For that, we might have to actually do some computation (e.g., show that the number of ways to flip $2n$ coins and never have more heads than tails is on the order of $(4p(1-p))^n$, which goes to $0$ pretty quickly as $n \to\infty$). $\endgroup$
    – Misha Lavrov
    Mar 24, 2017 at 21:34
7
$\begingroup$

This corresponds to calculating the expectation of the first-passage time of an asymmetric one-dimensional random walk. I believe that even the asymmetric one-dimensional random walk satisfies the (strong) Markov property, so therefore we can assume that the random walk "starts over" at every step. (See p. 4)

I.e. if $T(1)$ is the random variable indicating the first time we have one more head than tail, then $T(2)$ is the sum of two independent copies of $T(1)$. So by linearity of expectation: $$\mathbb{E}[T(2)]=\mathbb{E}[T(1)]+\mathbb{E}[T(1)]=2\mathbb{E}[T(1)]. $$

Now, $\mathbb{E}[T(1)]$ is a lot easier to calculate. According to this document (p.3 & p.5), $$\mathbb{E}[T(1)] = \Phi'(1)\,, \quad \text{where} \quad \Phi(t) = \frac{1 - \sqrt{1-4p(1-p)t^2}}{2(1-p)t} $$ i.e. $$\mathbb{E}[T(1)] = \frac{1 }{2p-1} \quad (p > \frac{1}{2})\,.$$ (In the document, $N= T(1)$.)

$\endgroup$
0

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.