7
$\begingroup$

I have a fair coin, and I flip it until the following condition is met:

#heads - #tails = N  OR  #tails - #heads = N 

where $N \geqslant 2$.

What is the expected number of times I flip the coin?

  • 0
    It may be useful too: http://www.ceid.upatras.gr/courses/probweb/lectures/lecture26.ps2012-02-24

2 Answers 2

9

Let $X_t$ denote the excess of heads over tails after the $t$th coin toss. Then this problem becomes a well-known result in the theory of random walks, that is solved using first step analysis.

Let $f(x)$ be the expected number of steps needed for $X_t$ to reach $\{-N,N\}$ starting at state $x$. This function satisfies $f(-N)=0,\ f(N)=0,\ \text{ and } f(x)=1+{f(x-1)+f(x+1)\over 2} \text{ for }-N

This forces $f(x)$ to be a quadratic, and since we know the two roots $-N$ and $N$, we conclude that $f(x)=(N+x)(N-x).$ In particular, at $x=0$ we get $f(0)=N^2$.

  • 0
    @Robz: Yes, you just have a different (more complex) system of equations, and $f$ has two arguments: $x$ and the result of the previous flip.2012-02-24
5

This is an answer which contains a lot of "modern" probability in it and should serve as a motivation to study measure-theoretic formulation of probability.

Consider $S_n$ to be a random walk, i.e. a process on $\mathbb{Z}$ such that it starts at $0$ and at each step moves $+1$ or $−1$ with equal probability

We are interested in $\mathbb{E}[T]$, where $T=\min \{n : |S_n|=N \}$. $T$ is an example of a stopping time.

It can be shown that $(S_n)_{n\geq0}$ and $(S_n^2-n)_{n\geq0}$ are both martingales. Application of an appropriate version of Optional Stopping Theorem yields:

$0=\mathbb{E}[S^2_T-T]$ Clearly $\mathbb{E}[S^2_T]=\frac{1}{2}N^2+\frac{1}{2}N^2=N^2$, because random walk is symmetric, and hence the answer.

There are crucial details omitted in the application of the Optional Stopping Theorem, so this is not a complete answer by any means.

  • 0
    Most importantly: it's shorter. That's a good enough reason for me to use \min :)2012-02-25