Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.