M57 wrote:

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. 

That would be simpler! However, failure and success are not independent events. Different failed sequences contribute different probabilities to the overall success. For example, HHTTTT is more likely to result in a success on flip 7 than HTHTHT.

Since the consecutive H's and T's ARE independent, we can calculate by hand the probability of success on 5th and 6th flip pretty easily. HTTTTT and THHHHH both occur with probability 1/64, so the probability of ending on the 6th turn is exactly 1/32, whereas on the 5th flip it is 1/16. The cumulative probability of hitting on flip 5 or 6 is 3/32. Your recursion suggests 15/16 * 1/16 = 15/256, which is not the same number.

http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CDwQFjAD&url=http%3A%2F%2Fpeople.ccmr.cornell.edu%2F~ginsparg%2FINFO295%2Fmh.pdf&ei=alhRUrD1G-P_4APaxoCwBA&usg=AFQjCNFqFAnYFR-6i40c30IIv61MqaA9Yw&sig2=2lUiixxxLK2wWY96gbfE9g&cad=rja

After re-viewing this thread, reconsidering, and digging around the net some more, I really like the above paper for explaining this problem.

Interestingly enough, it comes up with an A(n) of exactly double what hugh calculated.

Excellent find, very nice paper! I had started with Markov chains, but abandoned it.

That paper addresses the problem of getting n heads in a row, but we are looking for either n heads or n tails in a row. Very little modification is required!

On the opening move, we select heads or tails and then we really want 4 in a row after that. So, we add a state that never gets returned to. It goes to the state "0H" from the paper with probability 1. After that, everything is exactly the same, BUT, after any failure, we only need 4 in a row.

So, our situation adds a move with probability 1 in the beginning to select H ror T, but otherwise is exactly the same as the 4 heads in a row situation. Thus, the expected result is 1 + (2^{4+1} - 2) = 31.

I know I asked for "expected result," but I am not sure that is what I want. I am more interested in exact probabilities expressed as percentages at specific rolls, which the paper Cram found answers, suggesting direct and even recursive methods to calculate them, but I am not quite able to decipher the math - so but for trying to estimate the values given for the graph for n=5, I am still left to my own devices.

Regardless, considering Hugh's suggestion that the probability for achieving the goal on roll 6 is 1/32, let me re-phrase my premise a different way..

I agree that it appears that..

Following H with TTTTT is 1/32, and

Following T with HHHHH is 1/32..

so it appears as if 1/32 is correct, but (and stubbornly clinging to the gist of my earlier premise).. seeing as we are now looking at series with lengths of 6, are not HHHHHT, HHHHHH, TTTTTH, and TTTTTT impossible sequences, and shouldn’t they have to be factored out?

I will go and spend some more time with the paper and try to understand it better, but I would really appreciate if someone could post a calculation for a specific toss (say for flip #10) ..or perhaps 2 or 3 recursions starting from flip 5

Thanks for that follow-up, Hugh. You explanation makes it clear what I was missing.

M57 wrote:

I agree that it appears that..

Following H with TTTTT is 1/32, and

Following T with HHHHH is 1/32..

so it appears as if 1/32 is correct, but (and stubbornly clinging to the gist of my earlier premise).. seeing as we are now looking at series with lengths of 6, are not HHHHHT, HHHHHH, TTTTTH, and TTTTTT impossible sequences, and shouldn’t they have to be factored out?

Not quite.

Following H with TTTTT is (1/2)*(1/32)
Following T with HHHHH is (1/2)*(1/32)

Flipping TTTTT or HHHHH with no consideration of what comes before it is 1/32.

Cramchakle wrote:

M57 wrote:

Flipping TTTTT or HHHHH with no consideration of what comes before it is 1/32.

 

Yes, this is why I said 1/32 (in the aggregate) is correct.  I am agreeing with you and Hugh on this, - however, the fact that HHHHHH and HHHHHT is an impossible sequence remains.  I'm having trouble letting go of the apparently false premise that impossible sequences can be ignored.

M57 wrote:

I will go and spend some more time with the paper and try to understand it better, but I would really appreciate if someone could post a calculation for a specific toss (say for flip #10) ..or perhaps 2 or 3 recursions starting from flip 5

 

Hold that request - I think I've figured it out..

The penultimate paragraph on page 4 spells it out..

M57,

Do you understand cumulative probability and how the charts in the Markov Chain paper can help display it?

For example, if you wanted the probability that your 5th head in a row would come on a flip between the 17th and 28th tosses, you would start with M=17 and add together the y-axis value for M=17, M=18, ... M=28. Also, add together the y-axis values for M=0, ... M=17.

Then subtract the sum of the 17~28 values from 1 and subtract the sum of the 0~17 values from that.

Obviously, trying to trace across the values on that image will be impossible, so you need the function for the probability distribution (the formula for the curve on those charts), and you'll need Hugh to help with sorting out some of the finer points.

Cramchakle wrote:

M57,

Do you understand cumulative probability and how the charts in the Markov Chain paper can help display it?

For example, if you wanted the probability that your 5th head in a row would come on a flip between the 17th and 28th tosses, you would start with M=17 and add together the y-axis value for M=17, M=18, ... M=28. Also, add together the y-axis values for M=0, ... M=17.

Then subtract the sum of the 17~28 values from 1 and subtract the sum of the 0~17 values from that.

Obviously, trying to trace across the values on that image will be impossible, so you need the function for the probability distribution (the formula for the curve on those charts), and you'll need Hugh to help with sorting out some of the finer points.

No, I don't.  However, the ranges of M values are so small that I can just sum their individual probabilities.  I can see in the n=5 chart in the paper that (after dividing by 2 to account for heads AND tails), p_(M5-M23) is 50%.

After saying what the probability would be for the first n tosses, the next n tosses, and then one toss after that, the author outlines a strategy. The strategy would rely on knowing how to find the probability of having at least n consecutive heads in N tosses. But, he concludes, "In general, the probability of having at least n consecutive heads in N flips of a fair coin...is difficult to write down in closed form."

But, he managed to calculate the probability distribution with the aid of a computer. Markov chains are not hard to simulate. You can even simulate them using matrix multiplication. Unless some estimation technique gives a nice closed (but estimate) formula, you'll have to use some recursion or programming to find the answers. (***)

I gave you a way to find the probability distribution using a recursion: p(n) = p(n-1) - 1/32 * p(n - 5). Apply that where the first few values are 0, p(5) = 1/16, and p(6) = 1/32. Once you have the distribution, you can answer any of the types of questions you are asking.

*** In principle, we can write a closed form for the recursion I gave, but it isn't very nice. This is typical. Oftentimes the answer just isn't nice, and we must use computers.

What I found interesting is the values apparently remain constant from Rolls 5 through 10.  Hitting 50% at M = 21 is consistent with the n=5 chart hitting 50% at approximately M =42.

I know I'm close, but I'd like to be sure.

For larger values of M, pⁿ(M) becomes the probability of not having more than n − 1 consecutive heads in the first M − (n + 1) flips, then followed by a final tail and n heads in the last n+1 flips. For example, for M = 2n+1 flips, that probability is just all the ways not to have n consecutive flips in the first n flips,then the tail and n heads, so p_n(M = 2n + 1) = (1 − pⁿ)pⁿ⁺¹.

So just to be sure, what is  p_n(M = 2n + 2)?  The only thing that seems to work reasonably is..

=(1 − pⁿ(2M) - pⁿ(2M+1))pⁿ⁺¹...

Hugh wrote:

I gave you a way to find the probability distribution using a recursion: p(n) = p(n-1) - 1/32 * p(n - 5). Apply that where the first few values are 0, p(5) = 1/16, and p(6) = 1/32. Once you have the distribution, you can answer any of the types of questions you are asking.

Hugh, I know you are using a different nomenclature than the paper in the above quote, but I'm pretty sure the paper suggests a very different recursion, and additionally it is in conflict with (most of) our assumptions that the process begins at p(5) - The author of the paper would call it p_n(M = n).

The paper states that the recursion formula doesn't kick in until p_n(M = 2n + 1). 

I use p(n) to mean the probability of getting the first 5 in a row after n flips. In his notation, n is an arbitrary number of heads to get in a row. So, when n = 3, he's talking about a game where the goal is to hit 3 heads in a row. When he writes p_n(M = 2n+1), this is the probability of hitting n heads in row for the first time on the (2n+1)-st coin toss. For n = 3, this is the probability of hitting 3 heads in a row for the first time on the 7th toss. I would have just written p(7), if that was the specific game we were playing. Keep in mind that he is investigating the situation for arbitrary n.

The reason our recursions don't match is because he didn't give you a recursion!!  He gives you something to work out the first few results, up to 2n+1, and then he clearly gives up. The reason is that his goal was a formula FOR ALL n.

If he had known that the goal was just to get a recursion for n = 4, he could have gotten one, because he has a Markov chain, and from a Markov chain, you can get a recursion. He had a way to generate the data, because he has graphs of the probability distributions.

There are ways we can check my recursion. We could look at the Markov chain in matrix form. Also, a brute force program to traverse the probability tree would verify or falsify the result. If my recursion is wrong, fear not, for there IS a correct recursion. We have a Markov chain - it can be done.

M57 wrote:

Hugh, I know you are using a different nomenclature than the paper in the above quote, but I'm pretty sure the paper suggests a very different recursion, and additionally it is in conflict with (most of) our assumptions that the process begins at p(5) - The author of the paper would call it p_n(M = n).

The paper states that the recursion formula doesn't kick in until p_n(M = 2n + 1). 

I see your confusion here. Earlier, we said that our game is identical to the case of n = 4, but with one move added. This is because we choose H or T, and then need 4 H's or 4 T's in a row. If there is a failure in the heads-in-a-row game, it is due to a T, and then H's start all over again. But for us, when there is a failure, we have 1 H or 1T already starting a new sequence. So we only need 4 in a row at that point.

So really, if you want to compare our results, look at his n = 4. My p(10) is his p_4(M = 9). My p(5) = 1/16 and my p(9) = 1/32. The recursion gives p(10) = p(9) - 1/32* p(5). This comes out to 30/1024 = .2929.

His result is (1 - 1/16)*1/32 = 15/512 = 30/1024 = .2929.  They are the same. He doesn't say what it would look like for later values, but his chart looks an awful lot like what my recursion produces. (Your chart did not properly execute my recursion: rounding error, human error ??)

By the way, what school project is this for? I got an engineering degree, not a math one, but some of these concepts didn't show up until 400 level (Jr/Sr for me) stats classes. I'd be really surprised if you were expected to produce a result for which there is no closed form answer for anything less.

Before you catch this typo I made, 30/1024 ~ 0.02929 = 2.929%. The point is that your chart doesn't match this for p(10). At some point, I'll do the Markov chain simulation and post results.

Agree with Cramchakle - easily stated problem, but any reasonable solution is beyond most levels of school math. However, it might be a reasonable exercise for a computer programming class: Quick estimates can be obtained just by simulating the game a bunch of times and recording frequencies based on that.

This would be one bit easier if we changed the question to only include getting 5 H in a row and not 5 H or 5 T.

Also,

I think you could get a reasonable approximation in closed form if you could come up with a formula for the curve shown in the charts of the Markov Chain paper. Then you could set a lower and upper range for the flip containing the fifth H and solve for the probability of the fifth H being within that range by solving for the area under the curve (take the definite integral of the formula from the top of the range to the bottom).

Here's a rough explanation of using the integral to find area under the curve (first search result, not vouching for its quality): http://mathematicsi.com/area-under-a-curve/

Explaining why that area = the probability of the described event is probably an entire chapter in a stats textbook, so I defer on that.

Cramchakle wrote:

By the way, what school project is this for? I got an engineering degree, not a math one, but some of these concepts didn't show up until 400 level (Jr/Sr for me) stats classes. I'd be really surprised if you were expected to produce a result for which there is no closed form answer for anything less.

The problem is not one for students to solve. Per my initial post..

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 choose (from 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).  

The Grades participating range from Grades 4 through 8.

The problem is given as follows..

How many coin tosses will it take until either 5 heads OR 5 tails  in a row are thrown at the All-School Meeting next week? Choose one of the following..

1. 16 or less
2. 17 - 28
3. 29 - 40
4. 41 - 52
5. it wont' happen

About half the votes are already in. We'll have a few hundred students and faculty in the auditorium and I will project the coin tosses on a large projection screen.  We'll stop at 52 if we have no joy, and those that vote "E" will win.

I am interested in finding a more precise answer only to suggest to everyone what the "best" answer is, perhaps with a pie chart or a histogram.  Also, because my math teaching colleagues are interested.

Obviously we have already figured out what the best answers are (in order).  At this point, it's nothing more than a personal quest.