3
$\begingroup$

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?

  • 1
    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.2011-12-13
  • 0
    @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.2011-12-13
  • 0
    @DilipSarwate and how do you get 2 and 2?2011-12-13
  • 0
    "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.2011-12-13

2 Answers 2

7

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.

  • 1
    What a wonderful answer.2011-12-13
2

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

  • 0
    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 way2011-12-13
  • 1
    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.2011-12-13
  • 2
    "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.$$2011-12-13
  • 2
    "[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$.2011-12-13
  • 0
    @Didier, I didn't claim "symbol-shifting" worked in some general setting, only that it worked in the one setting in which I offered it. 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. But, still: the expected number of heads in 42 throws is 21; is not the expected number of throws until 21 heads 42? Isn't this what the last paragraph of Andre's answer says?2011-12-13
  • 1
    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 .../...2011-12-13
  • 0
    .../... you call "proof" what others call "statement" and that you call "justification" what others call "proof". I see no reasonable way to consider that "to cancel the sixes" proves that 26/65=2/5. (3) *the expected number of heads in 42 throws is 21; is not the expected number of throws until 21 heads 42?* These two statements are true but are they related? And if they are, where is the proof that the first one implies the second one? (4) *Isn't this what the last paragraph of Andre's answer says?* No this is not. (5) Where do you address the remarks made in my previous comment?2011-12-13
  • 0
    @Didier, (1) I was answering a student, not writing a paper, so I left something for the student to do. (2) Even in papers, one leaves out steps. Whether those steps are "justification" or "proof" is moot. (3), (4) I think it's exactly what Andre says, provided you know $E(X_1)=2$. (5) Non-integer values don't arise. Sure, the expected number of heads in 7 tosses is three-and-a-half; but no one would ever ask for the expected number of tosses until exactly three-and-a-half heads. $E(N(n))=k$ implies $E(T_k)=n$ provided $T_k$ is defined; you can't ask for more than that.2011-12-13
  • 0
    @Gerry: Without a proof that $E(N(n))=k$ implies $E(T_k)=n$ including an explicit description of the setting where this holds, the pedagogical value of said hint is doubtful. This value might even be negative, **especially to a student**, since it seems to refer to a general result although such a relation can only hold with qualifications. And you still did not describe "the one setting" you had in mind... (To confuse "proof" and "statement" in a paper you author is your responsability, to do so in a teaching context is a missdeed.)2011-12-14
  • 0
    @Didier, I value your contributions to this website. I feel increasingly like I am being lectured, and I don't like that. Anyway, the one setting I had in mind was the one setting in which I offered it: expected number of tries to get heads twice. As a bonus, it gives the right answer more generally: expected number of tries to get heads $k$ times (for non-negative integer $k$). It even works if the coin is heads with probability $p$, provided only that the quantities that arise are integers. Are we done?2011-12-14
  • 0
    @Gerry: Sorry if my comments offput you. But if you reread the first one, you will see that it simply asked for some explanations about an argument I did not (and still do not) know what to make of (and which I find dangerous to the non expert). The rest (including feelings of being lectured) does not concern me.2011-12-14
  • 0
    @Didier, in your first comment, you ask why $E(N(n))=k$ implies $E(T_k)=n$. If $k$ is a non-negative integer (and if it isn't, $T_k$ n'existe pas), then surely we agree that $E(N(n))=k$ if and only if $E(T_k)=n$, and the implication follows trivially. If you want a proof of the "if and only if," I maintain that it follows from Andre's last paragraph, together with $E(T_1)=2$. But we've been here already, so I must be missing the point.2011-12-14
  • 0
    @Gerry, yes this is the question: why $E(N(n))=k$ would imply $E(T_k)=n$? We have not moved an inch from my first comment, since you did not provide (the beginning of) a proof (if the implication follows *trivially*, this should be easy to explain why it does). Tout ceci est fort dommage mais je suppose que c'est la vie.2011-12-15
  • 0
    @Didier, we must be talking past each other. "$P$ implies $Q$" follows trivially from "$P$ if and only if $Q$," no matter what $P$ is and no matter what $Q$ is. There is nothing to explain (except for why, in this case, $P$ if and only if $Q$ - but I've already disposed of that twice).2011-12-15