Hard Probability Problem (at least hard to me)

Factual Questions
1

I have a weighted coin with probability of Heads = p and probability of Tails = q = 1-p. I perform a trial in which I toss the coin until I get a sequence of n tails in a row and then stop tossing. The outcome is the total number of tosses in the trial. What is the expected value for the number of tosses in a trial? Equivalently, if I perform a very large number of trials, what is the average number of tosses per trial?

The claimed answer is (1 - q^n)/(p*q^n). (The caret symbol ^ denotes exponentiation.) I have tried to derive this result using the direct method of summing the products of the value each possible outcome and the probability of that outcome, that is, SUM of V * p(V) over all values of V, where V is a possible length of a trial.

For example, with n = 3, the shortest possible length of a trial is 3, which occurs when the first 3 tosses are Tails (TTT), with probability q^3.

A trial of length 4 occurs only with sequence HTTT, with probability p*q^3.

A trial of length 5 occurs with sequences HHTTT or THTTT. Thus a trial of lenth 5 occurs with probability p^2q^3 + pq^4.

Then it starts to get messy. A trial of length 6 can occur with sequences HHHTTT, THHTTT, HTHTTT, or TTHTTT. The probability of a trial of length 6 is p^3q^3 + 2p^2q^4 + pq^5.

Enumerating all the possible sequences of length k for the case of 3 tails in a row is formidable enough, let alone for the generalized case of n in a row. Can any Doper provide a proof of the (1 - q^n)/(p*q^n) answer.

2

There’s a particular distribution that measures the number of trials necessary till the kth success, but I’ll be damned if I can remember the name.

3

Here we go. It’s the negative binomial distribution.

4

Let X = no. of tosses required.
Let A[sub]k[/sub] be the event that the first k tosses are tails and the (k+1)th is a head, for k = 0,1,…n-1. Let B be the event that the first n tosses are tails. Then ( key part)
E(X) = E(X|A[sub]0[/sub])P(A[sub]0[/sub]) + … + E(X|A[sub]n[/sub])P(A[sub]n[/sub]) + E(X|B)P(B)

Now P(A[sub]k[/sub]) = pq[sup]k[/sup]
P(B) = q[sup]n[/sup]
Now for the conditional expectations:
if B happens then we only need n tosses i.e. E(X|B) = n.
if A[sub]k[/sub] happens then k+1 tosses have already happened and then we have to start counting again from there i.e. E(X|A[sub]k[/sub]) = E(X) + k + 1

Plugging these into the above:
E(X) = p(E(X) + 1) + pq (E(X) + 2) + … + pq[sup]n-1[/sup](E(X) + n) + q[sup]n[/sup]n
= p(1 + q + q[sup]2[/sup] + … + q[sup]n-1[/sup])E(X) (*)

  • p(1 + 2q + 3q[sup]2[/sup] + … + nq[sup]n-1[/sup]) (**)
  • nq[sup]n[/sup] (***)

() = p(1 - q[sup]n[/sup])E(X)/(1 - q) = (1 - q[sup]n[/sup])E(X)
() is slightly trickier. Note first that
q + q[sup]2[/sup] + … + q[sup]n[/sup] = q(1 - q[sup]n[/sup])/(1 - q) = (q - q[sup]n+1[/sup])/(1 - q)
Differentiating ( and using the quotient rule on the RHS),
1 + 2q + 3q[sup]2[/sup] + … nq[sup]n-1[/sup] = {(1 - q)(1 - (n+1)q[sup]n[/sup]) + q - q[sup]n+1[/sup]}/(1 - q)[sup]2[/sup]
and so
() = (1 - (n+1)q[sup]n[/sup] + nq[sup]n+1[/sup])/(1 - q)
and
() + () = (1 - q[sup]n[/sup])/p ( I have omitted some trivial algebra here).

Thus finally
E(X) = (1 - q[sup]n[/sup])E(X) + (1 - q[sup]n[/sup])/p
and rearranging we have the stated result.

5

ultrafilter: The negative binomial distribution counts the number of tosses required until the nth tail altogether ( it is a sum of geometric distributions). It does not distinguish runs of consecutive tails.

6

My bad.

7

Jabba, you da man. Thanks.

8

You’re welcome. I should say that I assumed from the fact that you had the answer in advance that this was not your homework. I hope that is the case ( I don’t mind giving hints for homework, but not complete solutions).