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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The expected number of flips until the first time where we have 2 more heads than tails? $\endgroup$ – Chill2Macht Mar 24 '17 at 15:16
  • $\begingroup$ Yes. You would stop flipping the coin after you have 2 more heads than tails. $\endgroup$ – Jimmy Song Mar 24 '17 at 15:17
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}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Bravo! Very elegant solution! $\endgroup$ – Jimmy Song Mar 24 '17 at 15:43
  • 2
    $\begingroup$ Aka, "simplest equation that is 2 at p=1 and infinity at p=0.5". $\endgroup$ – Yakk Mar 24 '17 at 20:07
  • $\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 '17 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 '17 at 21:28
  • $\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 '17 at 21:34
6
$\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)$.)

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