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