I need a little help with a probability problem.  I’ve created a game/contest in my school where a coin will be tossed at assembly until either 5 heads or 5 tails are thrown consecutively.  Students and faculty can guess (within a set of ranges) on which roll the desired outcome will be achieved, and after the event, I’d like to give a short presentation that suggests what the best choice was (regardless of the actual outcome).  So my questions are as follows..

What is the ‘expected outcome’ or break-even point of an experiment where a coin is tossed until either  5 heads OR 5 tails are thrown consecutively?   In other words, by which roll is it likely that 5 heads or 5 tails will have been tossed?

Additionally and more specifically I’m interested in finding the probability of this occurring over a given range of tosses.

For instance, what is the probability that 5 consecutive heads or 5 consecutive tails will be achieved at exactly  the 17^th through the 28^th tosses.  I have some recursively based theories about how to do this but I’m getting over my head real fast.

Mathaletes HOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

(They're like the Thundercats but they have taped glasses and TI-85 calculators as opposed to swords)

hey i have a TI85! course, i don't remember how to do  much of anythign other than normal calcs & trig, etc...algebra basically

Let's give it a try.

If N is the number of times you toss.

If you toss 5 times, you have 1 chance out of 16 to get 5 times the same result (1/2 that the second toss is the same than the first * 1/2 that the third is the same than the first 2 * 1/2... * 1/2...).

But if N=6, you add another 1/16 as if it did not happen for the first 5, if could happen from number 2 to 6). Result 2/16

N=7 gives 3/16

So the probability is (N-4)/16.

The result you are looking for is when this will be worth 1. The result is 20 as (20-4)/16=1.

I could be wrong, I am not very sure. 

The second part of the question is too complicated for me.

http://math.stackexchange.com/questions/73758/probability-of-n-successes-in-a-row-at-the-k-th-bernoulli-trial-geometric

My experience teaching counting/probability problems is they go from easy to solve to extremely hard fairly quickly.  (In other words you need to be careful when you construct them because it's easy to make one that sounds easy but really is killer.)  What you are suggesting sounds killer and I believe the linked page backs that up.

A geometric distribution will give you the expected number of trials until your 1st success, and the probability of that happening at each trial, but you want n successes.  

And cool kids carry TI-89's these day.  TI-85's have not been cool for years.

Amidon37 wrote:

What you are suggesting sounds killer and I believe the linked page backs that up.

I know it is not an easy problem, but the experiment is finite in length, and though the  (1−p)^k−1 (p) Bernoulli expression that you pointed to is pretty close to what I was thinking, it looks more complicated than what I believe is necessary.

A geometric distribution will give you the expected number of trials until your 1st success, and the probability of that happening at each trial, but you want n successes.  

I only need 1 success, then the game is over.  If I can find the probability for success at any point, it is simply a matter of finding the probabilities recursively for all of the integer points in the range.

Roll 5 is the first opportunity for success, so with the probability at 1/16..

Roll₅ = p
Roll₆ = (1 - Roll₅) * p
Roll₇ = (1 - Roll₅ - Roll₆) * p
Roll₇ = (1 - Roll₅ - Roll₆ - Roll₇) * p

The series is predicated on the theory that the chance for success is highest (1/16) on the first check, and each successive check has a probability of 1/16 of the remaining opportunity.

TI-92s were coming out while i was finishing my 7 years of college. they could put a whole frakin equation in (like equation editor in MSWord). I'd ask to see what they got for step 5 of some simplification/proof or something and they'd answer 'dunno, i plugged it all in...' 

does the 89 supersede the 92s? 

Screw you guys.  I had an HP.   RPN FTW!  (Sorry M57 - I'm no help here)

You've asked a couple of questions. Amidon's link gets you close, I think, to answering the second one. (sorry, toto, I'm not really sure what you're on about)

Things we know. Flips are independent events. The chances of heads or tails is (1/2). For economy of words, we're just going to work on 5 heads in a row and know that everything will be the same for tails instead.

I'll assume you know some basics of independent events, and understand why the chances of 5 heads in a row is (1/2)^5 = 1/32. You could approximately say that if you flipped 5 coins 32 times, you could expect one set of 5 heads in that. So your expected value for a 5th consecutive head is on the 160th flip.

As for the probability of it happening between two flips, the most elegant way probably involves taking the integral of the probability distribution function from the bottom of your range to the top. That is, if you enjoy calculus, anyway.

If you combine Amidon's post with this one, I think you could make a more simplified go of it.

http://math.stackexchange.com/questions/4658/what-is-the-probability-of-a-coin-landing-tails-7-times-in-a-row-in-a-series-of

Edited for wrongness.

weathertop wrote:

TI-92s were coming out while i was finishing my 7 years of college. they could put a whole frakin equation in (like equation editor in MSWord). I'd ask to see what they got for step 5 of some simplification/proof or something and they'd answer 'dunno, i plugged it all in...' 

does the 89 supersede the 92s? 

92's were an evolutionary dead-end (Sort of).  One of the big market for TI is AP Calculus High School classes. The AP people ruled that to be used on the test the calculator could not have a QWERTY keyboard.  So, '92's died.

89's are updated 85's.  They absolutely can do symbolic manipulation.  (solving equations, derivatives/integrals etc.)

84's are also very popular (it is what we use at my school) - and are updated (ultimately) from the 81's.  Some of them have add-in programs that do symbolic manipulation, but they don't come with it.  The newest thing is "pretty print" where you type in something and the calculator shows it to how you would write it on paper.  Think fractions like (x+1)/(x+3) or exponents like x^2

Actually the cutting edge is things call TI-Nspire's.  I am not too familiar with them, but I think they come with geometry packages, etc. like the '92 did and have (wow) color screens.

Is that more than you wanted to know?

BorisTheFrugal wrote:

Mathaletes HOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

(They're like the Thundercats but they have taped glasses and TI-85 calculators as opposed to swords)

ROFL LMOA

BorisTheFrugal wrote:

Mathaletes HOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

(They're like the Thundercats but they have taped glasses and TI-85 calculators as opposed to swords)

Somehow, this motivated me to spend time on the problem!

Before giving lengthy posts, I'll summarize: The expected number of tosses is 31. You can calculate the probability of it ending on the n-th toss using a recursive formula.

This problem barely differs from the math stack exchange posts, but it differs enough to affect the recursive formula for the probabilities.

Looking at outcomes, the sequence ends with THHHHH or HTTTTT. Let a(n) be the number of outcomes where the first 5-in-a-row occurs on the n-th toss. 

To obtain a length n sequence from a length n – 1 sequence, we just insert an H or a T at the very beginning, suggesting something similar to a(n) = 2* a(n-1). But, we have to account for the possibility that a sequence of size n – 1 might begin with HHHH or TTTT, resulting in an illegal sequence. At this point my recursions got a bit complicated, but they simplified nicely to this:

a(n) = 2*a(n-1) – a(n-5)

I can supply details if necessary. It's worth at least checking. If instead of counting outcomes, we go to probabilities, we get

a(n) = a(n-1) – 1/32 * a(n-5)

a(n) = a(n-1) – 1/32 * a(n-5) 

Using the initial data, a(1) = a(2) = a(3) = a(4) = 0, a(5) = 1/16 and a(6) = 1/32, we can calculate the probability that the sequence ends on the 17th or 28th or whatever toss. We can also create a probability generating-function. 

http://en.wikipedia.org/wiki/Probability-generating_function

For this recursion, the GF is g(x) = (1/16 x^5 – 1/32 x^6) / ( 1 – x + 1/32 x^5). The point of this (see wiki article) is that we can find the expected value by calculating g'(1). Remarkably, it comes out to exactly 31 tosses.

Thanks All, I've been going over your posts and working on the problem independently as well.

Hugh's solution is still a bit more complex than my expectation, but his solution for the break even point is in-line with my small-batch samples of experimental data.

Hugh wrote: 

 For this recursion, the GF is g(x) = (1/16 x^5 – 1/32 x^6) / ( 1 – x + 1/32 x^5). 

Hugh - is there a typo in this? I'm getting very large numbers.  I'm assuming that x is n and always some positive integer.

For instance for g(10) = -56,250/3116 ~ -18.05

Or am I misunderstanding what the function represents?

Hmm..

My perspective is a little different.  I think that the probability that you will have tossed 5 in a row at any specific point (after 4 tosses) will be 1/32.  So, there is no greater chance of achieving 5 in a row at the 17th or 100th toss.

However, the more you toss your chance of tossing 5 in a row at ANY point in the past sequence will cumulatively increase.  So on your 100th toss you will have a much higher chance of having tossed 5 in a row at some point in the past compared to your 17th toss.

In that case you need to chose a threshold for your decision.  For example, you can ask "At what toss will you have a 95% chance to have tossed 5 heads in a row at some point in the sequence". 

Hugh – your observation RE: the 6 must be either HTTTTT or THHHHH got me to revising my much simpler recursive model.

Given that on roll 6, the goal will already have been reached 1/16^th of the time, on roll 6 there would seem to be a 15/16*1/16 chance of achieving HHHHH or TTTTT over flips 2-6.  However, as you point out, one of those is not a possibility. Therefore, the new recursion is

Roll₅ =1/16

Roll₆=(1-Roll₅)*1/32

Roll₇=(1-(SUM Roll₅:Roll₇))*1/32
…
Roll_n=(1-(SUM Roll₅:Roll_n-1))*1/32

Please excuse the poor nomenclature - and of course I don't mean Rolls, I  mean Flips.

This is very easy to plug into a spreadsheet.

             Likelyhood                         Cumulative

Also it's easy to find the ranges:

This puts a better than break-even point at Roll 25

I suspect you all disagree with my analysis, so can you please point out its flaw(s)?  Thanks

M57 wrote:

Hugh - is there a typo in this? I'm getting very large numbers.  I'm assuming that x is n and always some positive integer.

For instance for g(10) = -56,250/3116 ~ -18.05

Or am I misunderstanding what the function represents?

Generating functions are goofy tool. I wouldn't use them if I could easily solve the problem without them. However, it is a common tool for the probablists and combinatorialists.

x is not the same as n

A generating function has a Taylor series expansion where the coefficients in the expansion are the numbers in the sequence. For example,  1 / (1 - 2*x) represents the sequence 1, 2, 4, 8, 16, ... But, to find the fourth term of the sequence, you don't plug in x = 4; instead you find the coefficient of x^4 in the Taylor series expansion.

So, to check that my sequence matches your data, you could use Sage/Mathematica/Maple or whatever to expand out the Taylor series of the function.

M57 wrote:

This puts a better than break-even point at Roll 25

I suspect you all disagree with my analysis, so can you please point out its flaw(s)?  Thanks

The numbers look fine, but you are confusing expected value with 50% cumulative probability.

You find expected value by summing the value of the outcome (i.e. which toss the 5th in a row comes on) multiplied by the probability of its occurrence.

Suppose you have an investment that pays off $1, $2, $3, etc with a certain probability, and you find you have a cumulative probability of getting $10 or less with probability 50%. That doesn't make $10 the expected value. For example, if the only other outcome is a 50% chance of a return of $1000, clearly the expected return on investment is much higher.

SquintGnome wrote:

Hmm..

My perspective is a little different.  I think that the probability that you will have tossed 5 in a row at any specific point (after 4 tosses) will be 1/32.  So, there is no greater chance of achieving 5 in a row at the 17th or 100th toss.

1/32 is the probability of ending an arbitrary sequence with HHHHH. In the game, the initial sequences aren't arbitrary because we would have stopped on any previous HHHHH or TTTTT sequence.

After 5 tosses, we have HHHHH or TTTTT as winning, so 1/16 is the probability of ending it outright.

After 6 tosses, we have THHHHH or HTTTTT as the ones that end on the 6th toss exactly. This happens with probability 1/32, which is not the same as ending on the 5th toss. This difference occurs because TTTTTT and HHHHHH are sequences that end the game on the 5th toss, not on the 6th toss.