# expected number of coin flips given a condition

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?

-
Use Markov chains. Quite a similar question (more complex) is here: math.stackexchange.com/questions/109369/… –  savick01 Feb 24 '12 at 20:10
It may be useful too: ceid.upatras.gr/courses/probweb/lectures/lecture26.ps –  savick01 Feb 24 '12 at 20:18

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

-
follow up: I am unfamiliar with random walks, but I can study the subject. Have you given enough information here to solve a related problem of the coin being biased like so: on the first toss, it is fair, but if heads previously it has a 3/4 chance of being tails, if tails previously it has a 3/4 chance of being heads? –  Robz Feb 24 '12 at 20:37
@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. –  savick01 Feb 24 '12 at 20:45

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.

-
I changed \operatorname{min} to \min. That is already an operator name in $\TeX$. When used in a "displayed" rather than "inline" setting, its subscripts appear directly below it, thus: $\displaystyle\min_{x\in A} f(x)$. I don't think \operatorname{min} will have that feature, whereas \min does. –  Michael Hardy Feb 24 '12 at 21:48
Most importantly: it's shorter. That's a good enough reason for me to use \min :) –  Tom Artiom Fiodorov Feb 25 '12 at 9:40