Expected Number of Tosses of a Fair Coin
Thread Rating:
January 15th, 2019 at 2:25:41 PM
permalink
What is the expected number of tosses of a fair coin to get 1. HT, and 2. HH? In this context "expected" means "average." The expected number of flips to get a H is 2, since H will come up an average of n times in 2n flips. There is a general rule that the average number of times an event with a probability of p will come up is 1/p, but this problem demonstrates that this rule does not necessarily apply to sequences.
The answers to 1 and 2 are not the same.
The answers to 1 and 2 are not the same.
"I am not concerned that someone does not know of me; I am concerned that I do not know of him" - Confucius
January 15th, 2019 at 4:58:46 PM
permalink
That was Quick!
When a rock is thrown into a pack of dogs, the one that yells the loudest is the one who got hit.
January 15th, 2019 at 5:35:36 PM
permalink
Quote: DeMangoThat was Quick!
Sock.
If the House lost every hand, they wouldn't deal the game.
January 15th, 2019 at 6:53:08 PM
permalink
#1 is 4; #2 is 6
For HT, this is (zero or more Ts) followed by an H followed by (zero or more Hs) followed by a T
The expected number of tosses to get zero or more Ts followed by an H is:
1 x 1/2 + 2 x 1/4 + 3 x 1/8 + ...
= 1/2 x (1 + 2 x 1/2 + 3 x 1/4 + ...)
= 1/2 x (1 + 1/2 + 1/4 + 1/8 + ...)2
= 1/2 x 22 = 2
The expected number of tosses to get zero or more Hs followed by a T is the same.
Thus, the total = 2 + 2 + 4
HH is an entirely different problem:
Let (H) represent 0 or more Ts followed by an H; as already shown in the HT problem, this is 2 expected tosses
The possibilities are:
(H)H: 1/2 x 3
(H)T(H)H: 1/4 x 6
(H)T(H)T(H)H: 1/8 x 9
and so on
The sum is 3/2 (1 + 2 x 1/2 + 3 x 1/4 + ...) = 3/2 x 22 = 6
January 15th, 2019 at 11:58:27 PM
permalink
1/p is derived in the same way that a formula for a sequence would be. 1/p isn’t applicable for the latter because it’s a different scenario...the goal can not be achieved at every step with a probability p since you must also consider the state you’re in before each iteration.Quote: shoshoneThere is a general rule that the average number of times an event with a probability of p will come up is 1/p, but this problem demonstrates that this rule does not necessarily apply to sequences..
The formula for x consecutive heads is 2^(x+1) - 2. So, for example, it will take an avg of 62 toses to get 5 consecutive heads.
Calculating the median is another story. For binary events it’s very simple but for consecutive/multiple-state scenarios there is no way to calculate the median that I know of. You can only extrapolate an approximate value via a Markov chain.
Last edited by: Ace2 on Jan 16, 2019
It’s all about making that GTA
January 16th, 2019 at 5:33:45 PM
permalink
the general rule has to do with independent events.Quote: shoshoneThere is a general rule that the average number of times an event with a probability of p will come up is 1/p,
I see the patterns H and HH as way different.
The HH pattern MUST have a H to start. That makes it dependant.
if p=1/2 for an H we can easily say 1/p = the average number of flips to get an H = 2
T = 1-p
HH = p^-2 = 4 PLUS p^-1 = 2
(4+2)=6. There is overlap in the pattern (sequence) and we can easily calculate that event (those events)
this was (first ?) talked about by a famous math guy (John Conway) but can also be seen in a simple Markov chain transition matrix.
HT has NO overlap
p^-1*q^-1 = 4
Here is a link to a spreadsheet that shows average number of trials for any value of p
for a 2 to 6 word sequence (pattern) I think I got all the errors out of it.
https://sites.google.com/view/krapstuff/sequences
the overlap concept (in patterns) for many is difficult to grasp
but can be seen here in this example
HHHTTT = p^-3*q^-3 = 64 (2^6)
HHTTHH= p^-3*q^-3 PLUS p^-2 PLUS p^-1 = 2^6+2^2+2^1=70
| 1 | H | H | T | T | H | H |
|---|---|---|---|---|---|---|
| 5 | 0 | H | H | T | T | H |
| 4 | 0 | H | H | T | T | |
| 3 | 0 | H | H | T | ||
| 2 | 1 | H | H | |||
| 1 | 1 | H |
HHTTHH
x HHTTH <- not a match with the basic pattern starting at 2nd flip
xx HHTT<- not a match with the basic pattern starting at 3rd flip
xxx HHT <- not a match with the basic pattern starting at 4th flip
xxxx HH <- matches the basic pattern starting at 5th flip
xxxxx H <- matches the basic pattern starting at 6th flip
the worksheet I linked to has a sheet that shows this as well
this is way different from a 'race' between 2 patterns or more
that is a game that just is not that intuitive at first sight (Penney Ante game)
"Flipping a coin results in either an “H” or a “T”; a sequence of consecutive flips is thereby represented by a word. A collection of active words is given, and a coin is flipped to see which word from the list is the first to appear in the list of results. This game was published as Problem 95 by Walter Penney in the Journal of Recreational Mathematics (1969)."
time to move on
this is also easily simulated
Pattern: HH
grouped data
items: 1000000
minimum value: 2.00
first quartile: 2.00
median: 5.00
third quartile: 8.00
maximum value: 67.00
mean value: 6.00
midrange: 34.50
range: 65.00
interquartile range: 6.00
mean abs deviation: 3.44
sample variance (n): 22.05
sample variance (n-1): 22.05
sample std dev (n): 4.70
sample std dev (n-1): 4.70
Pattern: HT
grouped data
items: 1000000
minimum value: 2.00
first quartile: 2.00
median: 3.00
third quartile: 5.00
maximum value: 25.00
mean value: 4.00
midrange: 13.50
range: 23.00
interquartile range: 3.00
mean abs deviation: 1.50
sample variance (n): 3.99
sample variance (n-1): 3.99
sample std dev (n): 2.00
sample std dev (n-1): 2.00
Last edited by: 7craps on Jan 16, 2019
winsome johnny (not Win some johnny)
January 17th, 2019 at 9:23:25 AM
permalink
A very significant problem with an unexpectedly complicated solution!
I have visited this site many times but have never made a post. I just
had to jump in on this one.
ThatDonGuy's solution is correct but I am having trouble following his reasoning.
I think he is using an infinite series. If he used more words to explain what he is doing it would help with understanding. Presh Talwalkar has a YouTube video on this problem with yet another solution. This would be my entry in a contest for a solution that would be easiest to understand.
Case 1: goal is HT
Let e be the expected (average) number of flips to achieve the goal.
1a. First flip T: this is useless, so e is increased by one.
1b. First flip H: we are half way there.
1ba. The next flip is T and we have attained our goal in two flips with a probability 1/4.
1bb. The next flip is a H. We are at HH and can attain our goal in one more flip. That would be a T and the average number of flips to get a T is 2. In this case we expect to attain our goal in an average of 4 flips.
Adding up these three contingencies weighted by their probabilities:
e = (1/2)(e + 1) + (1/4)(4) + (1/4)(2)
Solving for e, e = 4
Case 2: goal is HH
2a. First flip T: this is useless, so e is increased by one.
2b. First flip is H: we are half way there waiting for the next flip.
2ba. Next flip is H. We have attained our goal in two flips with a probability of 1/4.
2bb. Next flip is a T. We are back to square one and cannot complete our goal in fewer than two additional flips. In this case the expected number of flips is e + 2 with a probability of 1/4
Adding up these three contingencies weighted by their probabilities:
e = (1/2)(e + 1) + (1/4)(e + 2) + (1/4)(2)
Solving for e, e = 6.
I have visited this site many times but have never made a post. I just
had to jump in on this one.
ThatDonGuy's solution is correct but I am having trouble following his reasoning.
I think he is using an infinite series. If he used more words to explain what he is doing it would help with understanding. Presh Talwalkar has a YouTube video on this problem with yet another solution. This would be my entry in a contest for a solution that would be easiest to understand.
Case 1: goal is HT
Let e be the expected (average) number of flips to achieve the goal.
1a. First flip T: this is useless, so e is increased by one.
1b. First flip H: we are half way there.
1ba. The next flip is T and we have attained our goal in two flips with a probability 1/4.
1bb. The next flip is a H. We are at HH and can attain our goal in one more flip. That would be a T and the average number of flips to get a T is 2. In this case we expect to attain our goal in an average of 4 flips.
Adding up these three contingencies weighted by their probabilities:
e = (1/2)(e + 1) + (1/4)(4) + (1/4)(2)
Solving for e, e = 4
Case 2: goal is HH
2a. First flip T: this is useless, so e is increased by one.
2b. First flip is H: we are half way there waiting for the next flip.
2ba. Next flip is H. We have attained our goal in two flips with a probability of 1/4.
2bb. Next flip is a T. We are back to square one and cannot complete our goal in fewer than two additional flips. In this case the expected number of flips is e + 2 with a probability of 1/4
Adding up these three contingencies weighted by their probabilities:
e = (1/2)(e + 1) + (1/4)(e + 2) + (1/4)(2)
Solving for e, e = 6.
OnceDear is a Dear!
January 17th, 2019 at 9:54:23 AM
permalink
exactly, when needing a proof with math also most anything can be complicated to someone.Quote: netzerA very significant problem with an unexpectedly complicated solution!
HH and HT is way too easy (unless one changes the value of p away from 1/2)
try this one
p=1/2 (fair coin)
HHHHHH
and
HHHHHT
This is so easy using the overlap method (can be done in ones' head very quickly)
one can 'see' how different states figure into the averages using a Markov chain solution
now many will NOT believe the mean wait time (keep flipping until the pattern is complete) for each of those 6 flip patterns
the mean wait time for HHHHHT is 2^6 - no overlap in the sequence = 64 flips
the mean wait time for HHHHHH is 2^6+2^5+2^4+2^3+2^2+2^1 - overlaps at every flip = 126
of course this 'run' has a simpler formula of 2^(r+1)-2
the mean wait time for HHHHHH is 2^6+2^5+2^4+2^3+2^2+2^1 - overlaps at every flip = 126
of course this 'run' has a simpler formula of 2^(r+1)-2
so there it is
enjoy
winsome johnny (not Win some johnny)
January 17th, 2019 at 12:25:43 PM
permalink
Quote: 7crapsexactly, when needing a proof with math also most anything can be complicated to someone.
HH and HT is way too easy (unless one changes the value of p away from 1/2)
I suppose you mean that it is complicated to me but not to you.
I studied your solution but did not acknowledge it because I thought it veered off the point. ThatDonGuy's solution is directly to the point but too concise for easy understanding. If you understand it could you explain it to me in detail?
I encourage you to look up Presh Talwalkar's solution on YouTube. He is one of the Internet's top mathematicians and can handle just about anything.
OnceDear is a Dear!
January 17th, 2019 at 2:33:18 PM
permalink
actually the other way around.Quote: netzerI suppose you mean that it is complicated to me but not to you.
I understood what Don did, but after reading it, it came to an end.
I use others' solutions as mentioned.
actually was not my solution. just what I use as a different way to get an answer.Quote: netzerI studied your solution but did not acknowledge it because I thought it veered off the point.
my perfered method for these type Qs is to use a Markov chain solution.
It is basic math and gives lots of info, more than just x
and, to me, they are fun to do, sometimes
HT
HH
I also realize, the vast majority is lost with how I solved the HT or HH question.
There may not be enough time to explain so all gets it either.
I could show a diagram of the transition matrix and some will get it.
It can't hurt. sure, it might bring up more questions.
(using R package 'markovchain')
HT
HH
one can see why HH is longer than HT because a T forces the system to go all the way back to 0
that is why I mentioned HHHHHH and HHHHHT and would like to see Don solve it his way.
I have the basic idea how he does it, but am really left as did he really prove it to many that the answer is correct.
He is very good at explanations of what he does, but still, many will not be able to follow, so they take it on faith.
there are many like him, without listing them all.Quote: netzerI encourage you to look up Presh Talwalkar's solution on YouTube. He is one of the Internet's top mathematicians and can handle just about anything.
some use extreme heavy artillery to show a solution and a mathematical proof. That is fine for some but many get lost in that and are left holding the bag, so to speak and unable to work out another problem, say HHHHT and HHHHH.
I thought the OP question was going to lead down another path
but now I see the OP is restricted, for some reason.
enjoy
Last edited by: 7craps on Jan 17, 2019
winsome johnny (not Win some johnny)
January 18th, 2019 at 11:56:54 AM
permalink
for those so interested, now or in the future visits
try this
(p(H) and p(T) = 1/2)
a) HHH
and
b) TTHH
1) the average number of flips to get each pattern (the wait game)
who wins? (the shorter wait time wins)
2)Now, try the 'race game'. keep flipping until one pattern wins. Some math guys call this a 'horse race'
"Naively, one would expect that this relation is transitive, but this
is not true! "
I have to agree.
the race game is where John Conway's' algorithm comes in real handy to calculate winning probabilities.
I still use a Markov chain.
time to grow up and out and expand the mind!
enjoy
try this
(p(H) and p(T) = 1/2)
a) HHH
and
b) TTHH
1) the average number of flips to get each pattern (the wait game)
who wins? (the shorter wait time wins)
I get HHH = 2^3+2^2+2^1 = 14
TTHH = 2^4 = 16
so HHH wins the 'wait game'
TTHH = 2^4 = 16
so HHH wins the 'wait game'
2)Now, try the 'race game'. keep flipping until one pattern wins. Some math guys call this a 'horse race'
I get HHH = 5/12 probability of winning
TTHH = 7/12 probability of winning
so TTHH wins the 'horse race'
TTHH = 7/12 probability of winning
so TTHH wins the 'horse race'
"Naively, one would expect that this relation is transitive, but this
is not true! "
I have to agree.
the race game is where John Conway's' algorithm comes in real handy to calculate winning probabilities.
I still use a Markov chain.
time to grow up and out and expand the mind!
enjoy
Last edited by: 7craps on Jan 18, 2019
winsome johnny (not Win some johnny)
January 18th, 2019 at 1:10:57 PM
permalink
Quote: Ace2
The formula for x consecutive heads is 2^(x+1) - 2. So, for example, it will take an avg of 62 toses to get 5 consecutive heads.
I found the formula 2(2^n - 1) at Stackexchange (URL link does not work).
This is algebraically equivalent but in a slightly different form. Did you find yours somewhere else or did you derive it yourself?
7craps is going ape over this. What do you think of his sequences?
This thread is getting a lot of votes. I guess that's hurray for us!
OnceDear is a Dear!
January 19th, 2019 at 11:55:56 AM
permalink
I agree. well said. LOLQuote: netzer7craps is going ape over this.
I find this topic very interesting.
The Original Post (with a pattern wait time)
directly leads to the Penney-Ante game that is a 'race' between 2 patterns (words), originally a race between 2 patterns of the same length and how information that player 2 has from player 1 selecting the 1st pattern gives player 2 a large probability of winning the race.
I find a race between different lengths of a pattern (words) even more interesting but have only a Markov chain solution for the winning probabilities and the mean time to the end of a game.
I think I will look into this more.
example: (another one)
TT vs. HHT
wait time I get is 6 vs 8
so TT wins the wait time game (feels right)
in a race between TT and HHT
I think intuition might just be right as many times it is not in a race.
I do know the mean length a the race = 4.
I get a tie! 50-50 when p(T) and p(H) = 1/2
how about TT vs HTH?
this should be easier
any that find this interesting
enjoy
any that find this not so interesting
enjoy
moving on
winsome johnny (not Win some johnny)
January 19th, 2019 at 6:46:31 PM
permalink
Can you explain what a “race” is? I’m confused how HH and TTH can could lead to a tie expected. I would think that TT and HH would tie, and adding H to the end of TT would make it a “slower” racer. So I’m going to conclude I don’t understand what the “race” game is.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 20th, 2019 at 12:14:42 AM
permalink
This can be easily calculated.Quote: 7crapsfor those so interested, now or in the future visits
try this
(p(H) and p(T) = 1/2)
a) HHH
and
b) TTHH
2)Now, try the 'race game'. keep flipping until one pattern wins. Some math guys call this a 'horse race
I get HHH = 5/12 probability of winning
TTHH = 7/12 probability of winning
so TTHH wins the 'horse race'
the race game is where John Conway's' algorithm comes in real handy to calculate winning probabilities.
I still use a Markov chain.
To determine who wins, start flipping and record the results. Find the first sequence of THH, then look back one flip. If it’s at T (1/2 chance) then “b” wins, if it’s not T and if the next flip is H (1/2 * 1/2 = 1/4 chance) then “a” wins. If neither wins, continue to next sequence until someone does.
This would give “b” a (1/2) / (1/2 + 1/4) = 2/3 chance of winning. This algorithm is valid except for when the first three flips are HHH (1/8 chance) when “a” wins before the algorithm can be applied. Otherwise (7/8 chance) it works.
So “b” wins with a probability 7/8 * 2/3 = 7/12.
It’s all about making that GTA
January 20th, 2019 at 8:07:37 AM
permalink
a fair coin, in this case, is flipped until one of the words (patterns) completely shows up. the game ends.Quote: unJonCan you explain what a “race” is? I’m confused how HH and TTH can could lead to a tie expected. I would think that TT and HH would tie, and adding H to the end of TT would make it a “slower” racer. So I’m going to conclude I don’t understand what the “race” game is.
one math guy says: The Penney-Ante Game (a race game)
"Flipping a coin results in either an “H” or a “T”;
a sequence of consecutive flips is thereby represented by a word. A collection of active words is given, and a coin is flipped to see which word from the list is the first to appear in the list of results."
another says this:
"Assume a coin flip with equal probability of coming up heads or tails. The
game is played by Players A and B each selecting a sequence of three flips, (the example in the pdf)
flipping the coin repeatedly, and seeing whose sequence comes up first."
You are correct that in the 2 letter words (TT,HH) they would tie in a race between 2 players.
a closer look should reveal that the game ends at TT
and when HH is reached, TT can not win. some call that a 'clinch state'
TT is the dark circle on the lower right.
that makes it actually a 'race' of getting to TT or HH first
50% happening for each player.
some can look at a couple patterns and know the race will be close or one will dominate and it may NOT be the same as the 'wait game' where how many flips on average does it take to get HH. TTH. (FCP or Flipping Coin Problem)
I have to run a Markov chain to get a 2 player race results.
same with more than 2 players.
I am slow that way.
hope that helps some
Last edited by: 7craps on Jan 20, 2019
winsome johnny (not Win some johnny)
January 20th, 2019 at 10:00:19 AM
permalink
Quote: 7crapsa fair coin, in this case, is flipped until one of the words (patterns) completely shows up. the game ends.
one math guy says: The Penney-Ante Game (a race game)
"Flipping a coin results in either an “H” or a “T”;
a sequence of consecutive flips is thereby represented by a word. A collection of active words is given, and a coin is flipped to see which word from the list is the first to appear in the list of results."
another says this:
"Assume a coin flip with equal probability of coming up heads or tails. The
game is played by Players A and B each selecting a sequence of three flips, (the example in the pdf)
flipping the coin repeatedly, and seeing whose sequence comes up first."
You are correct that in the 2 letter words (TT,HH) they would tie in a race between 2 players.
a closer look should reveal that the game ends at TT
and when HH is reached, TT can not win. some call that a 'clinch state'
TT is the dark circle on the lower right.
that makes it actually a 'race' of getting to TT or HH first
50% happening for each player.
some can look at a couple patterns and know the race will be close or one will dominate and it may NOT be the same as the 'wait game' where how many flips on average does it take to get HH. TTH. (FCP or Flipping Coin Problem)
I have to run a Markov chain to get a 2 player race results.
same with more than 2 players.
I am slow that way.
hope that helps some
Bolded mine. Ah, of course. I see now. Thank you.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 20th, 2019 at 4:56:14 PM
permalink
I only saw that after I simmed it not really believing the calculated results.Quote: unJonAh, of course. I see now. Thank you.
> print(pAwin)
[1] 500017
> print(pBwin)
[1] 499983
> print(pAwin/sims)
[1] 0.500017
> print(pBwin/sims)
[1] 0.499983
> print(pA.seq)
[1] 0 0
> print(pB.seq)
[1] 1 1 0
> print(flips)
[1] 3997860
> print(flips/sims)
[1] 3.99786
of course, it now makes sense
these PAG races sure can play with your mind
now I want to find how to calculate (without a Markov chain)
the expected length of a race.
not that it matters
winsome johnny (not Win some johnny)
January 23rd, 2019 at 12:14:26 PM
permalink
Somebody was lamenting in the Discussion of the Suspension List thread that I killed this thread by nuking the OP, for which I make no apologies. It looks like many of you already have arrived at the answer, but if anyone still doesn't get it, I'll try to help. That said, here is how I would explain the answers:
H-H Case
Let x = expected flips from the beginning or after a T.
Let y = expected flips from the state after a heads.
There are only three possible states -- x, y, and having achieved H-H. Each state leads to another state or back to itself. We can set up these equations as follows:
x = 1 + pr(H)*y + pr(T)*x
x = 1 + y/2 + x/2
x/2 = 1 + y/2
(1) x = 2 + y
y = 1 + pr(H) + pr(T)
y = 1 + 0/2 + y/2
2y = 2 + y
y = 2
Putting y=2 into equation (1):
x = 2 + 2 = 4
So, it will take, on average, 4 flips to get to a H-H sequence.
H-T Case
Let x = expected flips from the beginning or after a T.
Let y = expected flips from the state after a heads.
x = 1 + pr(H)*y + pr(T)*x
x = 1 + y/2 + x/2
x/2 = 1 + y/2
(1) x = 2 + y
y = 1 + pr(H) + pr(T)*0
y = 1 + 0/2 + x/2
2y = 2 + x
(2) y = 1 + x/2
Putting equation (2) into equation (1):
x = 2 + 1 + x/2
2x = 6 + x
x = 6
So, it will take, on average, 6 flips to get to a H-T sequence.
In plain simple English, the reason it is less for H-H, is that after you get a H, you can't go backwards. Any further flips either leads to a success or the same state.
In contrast, for H-T, after you get the first H, if that is followed by a T, you have to go back to the initial state, erasing all progress.
H-H Case
Let x = expected flips from the beginning or after a T.
Let y = expected flips from the state after a heads.
There are only three possible states -- x, y, and having achieved H-H. Each state leads to another state or back to itself. We can set up these equations as follows:
x = 1 + pr(H)*y + pr(T)*x
x = 1 + y/2 + x/2
x/2 = 1 + y/2
(1) x = 2 + y
y = 1 + pr(H) + pr(T)
y = 1 + 0/2 + y/2
2y = 2 + y
y = 2
Putting y=2 into equation (1):
x = 2 + 2 = 4
So, it will take, on average, 4 flips to get to a H-H sequence.
H-T Case
Let x = expected flips from the beginning or after a T.
Let y = expected flips from the state after a heads.
x = 1 + pr(H)*y + pr(T)*x
x = 1 + y/2 + x/2
x/2 = 1 + y/2
(1) x = 2 + y
y = 1 + pr(H) + pr(T)*0
y = 1 + 0/2 + x/2
2y = 2 + x
(2) y = 1 + x/2
Putting equation (2) into equation (1):
x = 2 + 1 + x/2
2x = 6 + x
x = 6
So, it will take, on average, 6 flips to get to a H-T sequence.
In plain simple English, the reason it is less for H-H, is that after you get a H, you can't go backwards. Any further flips either leads to a success or the same state.
In contrast, for H-T, after you get the first H, if that is followed by a T, you have to go back to the initial state, erasing all progress.
Last edited by: Wizard on Jan 23, 2019
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 23rd, 2019 at 1:12:37 PM
permalink
agree on your conclusions.Quote: WizardIn plain simple English, the reason it is less for H-T, is that after you get a H, you can't go backwards. Any further flips either leads to a success or the same state.
In contrast, for H-H, after you get the first H, if that is followed by a T, you have to go back to the initial state, erasing all progress.
your math approach would get tiresome, imo, for larger patterns than just length 2 unless you had some computer code do it for you or you used a different method other than simulation.
John Conway's concept of leading numbers and his algorithm for using them
to automatically calculate mutual odds of winning a PAG 'race' (not the OP question)
can also be used on just ONE pattern to arrive at the 'average wait time'. It is because it takes into consideration the overlap in the pattern itself. (and only works when p(H) & p(T) = 1/2)
HTTTH (fair coin)
I see the 'mean wait time' = 2^5+2^1
JC method turns HTTTH in binary 1st =10001 then back to decimal = 17
simply multiply by 2 for the MWT = 34
even longer patterns are easier
HHHTHTTHH (a 9tuple)
I see the mean wait time = 2^9+2^2+2^1
JC binary=100000011= (left to the reader)
100000011=259 in decimal=a
a*2=518
a*2=518
still some will disagree
and that is fine
winsome johnny (not Win some johnny)
January 23rd, 2019 at 2:38:00 PM
permalink
Quote: 7crapsJohn Conway's concept ...
Very interesting. I do not dispute that it works, but don't immediately see why.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 23rd, 2019 at 2:52:59 PM
permalink
Quote: WizardSomebody was lamenting in the Discussion of the Suspension List thread that I killed this thread by nuking the OP, for which I make no apologies. It looks like many of you already have arrived at the answer, but if anyone still doesn't get it, I'll try to help. That said, here is how I would explain the answers:
H-H Case
Let x = expected flips from the beginning or after a T.
Let y = expected flips from the state after a heads.
There are only three possible states -- x, y, and having achieved H-H. Each state leads to another state or back to itself. We can set up these equations as follows:
x = 1 + pr(H)*y + pr(T)*x
x = 1 + y/2 + x/2
x/2 = 1 + y/2
(1) x = 2 + y
y = 1 + pr(H) + pr(T)
y = 1 + 0/2 + y/2
2y = 2 + y
y = 2
Putting y=2 into equation (1):
x = 2 + 2 = 4
So, it will take, on average, 4 flips to get to a H-H sequence.
H-T Case
Let x = expected flips from the beginning or after a T.
Let y = expected flips from the state after a heads.
x = 1 + pr(H)*y + pr(T)*x
x = 1 + y/2 + x/2
x/2 = 1 + y/2
(1) x = 2 + y
y = 1 + pr(H) + pr(T)*0
y = 1 + 0/2 + x/2
2y = 2 + x
(2) y = 1 + x/2
Putting equation (2) into equation (1):
x = 2 + 1 + x/2
2x = 6 + x
x = 6
So, it will take, on average, 6 flips to get to a H-T sequence.
In plain simple English, the reason it is less for H-T, is that after you get a H, you can't go backwards. Any further flips either leads to a success or the same state.
In contrast, for H-H, after you get the first H, if that is followed by a T, you have to go back to the initial state, erasing all progress.
I think your labeling is off. The HH case should be 6 not 4. And the HT case should be 4 not 6.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 23rd, 2019 at 3:59:43 PM
permalink
Quote: unJonI think your labeling is off. The HH case should be 6 not 4. And the HT case should be 4 not 6.
You're right; thanks. My math was right, just the conclusion at the end I got confused.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 23rd, 2019 at 5:27:28 PM
permalink
Quote: WizardVery interesting. I do not dispute that it works, but don't immediately see why.
To calculate the waiting time of any consecutive string of x “wins” when the probability of a win is 1/y there’s a basic formula of: y^x + y^(x-1) + y^(x-2) ...+y^1.
So if you’re throwing a single die and want to know the average number of rolls to get 4 consecutive 1s the calculation is : 6^4 + 6^3 + 6^2 + 6^1 = 1,554.
This also happens to be the way you would do a conversion of the number 11110 from base 6 to base 10 which is 1,554.
However, when analyzing strings that contain more than one “win” value, like the specific string TTHH, I think this coincidence is only valid when the probability is 1/2 ie coin flip.
It’s all about making that GTA
January 23rd, 2019 at 8:23:01 PM
permalink
using the Markov chain approach one can use simple recursion in a spreadsheet to get the actual distributionQuote: Ace2Calculating the median is another story. For binary events it’s very simple but for consecutive/multiple-state scenarios there is no way to calculate the median that I know of.
You can only extrapolate an approximate value via a Markov chain.
and from that get what the mean, median and mode is for a particular pattern.
actually an interesting view in Excel
(and Google sheets - requires a few seconds to display the chart)
for HT (TH)
https://goo.gl/o3wy1d
for HH (TT)
https://goo.gl/DTPHPM
The OP was about HT and HH (could be TH and TT)
fair coin flips
HT (or TH)
mean: 4
median: 3
mode: 2&3
HH (or TT)
mean: 6
median: 4
mode: 2
winsome johnny (not Win some johnny)
January 23rd, 2019 at 8:48:56 PM
permalink
To see the first occurrence of HHHH will take an average of 2^(4+1) - 2 = 30 flips. What’s the median number of flips?Quote: 7crapsusing the Markov chain approach one can use simple recursion in a spreadsheet to get the actual distribution
and from that get what the mean, median and mode is for a particular pattern.
It’s all about making that GTA
January 23rd, 2019 at 10:21:57 PM
permalink
agreeQuote: Ace2To see the first occurrence of HHHH will take an average of 2^(4+1) - 2 = 30 flips.
2^4+2^3+2^2+2^1 = 16+8+4+2 = 16+14=30
the mode is 4
looks to be at 22Quote: Ace2What’s the median number of flips?
from a run program (column 5)
x prob[X=x] prob[X<x] prob[X>=x] prob[X<=x] prob[X>x]
4 0.06250 0.00000 1.00000 0.06250 0.93750
5 0.03125 0.06250 0.93750 0.09375 0.90625
6 0.03125 0.09375 0.90625 0.12500 0.87500
7 0.03125 0.12500 0.87500 0.15625 0.84375
8 0.03125 0.15625 0.84375 0.18750 0.81250
9 0.02930 0.18750 0.81250 0.21680 0.78320
10 0.02832 0.21680 0.78320 0.24512 0.75488
11 0.02734 0.24512 0.75488 0.27246 0.72754
12 0.02637 0.27246 0.72754 0.29883 0.70117
13 0.02539 0.29883 0.70117 0.32422 0.67578
14 0.02448 0.32422 0.67578 0.34869 0.65131
15 0.02359 0.34869 0.65131 0.37228 0.62772
16 0.02274 0.37228 0.62772 0.39502 0.60498
17 0.02191 0.39502 0.60498 0.41693 0.58307
18 0.02112 0.41693 0.58307 0.43805 0.56195
19 0.02035 0.43805 0.56195 0.45840 0.54160
20 0.01962 0.45840 0.54160 0.47802 0.52198
21 0.01891 0.47802 0.52198 0.49692 0.50308
22 0.01822 0.49692 0.50308 0.51515 0.48485
23 0.01756 0.51515 0.48485 0.53271 0.46729
24 0.01692 0.53271 0.46729 0.54963 0.45037
25 0.01631 0.54963 0.45037 0.56594 0.43406
26 0.01572 0.56594 0.43406 0.58166 0.41834
27 0.01515 0.58166 0.41834 0.59682 0.40318
28 0.01460 0.59682 0.40318 0.61142 0.38858
29 0.01407 0.61142 0.38858 0.62549 0.37451
30 0.01356 0.62549 0.37451 0.63906 0.36094
31 0.01307 0.63906 0.36094 0.65213 0.34787
32 0.01260 0.65213 0.34787 0.66473 0.33527
33 0.01214 0.66473 0.33527 0.67687 0.32313
34 0.01170 0.67687 0.32313 0.68858 0.31142
35 0.01128 0.68858 0.31142 0.69986 0.30014
36 0.01087 0.69986 0.30014 0.71073 0.28927
37 0.01048 0.71073 0.28927 0.72120 0.27880
38 0.01010 0.72120 0.27880 0.73130 0.26870
39 0.00973 0.73130 0.26870 0.74103 0.25897
40 0.00938 0.74103 0.25897 0.75041 0.24959
41 0.00904 0.75041 0.24959 0.75945 0.24055
42 0.00871 0.75945 0.24055 0.76817 0.23183
43 0.00840 0.76817 0.23183 0.77656 0.22344
44 0.00809 0.77656 0.22344 0.78465 0.21535
45 0.00780 0.78465 0.21535 0.79245 0.20755
46 0.00752 0.79245 0.20755 0.79997 0.20003
47 0.00724 0.79997 0.20003 0.80722 0.19278
48 0.00698 0.80722 0.19278 0.81420 0.18580
49 0.00673 0.81420 0.18580 0.82093 0.17907
50 0.00649 0.82093 0.17907 0.82741 0.17259
51 0.00625 0.82741 0.17259 0.83366 0.16634
52 0.00602 0.83366 0.16634 0.83969 0.16031
53 0.00581 0.83969 0.16031 0.84550 0.15450
54 0.00560 0.84550 0.15450 0.85109 0.14891
55 0.00539 0.85109 0.14891 0.85648 0.14352
56 0.00520 0.85648 0.14352 0.86168 0.13832
57 0.00501 0.86168 0.13832 0.86669 0.13331
58 0.00483 0.86669 0.13331 0.87152 0.12848
59 0.00465 0.87152 0.12848 0.87617 0.12383
60 0.00448 0.87617 0.12383 0.88066 0.11934
61 0.00432 0.88066 0.11934 0.88498 0.11502
62 0.00417 0.88498 0.11502 0.88915 0.11085
63 0.00401 0.88915 0.11085 0.89316 0.10684
64 0.00387 0.89316 0.10684 0.89703 0.10297
65 0.00373 0.89703 0.10297 0.90076 0.09924
66 0.00359 0.90076 0.09924 0.90436 0.09564
67 0.00346 0.90436 0.09564 0.90782 0.09218
68 0.00334 0.90782 0.09218 0.91116 0.08884
69 0.00322 0.91116 0.08884 0.91438 0.08562
70 0.00310 0.91438 0.08562 0.91748 0.08252
71 0.00299 0.91748 0.08252 0.92047 0.07953
72 0.00288 0.92047 0.07953 0.92335 0.07665
73 0.00278 0.92335 0.07665 0.92612 0.07388
74 0.00268 0.92612 0.07388 0.92880 0.07120
75 0.00258 0.92880 0.07120 0.93138 0.06862
76 0.00249 0.93138 0.06862 0.93386 0.06614
77 0.00240 0.93386 0.06614 0.93626 0.06374
78 0.00231 0.93626 0.06374 0.93857 0.06143
79 0.00223 0.93857 0.06143 0.94079 0.05921
80 0.00214 0.94079 0.05921 0.94294 0.05706
81 0.00207 0.94294 0.05706 0.94500 0.05500
82 0.00199 0.94500 0.05500 0.94700 0.05300
83 0.00192 0.94700 0.05300 0.94892 0.05108
84 0.00185 0.94892 0.05108 0.95077 0.04923
85 0.00178 0.95077 0.04923 0.95255 0.04745
86 0.00172 0.95255 0.04745 0.95427 0.04573
87 0.00166 0.95427 0.04573 0.95592 0.04408
88 0.00160 0.95592 0.04408 0.95752 0.04248
89 0.00154 0.95752 0.04248 0.95906 0.04094
90 0.00148 0.95906 0.04094 0.96054 0.03946
91 0.00143 0.96054 0.03946 0.96197 0.03803
92 0.00138 0.96197 0.03803 0.96335 0.03665
93 0.00133 0.96335 0.03665 0.96468 0.03532
94 0.00128 0.96468 0.03532 0.96596 0.03404
95 0.00123 0.96596 0.03404 0.96719 0.03281
96 0.00119 0.96719 0.03281 0.96838 0.03162
97 0.00115 0.96838 0.03162 0.96952 0.03048
98 0.00110 0.96952 0.03048 0.97063 0.02937
99 0.00106 0.97063 0.02937 0.97169 0.02831
100 0.00103 0.97169 0.02831 0.97272 0.02728
101 0.00099 0.97272 0.02728 0.97370 0.02630
102 0.00095 0.97370 0.02630 0.97466 0.02534
103 0.00092 0.97466 0.02534 0.97557 0.02443
104 0.00088 0.97557 0.02443 0.97646 0.02354
105 0.00085 0.97646 0.02354 0.97731 0.02269
106 0.00082 0.97731 0.02269 0.97813 0.02187
107 0.00079 0.97813 0.02187 0.97892 0.02108
108 0.00076 0.97892 0.02108 0.97969 0.02031
109 0.00074 0.97969 0.02031 0.98042 0.01958
110 0.00071 0.98042 0.01958 0.98113 0.01887
111 0.00068 0.98113 0.01887 0.98182 0.01818
112 0.00066 0.98182 0.01818 0.98247 0.01753
113 0.00063 0.98247 0.01753 0.98311 0.01689
114 0.00061 0.98311 0.01689 0.98372 0.01628
115 0.00059 0.98372 0.01628 0.98431 0.01569
116 0.00057 0.98431 0.01569 0.98488 0.01512
117 0.00055 0.98488 0.01512 0.98543 0.01457
118 0.00053 0.98543 0.01457 0.98595 0.01405
119 0.00051 0.98595 0.01405 0.98646 0.01354
120 0.00049 0.98646 0.01354 0.98695 0.01305
121 0.00047 0.98695 0.01305 0.98743 0.01257
122 0.00046 0.98743 0.01257 0.98788 0.01212
123 0.00044 0.98788 0.01212 0.98832 0.01168
124 0.00042 0.98832 0.01168 0.98874 0.01126
125 0.00041 0.98874 0.01126 0.98915 0.01085
126 0.00039 0.98915 0.01085 0.98954 0.01046
127 0.00038 0.98954 0.01046 0.98992 0.01008
128 0.00036 0.98992 0.01008 0.99029 0.00971
How they compare to each other
2)HH: mean: 6, median: 4, mode: 2
3)HHH: mean: 14, median: 10, mode: 3
4)HHHH: mean: 30, median: 22, mode: 4
5)HHHHH: mean: 62, median: 44, mode: 5
6)HHHHHH: mean: 126, median: 89, mode: 6
7)HHHHHHH: mean: 254, median: 178, mode: 7
8)HHHHHHHH: mean: 510, median: 356, mode: 8
I think I copied/pasted the values in the right place
Last edited by: 7craps on Jan 23, 2019
winsome johnny (not Win some johnny)
January 23rd, 2019 at 10:34:45 PM
permalink
I see the value for 50.308 % is 21 and the value for 48.485 % is 22.
What is the value for 50% ? That is the median.
What is the value for 50% ? That is the median.
It’s all about making that GTA
January 23rd, 2019 at 11:49:33 PM
permalink
median in this type of distribution has to be an integer or that value is meaningless. a few distributions will have a 50% value, but most will not.Quote: Ace2What is the value for 50% ? That is the median.
I know it happens for HH in 4 flips (exactly 50%)
added: A classic example in probability is tossing 2 fair dice and the 50% value (median = 50%)
of rolling at least 1 double 6 showing.
p=1/36
=LOG(1-0.5)/LOG(1-p) = 24.61
one has to try hard to explain how one rolls the dice 0.61 times.
or 24.61 times for that matter.
here is easier data to read (using some R code)
> tMax.dist.run(4,1/2,100)
Trial X Trial X Prob cumulative: X or less
[1,] 3 0 0
[2,] 4 0.0625 0.0625
[3,] 5 0.03125 0.09375
[4,] 6 0.03125 0.125
[5,] 7 0.03125 0.15625
[6,] 8 0.03125 0.1875
[7,] 9 0.029296875 0.216796875
[8,] 10 0.0283203125 0.2451171875
[9,] 11 0.02734375 0.2724609375
[10,] 12 0.0263671875 0.298828125
[11,] 13 0.025390625 0.32421875
[12,] 14 0.02447509766 0.3486938477
[13,] 15 0.02359008789 0.3722839355
[14,] 16 0.0227355957 0.3950195312
[15,] 17 0.02191162109 0.4169311523
[16,] 18 0.02111816406 0.4380493164
[17,] 19 0.02035331726 0.4584026337
[18,] 20 0.01961612701 0.4780187607
[19,] 21 0.01890563965 0.4969244003
[20,] 22 0.01822090149 0.5151453018
[21,] 23 0.01756095886 0.5327062607
[22,] 24 0.0169249177 0.5496311784
[23,] 25 0.01631191373 0.5659430921
[24,] 26 0.01572111249 0.5816642046
[25,] 27 0.01515170932 0.5968159139
[26,] 28 0.01460292935 0.6114188433
[27,] 29 0.01407402568 0.6254928689
21 flips = 0.4969244003
22 flips = 0.5151453018
there can not be any flips between 21 and 22
unless you are from that type of school that says there is.
the 1st value of 50% or greater is 22
if you want the value of exactly 50%
that search continues
back to mean wait time for patterns
no one asked about the variance yet
simulation results for HHHH (when that pattern arrives, we start the count over for another arrival)
grouped data
items: 1000000
minimum value: 4.00
first quartile: 11.00
median: 22.00
third quartile: 40.00
maximum value: 381.00
mean value: 29.95
midrange: 192.50
range: 377.00
interquartile range: 29.00
mean abs deviation: 19.92
sample variance (n): 733.38
sample variance (n-1): 733.38
sample std dev (n): 27.08
sample std dev (n-1): 27.08
Last edited by: 7craps on Jan 24, 2019
winsome johnny (not Win some johnny)
