Assume that when you flip a coin, the probability of getting heads is $1-\alpha$. If you need to flip the coin $N$ times before getting heads, then one can write the expected value of $N$ like so:

$$ E[N] = \underbrace{1}_{1st\ coin\ flip} + \underbrace{\alpha}_{prob.\ it\ fails}\cdot \underbrace{E[N]}_{expected\ \#\ of\ further\ flips} $$

I was presented the above equation in a lecture, but I cannot derive it myself. Can someone shed some light for me and tell me how this is derived?

  • $\begingroup$ This has been discussed repeatedly on MSE, most recently today. The notation there is not the same as yours, but perhaps it will be helpful. If you need further help, I can discuss it in comments. Am reluctant to give an answer, since the question is very much a duplicate. $\endgroup$ – André Nicolas Mar 26 '14 at 19:48

This is known as renewal argument. The logic behind it is to condition on the result of the first toss.

Intuitively at the first toss two things can happen

  1. You can toss heads with probability $1-α$ and in that case you are done. But you have done 1 step.
  2. You can toss tails with probability $α$ and in that case you start anew with the second toss. But again you have done 1 step. Counting this 1 step, it is as if you start tottaly from the beginning with the second step.

Thus $$E[N]=(1-α)\cdot1+α(1+Ε[Ν])=1-α+α+α\cdotΕ[Ν]=1+α\cdotΕ[Ν]$$

Formally denote with $X$ the result of the first step, with $X \in \{T,H\}$ and $P(X=T)=α$ and $P(X=H)=1-α$. Then by the law of total expectation: $$E[N]=E_X\left[E_{N|X}[N|X]\right] \tag1$$ where

  1. $E[N|X=H]=1$ and
  2. $E[N|X=T]=1+E[N]$

Thus, substituting in (1) we find that $$\begin{align*}E[N]&=E_X\left[E_{N|X}[N|X]\right]=P(X=H)E[N|X=H]+P(X=T)E[N|X=T]=\\&=(1-α)\cdot1+α\cdot(1+E[N])=1+α\cdot E[N]\end{align*}$$ which yields the same result.


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.