# Throwing coins until get 2 heads

I have coin, and want to get 2 heads exactly. I will throw it until this condition is met.

What is expected number of tries for this condition?

I know that it would be $$\sum\limits_{n=2}^\infty P(X=n)n=0.5^n \cdot n\cdot(n-1)$$ however I don't have an idea how to solve that sum because we didn't learn how to. I have knowledge just how to solve geometrical and arithmetical progression's sum. Maybe it's possible to get expected value using Poisson distribution?

-
Do you mean two Heads in succession, or just toss the coin repeatedly till the second Head occurs? In the latter case, look for something called the negative binomial distribution. It models the waiting time for the second occurrence of an event. The average waiting time is the sum of the waiting times for the first head ($2$) plus the additional waiting time for the second head which is also $2$ for a grand total of $4$. Analysis of the other version (two heads in succession) is more complicated. –  Dilip Sarwate Dec 13 '11 at 1:55
@DilipSarwate what do you mean two heads in succession? I am throwing, throwing and I get one head, I am throwing throwing then I get second head and I stop. –  Templar Dec 13 '11 at 1:59
@DilipSarwate and how do you get 2 and 2? –  Templar Dec 13 '11 at 2:01
"I am throwing, throwing and I get one head, I am throwing throwing then I get second head and I stop." That is the second model. Two heads in succession means keep going if you see, for example, HTTHTTTHTHTHTTTT etc because you have not yet seen two H one after another as in HTTHTTTTHTHTHTTTTTTHH. –  Dilip Sarwate Dec 13 '11 at 2:06

Your analysis is right. The probability that $X=n$ is indeed $(n-1)(0.5)^n$. This is because we need to have exactly $1$ head in the first $n-1$ tosses (probability $(n-1)(0.5)^{n-1}$) and then a head (probability $0.5$). So the required expectation is $$\sum_{n=2}^\infty (n)(n-1)(0.5)^n. \qquad (\ast)$$

To get a closed form for this, note that (if $|x|<1$) then $$\frac{1}{1-x}=1+x+x^2+x^3+x^4+x^5+\cdots.$$ Differentiate both sides with respect to $x$, twice. We get $$\frac{1}{(1-x)^2}=1+2x+3x^2+4x^3+5x^4+\cdots,$$ and then $$\frac{2}{(1-x)^3}=2+(3)(2)x+(4)(3)x^2+(5)(4)x^3+ \cdots.$$ Put $x=0.5$. We get $$16=2+(3)(2)(0.5)^1 +(4)(3)(0.5)^2+ (5)(4)(0.5)^3+\cdots. \qquad(\ast\ast)$$ To make the right-hand side of $(\ast\ast)$ equal to $(\ast)$, we need to multiply by $(0.5)^2$. So our expectation is $(16)(0.5)^2$, which is $4$.

There are better (meaning more probabilistic) ways of tackling the problem. For example, let $X_1$ be the waiting time, that is, number of tosses, until the first success (head), and let $X_2$ be the waiting time between the first success and the second. Then $X=X_1+X_2$, and therefore $E(X)=E(X_1)+E(X_2)$. The random variables $X_1$ and $X_2$ each have geometric distribution with parameter $p=1/2$. The expectation of a geometric distribution with parameter $p \ne 0$ may be something you have already seen: it is $\frac{1}{p}$. Note that the same idea works with essentially no change if $X$ is the number of tosses until, say, the $17$-th head.

-
What a wonderful answer. –  Gigili Dec 13 '11 at 20:55

The probability that it will take exactly $n$ throws is the probability of getting exactly one head in the first $n-1$ throws, times the probability of getting heads on the $n$th throw, so it's $((n-1)/2^{n-1})(1/2)$, which is $(n-1)/2^n$. So the expected number of throws is $\sum_{n=2}^{\infty}n(n-1)/2^n$. Series similar to this one have come up many times on this site. See, for example, Generalizing $\sum \limits_{n=1}^{\infty }n^{2}/x^{n}$ to $\sum \limits_{n=1}^{\infty }n^{p}/x^{n}$

-
that's the problem, we haven't learn such summing and I don't understand it and probably I need to solve it in a different way –  Templar Dec 13 '11 at 2:04
Here's a much simpler way: the expected number of heads in 4 throws is 2, so the expected number of throws until 2 heads is 4. Unfortunately, justifying this bit of symbol-shifting is a long story. –  Gerry Myerson Dec 13 '11 at 2:17
"Unfortunately, justifying this bit of symbol-shifting is a long story." A plausible explanation might be that if $A$ is the average number of tosses to get a Head, then with probability $\frac{1}{2}$, one toss is sufficient, and if you got a Tail instead on the first toss (which also has probability $\frac{1}{2}$), you are back to Square One and have to toss an average of $A$ times more. So, $$A = \frac{1}{2}\times 1 + \frac{1}{2}\times(1+A) \Rightarrow A = 2.$$ –  Dilip Sarwate Dec 13 '11 at 3:03
"[T]he expected number of heads in 4 throws is 2, so the expected number of throws until 2 heads is 4": Wow... Let $N(n)$ denote the number of heads in $n$ throws and $T_k$ the expected number of throws until $k$ heads. Obviously $N(T_4)=4$ almost surely and $\mathrm E(N(2))=4$ but I fail to see why, in general, $\mathrm E(N(n))=k$ would imply that $\mathrm E(T_k)=n$ (first of all, what about noninteger values of $\mathrm E(N(n))$?), whether one uses "symbol-shifting" or not. (Note that @Dilip explains something else, which is how to prove that $\mathrm E(T_1)=2$. –  Did Dec 13 '11 at 6:59
Let me assume you are not playing word games but are really meaning what you wrote. Then I see four parts in your last comment, and a fifth part which is missing. (1) I didn't claim "symbol-shifting" worked in some general setting, only that it worked in the one setting in which I offered it: You claimed but you did not prove. And you did not describe the exact setting where the argument works. (2) In a similar vein, I would claim that a simple way to prove 26/65=2/5 is to cancel the sixes, but justifying the cancellation is the hard part. It seems that .../... –  Did Dec 13 '11 at 13:42