# Hard Probability Problem (at least hard to me) **URL:** \ **Category:** Factual Questions\ **Created:** [September 27, 2002, 5:25pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899 "2002-09-27T17:25:07Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![jebert](https://avatars.discourse-cdn.com/v4/letter/j/ec9cab/32.png) [@jebert](https://boards.straightdope.com/u/jebert)\ **Post date:** [September 27, 2002, 5:25pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/1 "2002-09-27T17:25:07Z")
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^2_q^3 + p_q^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^3_q^3 + 2_p^2_q^4 + p_q^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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 27, 2002, 5:49pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/2 "2002-09-27T17:49:25Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 27, 2002, 5:52pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/3 "2002-09-27T17:52:01Z")
Here we go. It’s the [negative binomial distribution](http://www.math.uah.edu/stat/bernoulli/bernoulli5.html). ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [September 27, 2002, 6:50pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/4 "2002-09-27T18:50:16Z")
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. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [September 27, 2002, 7:01pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/5 "2002-09-27T19:01:07Z")
**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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 27, 2002, 7:22pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/6 "2002-09-27T19:22:25Z")
My bad. ---
**Author:** ![jebert](https://avatars.discourse-cdn.com/v4/letter/j/ec9cab/32.png) [@jebert](https://boards.straightdope.com/u/jebert)\ **Post date:** [September 27, 2002, 9:45pm UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/7 "2002-09-27T21:45:26Z")
**Jabba** , you da man. Thanks. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [September 28, 2002, 12:00am UTC](https://boards.straightdope.com/t/hard-probability-problem-at-least-hard-to-me/129899/8 "2002-09-28T00:00:05Z")
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).