bonanova Posted October 10, 2008 Report Share Posted October 10, 2008 Here's a simple question about probability and expectation. On average, how many times do you need to flip a fair coin before you have seen a run of an odd number of heads, followed by a tail? This puzzle was submitted, but not used, in the International Mathematical Olympiad twenty-five years ago. What makes it appealing for use as a test question [where time can be of the essence] is that it has an easy answer as well as a difficult answer. That is it tests for insight. As such it qualifies as a puzzle as well as a math question. Extra bragging rights go to the solver who solves it both ways. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Here's a simple question about probability and expectation. On average, how many times do you need to flip a fair coin before you have seen a run of an odd number of heads, followed by a tail? This puzzle was submitted, but not used, in the International Mathematical Olympiad twenty-five years ago. What makes it appealing for use as a test question [where time can be of the essence] is that it has an easy answer as well as a difficult answer. That is it tests for insight. As such it qualifies as a puzzle as well as a math question. Extra bragging rights go to the solver who solves it both ways. Must the tail also in odd number? :huh Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 My suggestion is : two times is enough, tough it seemed me rather low. My solution: Sigma(n) (sum of) from 2 to inf. (1/2)^n = 1/2 then you need 2 toss. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 could it be like 3 real heads followed by a dogs tail or something like that?? Quote Link to comment Share on other sites More sharing options...
0 Yoruichi-san Posted October 10, 2008 Report Share Posted October 10, 2008 (edited) My suggestion is : two times is enough, tough it seemed me rather low. My solution: Sigma(n) (sum of) from 2 to inf. (1/2)^n = 1/2 then you need 2 toss. that you need n to be even (using your notation), since you need n-1 to be odd, so the probability should be 1/2*1/2=1/4, so the expected number should be 4. In the spirit of the Math Olympiad, doing it quickly, what I *think* is the "easy way" (plus I need to get to sleep ;P) The probability of having a string n-1 of heads is (1/2)^(n-1). The probability of the next one being tails is 1/2. So the probability of having a string n-1 of heads and then a tails is (1/2)^n. Start from n=2 b/c you need at least one heads and one tails, and summing up the geometric series gives 1/2. Since you need n-1 to be odd, divide again by two (alternatively you could have considered an odd series of heads (1/2)^(2n-1)), and you get 1/4 probability of an odd string of heads followed by a tails. Using the result we proved in a different thread , the expected number of tosses is 4. (I'm not sure if this works, but)is the real "easy way" to say: When you get your first tails, there is an equal 1/2 chance of the string of heads before being even or odd. And the probability of the first coin tossed not being a tails is 1/2, giving 1/2*1/2=1/4, and using the same result, the expected number of coin tosses is 4? Edited October 10, 2008 by Yoruichi-san Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 first flip a head second flip a tail will make the eqution true. But that is only one solution. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 (I'm not sure if this works, but)is the real "easy way" to say: When you get your first tails, there is an equal 1/2 chance of the string of heads before being even or odd. And the probability of the first coin tossed not being a tails is 1/2, giving 1/2*1/2=1/4, and using the same result, the expected number of coin tosses is 4?that you need n to be even (using your notation), since you need n-1 to be odd, so the probability should be 1/2*1/2=1/4, so the expected number should be 4. In the spirit of the Math Olympiad, doing it quickly, what I *think* is the "easy way" (plus I need to get to sleep ;P) The probability of having a string n-1 of heads is (1/2)^(n-1). The probability of the next one being tails is 1/2. So the probability of having a string n-1 of heads and then a tails is (1/2)^n. Start from n=2 b/c you need at least one heads and one tails, and summing up the geometric series gives 1/2. Since you need n-1 to be odd, divide again by two (alternatively you could have considered an odd series of heads (1/2)^(2n-1)), and you get 1/4 probability of an odd string of heads followed by a tails. Using the result we proved in a different thread , the expected number of tosses is 4. You're right Yourichi-san, I calculated the probability of getting a tail before an odd number of heads. But it was not the question Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted October 10, 2008 Author Report Share Posted October 10, 2008 Must the tail also in odd number? :huh Here are some examples of what you want to have happen. It should clear up what the OP asks: Here the dots represent H or T but with the caveat that the dots don't contain the string of results you want. . . . . H H H T [8 tosses] . . . . . . . H H H H H T [13 tosses] H T [2 tosses] Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Here are some examples of what you want to have happen. It should clear up what the OP asks: Here the dots represent H or T but with the caveat that the dots don't contain the string of results you want. . . . . H H H T [8 tosses] . . . . . . . H H H H H T [13 tosses] H T [2 tosses]I'm confused. What if you tossed: T H H T Would that count as a success? That includes the string "H T" but is preceded by another head. Technically it meets the criteria but I suspect that wasn't what you meant... Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Here are some examples of what you want to have happen. It should clear up what the OP asks: Here the dots represent H or T but with the caveat that the dots don't contain the string of results you want. . . . . H H H T [8 tosses] . . . . . . . H H H H H T [13 tosses] H T [2 tosses] for "H T" will be (1/2)2 for "H H H T" will be (1/2)4 for "H H H H H T" will be (1/2)6 for (2n-1) odd number of head followed by a tail, the probability = (1/2)2n hence the average expectation should be x * p(x) which is 1*(1/2)2+3*(1/2)4+5*(1/2)2+.....+ (2n-1)*(1/2)2n+..... well, am I on the right track? :huh Quote Link to comment Share on other sites More sharing options...
0 Yoruichi-san Posted October 10, 2008 Report Share Posted October 10, 2008 (edited) You're right Yourichi-san, I calculated the probability of getting a tail before an odd number of heads. But it was not the question Lol, and you're right! I forgot about the tail before the string of heads! The string needs to be bound on both sides by tails, so the probability is actually 1/8 -> average of 8 tosses. Basically the probability of having an odd string of heads*probability of tails on both sides = (1/2)^3 Lol...didn't I say I was going to bed? Edited October 10, 2008 by Yoruichi-san Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 I'm confused. What if you tossed: T H H T Would that count as a success? That includes the string "H T" but is preceded by another head. Technically it meets the criteria but I suspect that wasn't what you meant... That's what I was thinking too, and i think that's the trick. All you need to flip is an "H T" string, nothing else matters. Which means all you need is H...HT or TH...HT. To calculate the expected value HT: 1/4*2 HHT: 1/8*3 THT: 1/8*3 HHHT: 1/16*4 THHT: 1/16*4 HHHHT: 1/32*5 THHHT: 1/32*5 =1/2+sum(n=3,inf)[1/2n-1*n), Which comes out to 2.5 expected flips. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 That's what I was thinking too, and i think that's the trick. All you need to flip is an "H T" string, nothing else matters. Which means all you need is H...HT or TH...HT. To calculate the expected value HT: 1/4*2 HHT: 1/8*3 THT: 1/8*3 HHHT: 1/16*4 THHT: 1/16*4 HHHHT: 1/32*5 THHHT: 1/32*5 =1/2+sum(n=3,inf)[1/2n-1*n), Which comes out to 2.5 expected flips. Too late to edit, but I clearly forgot about the T...TH...HT solutions, which changes the calculations. That's why I shouldn't do math this early in the morning. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Generally we will be in one of two conditions: A) We have just tossed an even run of heads, or a tail B) We have just tossed an odd run of heads A followed by head moves us to B B followed by head moves us to A A followed by tail keeps us on A B followed by tail finishes the sequence So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success, An=(An-1+Bn-1)/2 Bn=An-1/2 Sn=Bn-1/2 A0=1, A1=1/2, A2=1/2... B0=0, B1=1/2, B2=1/4... S0=0, S1=0, S2=1/4... Expected trials = sum {n>=1} (n*Sn) = S1+2*S2+C = 0.5+C, where C = sum {n>=3} (n*Sn) = sum (n*Bn-1)/2 = sum (n*An-2)/4 = sum (n*An-3+n*Bn-3))/8 = sum ((n+1)*An-2+(n+2)*Bn-1)/8 + (3*A0+3*B0+4*B1)/8 = sum (n*An-2+An-2+n*Bn-1+2Bn-1)/8 + 5/8 = C*1/4 + C*1/2 + sum(An-2) + 2*sum(Bn-1) + 5/8 C = 4*sum{n>2}(An-2) + 8*sum{n>2}(Bn-1) + 5/2 C = 4*sum{n>0}(An) + 8*sum{n>1}(Bn) + 5/2 sum(Sn) {n>2} = 1-S2 = 3/4 Bn-1=Sn*2, so sum(Bn) {n>1} = 3/2 An-1=Bn*2, so sum(An) {n>0} = 3 C = 4*3 + 8*3/2 + 2.5 = 26.5 So that would make expected trials 27 Only experimenting it in Excel gives me an answer of 6, which I think is more plausible So much for maths, I'll have to try and find my mistake... Oh, and if this is the easy way I don't want to know about the hard way Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Well I think that, on average, you have to toss the coin an infinite number of times to get the H followed by a T... Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted October 10, 2008 Author Report Share Posted October 10, 2008 Interpreting an odd number of H followed by a T: H H T T H H T H T 9 flips H T 2 flips T T T H H T H H H H T T T H H H T 17 flips H H H H H H H H H H H H H H H T 16 flips T T T T T T T T H T 10 flips T T H H T T H H T T H H T T H H T T H H H T 22 flips At the point that you've "won" you have a T. Preceding that is an odd number of H Preceding that is either a T or nothing [you started with an odd number of H] Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted October 10, 2008 Author Report Share Posted October 10, 2008 Generally we will be in one of two conditions: A) We have just tossed an even run of heads, or a tail B) We have just tossed an odd run of heads A followed by head moves us to B B followed by head moves us to A A followed by tail keeps us on A B followed by tail finishes the sequence So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success, An=(An-1+Bn-1)/2 Bn=An-1/2 Sn=Bn-1/2 A0=1, A1=1/2, A2=1/2... B0=0, B1=1/2, B2=1/4... S0=0, S1=0, S2=1/4... Expected trials = sum {n>=1} (n*Sn) = S1+2*S2+C = 0.5+C, where C = sum {n>=3} (n*Sn) = sum (n*Bn-1)/2 = sum (n*An-2)/4 = sum (n*An-3+n*Bn-3))/8 = sum ((n+1)*An-2+(n+2)*Bn-1)/8 + (3*A0+3*B0+4*B1)/8 = sum (n*An-2+An-2+n*Bn-1+2Bn-1)/8 + 5/8 = C*1/4 + C*1/2 + sum(An-2) + 2*sum(Bn-1) + 5/8 C = 4*sum{n>2}(An-2) + 8*sum{n>2}(Bn-1) + 5/2 C = 4*sum{n>0}(An) + 8*sum{n>1}(Bn) + 5/2 sum(Sn) {n>2} = 1-S2 = 3/4 Bn-1=Sn*2, so sum(Bn) {n>1} = 3/2 An-1=Bn*2, so sum(An) {n>0} = 3 C = 4*3 + 8*3/2 + 2.5 = 26.5 So that would make expected trials 27 Only experimenting it in Excel gives me an answer of 6, which I think is more plausible So much for maths, I'll have to try and find my mistake... Oh, and if this is the easy way I don't want to know about the hard way Impressive. Now lie down in a quiet place, put a cool washcloth on your forehead, and relax. No worry - that is not even close to the easy way. Or the hard way, for that matter. That is, there are [at least] two ways, one very quick, that are less cumbersome. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Interpreting an odd number of H followed by a T: H H T T H H T H T 9 flips H T 2 flips T T T H H T H H H H T T T H H H T 17 flips H H H H H H H H H H H H H H H T 16 flips T T T T T T T T H T 10 flips T T H H T T H H T T H H T T H H T T H H H T 22 flips At the point that you've "won" you have a T. Preceding that is an odd number of H Preceding that is either a T or nothing [you started with an odd number of H] Thank you for the clarification, but this is not what u've explained in ur post before! In this case, my answer, infinite numbers, doesn't stand anymore!!! Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Impressive. Now lie down in a quiet place, put a cool washcloth on your forehead, and relax. No worry - that is not even close to the easy way. Or the hard way, for that matter. That is, there are [at least] two ways, one very quick, that are less cumbersome. I think its either 2 or 3.. If yes then i can explain the logic behind it.. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 Generally we will be in one of two conditions: A) We have just tossed an even run of heads, or a tail B) We have just tossed an odd run of heads A followed by head moves us to B B followed by head moves us to A A followed by tail keeps us on A B followed by tail finishes the sequence So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success, An=(An-1+Bn-1)/2 Bn=An-1/2 Sn=Bn-1/2 A0=1, A1=1/2, A2=1/2... B0=0, B1=1/2, B2=1/4... S0=0, S1=0, S2=1/4... Expected trials = sum {n>=1} (n*Sn) = sum {n>=1} ((n-2+2)*Sn) = sum {n>=1} ((n-2)*Sn) + 2 * sum {n>=1} (Sn) = sum {n>=-1} (n*Sn+2) + 2 = sum {n>=1} (n*Sn+2) + 2 - S1 +0*S2 = C + 2, where C = sum {n>=1} (n*Sn+2) = sum (n*Bn+1)/2 = sum (n*An)/4 = sum (n*An-1+n*Bn-1)/8 = sum ((n+1)*An+(n+2)*Bn+1)/8 + (1*A0+1*B0+2*B1)/8 = sum (n*An+An+n*Bn+1+2Bn+1)/8 + (1+0+1)/8 = sum (n*An)/8 + sum(n*Bn+1)/8+ sum(An)/8 + sum(2Bn+1)/8 + ¼ = C/2 + C/4 +sum(An)/8 + sum(Bn+1)/4 + ¼ [multiply both sides by 4 and subtract 3*C] = sum(An/2) + sum(Bn+1) + 1 [use Bn = An-1/2] = 2*sum(Bn+1) + 1 [use Sn = Bn-1/2] = 4*(sum {n>=1} (Sn+2)) + 1 = 4*(sum {n>=1} (Sn) – (S1+S2)) + 1 = 4*(1 – ¼) + 1 = 4 Expected trials = C+2 = 6 Tell me that isn't the easy way!I'm going to stick my head in a bucket of ice now Quote Link to comment Share on other sites More sharing options...
0 Brandonb Posted October 10, 2008 Report Share Posted October 10, 2008 (edited) 25 times The most basic element of this, is that there must be an odd 'run' (suggesting at least 3 flips) on heads, and then a tails side. So it would take four tosses to complete the prerequisite. The odds of performing this particular action seems to be .5^4 (H, H, H, T) Yielding 0.0625 So, out of 100 4-toss runs, it would work about 16 times. Meaning that on average it would occur once in every 25 tosses. I'm probably way off. Edit: or it might be 6.25, and I took it a little too far. <_< but I'm leaning toward 25 Edited October 10, 2008 by Brandonb Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted October 10, 2008 Author Report Share Posted October 10, 2008 Thank you for the clarification, but this is not what u've explained in ur post before! In this case, my answer, infinite numbers, doesn't stand anymore!!! The blue H and T are the dots in the previous post - flips that didn't contribute to odd H plus T. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted October 10, 2008 Author Report Share Posted October 10, 2008 Generally we will be in one of two conditions: A) We have just tossed an even run of heads, or a tail B) We have just tossed an odd run of heads A followed by head moves us to B B followed by head moves us to A A followed by tail keeps us on A B followed by tail finishes the sequence So if An is probability of A on nth trial, Bn probability of B, and Sn probability of success, An=(An-1+Bn-1)/2 Bn=An-1/2 Sn=Bn-1/2 A0=1, A1=1/2, A2=1/2... B0=0, B1=1/2, B2=1/4... S0=0, S1=0, S2=1/4... Expected trials = sum {n>=1} (n*Sn) = sum {n>=1} ((n-2+2)*Sn) = sum {n>=1} ((n-2)*Sn) + 2 * sum {n>=1} (Sn) = sum {n>=-1} (n*Sn+2) + 2 = sum {n>=1} (n*Sn+2) + 2 - S1 + 0*S2 = C + 2, where C = sum {n>=1} (n*Sn+2) = sum (n*Bn+1)/2 = sum (n*An)/4 = sum (n*An-1+n*Bn-1)/8 = sum ((n+1)*An+(n+2)*Bn+1)/8 + (1*A0+1*B0+2*B1)/8 = sum (n*An+An+n*Bn+1+2Bn+1)/8 + (1+0+1)/8 = sum (n*An)/8 + sum(n*Bn+1)/8 + sum(An)/8 + sum(2Bn+1)/8 + ¼ = C/2 + C/4 + sum(An)/8 + sum(Bn+1)/4 + ¼ [multiply both sides by 4 and subtract 3*C] = sum(An/2) + sum(Bn+1) + 1 [use Bn = An-1/2] = 2*sum(Bn+1) + 1 [use Sn = Bn-1/2] = 4*(sum {n>=1} (Sn+2)) + 1 = 4*(sum {n>=1} (Sn) – (S1+S2)) + 1 = 4*(1 – ¼) + 1 = 4 Expected trials = C+2 = 6 Tell me that isn't the easy way!I'm going to stick my head in a bucket of ice now shooting a rabbit with an elephant gun, but Bugs is quite taken care of, nonetheless. Kudos. Now for something simpler. And disparagement of frequency analysis aside, those simulations do provide useful guidance don't they? Quote Link to comment Share on other sites More sharing options...
0 Prime Posted October 10, 2008 Report Share Posted October 10, 2008 (edited) I thought we laid quite a bit of groundwork in previous like-topics. I'll designate head as 0 and tail as 1. Let's call the average number of tosses we seek -- x. 1) 00 -- this has a probability of 1/4, two tosses and we are back where we started. Thus 1/4(2+x) 2) 01 -- probability 1/4 and we are done in just two tosses. 1/4*2 3) 100 -- probability 1/8, 3 tosses, same position as from the start. 1/8(3+x) 4) 101 -- probability 1/8, 3 tosses, done. 1/8*3 5) 11 -- probability 1/4, 2 tosses, starting position. 1/4(2+x) Adding them all up we get: x = 1/2 + x/4 + 1/2 + 3/8 + x/8 + 3/8 + 1/2 + x/4 Solving, we find x = 6 Using geometric series to solve is straight forward enough too. There we get probability of the required sequence is 1/3 and its average length is 8/3, whereas probability of other sequences is 2/3 and their average length 5/3. Calculating 2*5/3 + 8/3 = 6. Same result, I don't show the actual series here as we have discussed them at other topics. Edited October 10, 2008 by Prime Quote Link to comment Share on other sites More sharing options...
0 Prime Posted October 10, 2008 Report Share Posted October 10, 2008 Or even simpler, yet: If we tossed tails on the first try, we are at the starting position again, the averaage in that case is 1/2*(x+1). When heads, we have probability 1/2 to finish on the next toss: 1/2*1/2*2, or get back to starting position: 1/2*1/2*(2+x). Thus x = x/2 + 1/2 + 1/2 +1/2 + x/4 --> x = 6 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 10, 2008 Report Share Posted October 10, 2008 6 is exactly right. I wonder what's the long way of solving. Once I got it easy way there's no stimulus looking for long one. Quote Link to comment Share on other sites More sharing options...
Question
bonanova
Here's a simple question about probability and expectation.
On average, how many times do you need to flip a fair coin
before you have seen a run of an odd number of heads,
followed by a tail?
This puzzle was submitted, but not used, in the International
Mathematical Olympiad twenty-five years ago. What makes it
appealing for use as a test question [where time can be of the
essence] is that it has an easy answer as well as a difficult answer.
That is it tests for insight.
As such it qualifies as a puzzle as well as a math question.
Extra bragging rights go to the solver who solves it both ways.
Link to comment
Share on other sites
35 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.