hmmm23
Joined: Jun 23, 2013
• Posts: 66
July 12th, 2013 at 11:12:09 AM permalink
Me and a buddy generally tackle gambling questions together. But we've hit a problem we can't solve. Thanks for your time.

If you flip a coin 9 times, what are the chances you'll have at least one streak of 3 Heads or 3 Tails in a row?

He's an engineer, so he likes equations. This time his fancy binomial whatsits suggested the answer might be 86.6%, but that felt a little high to me, so I asked him to apply his equation to a set of 4 coin flips.

Since a set of 4 coin flips only has 16 possible outcomes, I was able to write them all out and ascertain there's a 6 in 16, or 37.5% chance of a '3 straight' streak. His fancypants math produced an incorrect number of 43.75%.

So I have two questions:

1. What's the correct answer to the Streak of 3 Heads or Tails in 9 coin flips question? and,

2. What's the proper equation to use to arrive at that number? (Teach a man to fish, and all that.)

Thanks again.
tringlomane
Joined: Aug 25, 2012
• Posts: 6278
July 12th, 2013 at 11:23:39 AM permalink
A recursive formula was written out by the Wizard himself to answer a similar problem. I'll leave the modifications to answer your particular question for the moment.

MathExtremist
Joined: Aug 31, 2010
• Posts: 6526
July 12th, 2013 at 11:24:06 AM permalink
See this:

http://www.pulcinientertainment.com/info/Streak-Calculator-enter.html

Note that to get the probability of either 3 heads *or* 3 tails, you need to double the reported probability.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
treetopbuddy
Joined: Jan 12, 2013
• Posts: 1739
July 12th, 2013 at 11:31:06 AM permalink
I'm chiming in for EvenBob......what difference does it make if 3 in a row show.. :-)
Each day is better than the next
tringlomane
Joined: Aug 25, 2012
• Posts: 6278
July 12th, 2013 at 11:36:49 AM permalink
Ah yes, I forgot about the streak calculator. :) Read many discussions on 2+2 from BruceZ about it.
7craps
Joined: Jan 23, 2010
• Posts: 1977
July 12th, 2013 at 12:35:44 PM permalink
Quote: hmmm23

So I have two questions:

1. What's the correct answer to the Streak of 3 Heads or Tails in 9 coin flips question? and,

The trick while using that streak calculator repaired by BruceZ is to use
n-1 for n and
k-1 for k
this trick only works when p = 0.50 (1/2)
n=8 and k = 2 = 0.785156250000000
pacomartin in another post also showed this trick
I think in the link provided for the math of streaks where the calculator lives

I also have this in a simple three-state Markov Chain using Excel
columns are A-F
A1,B1,C1 as shown D1 = 1-C1
A2: =0.5*SUM(A1:B1)
B2: =0.5*A1
C2: =C1+0.5*B1
D2: =1-C2

fill down from row 2 to how far you want.
300. Fine
ColA is probability after N flips that you are at 1 in a row
ColB is probability after N flips that you are at 2 in a row
other columns are shown

easy stuff and very clean
Look at C9.
the answer to the probability that in 9 flips of a fair coin, one sees a Head or Tail run of at least 3

there is some R code by BruceZ here for Heads or Tails Runs where p does not have to equal 0.50
http://forumserver.twoplustwo.com/25/probability/flipping-coins-getting-3-row-1233506/#post34329689

BruceZ is 'fantabulous'

a note: # length of run (must be > 1 and <= N/2)
R returns for 4 flips and either run of 3
Error in h[n] = ((1 - p) - t[n - m] - prob[n - m - 1] * (1 - p)) * p^m :
replacement has length zero
>
> # m heads OR m tails
> prob[N]
[1] 0.375
So that looks right for 4 flips

9 Flips
> # m heads OR m tails
> prob[N]
[1] 0.7851562

One can use
http://www.compileonline.com/execute_r_online.php
to run the R code below
`############################################### Biased/unbiased  recursion of heads OR tails##############################################N = 9     # number of flipsm = 3      # length of run (must be  > 1 and <= N/2)p = 0.5   # P(heads)prob = rep(0,N)h = rep(0,N)t = rep(0,N)h[m] = p^mt[m] = (1-p)^mprob[m] = h[m] + t[m]for (n in (m+1):(2*m-1)) {  h[n] = (1-p)*p^m  t[n] = p*(1-p)^m  prob[n] = prob[n-1] + h[n] + t[n]}for (n in (2*m):N) {  h[n] = ((1-p) - t[n-m] - prob[n-m-1]*(1-p))*p^m  t[n] = (p - h[n-m] - prob[n-m-1]*p)*(1-p)^m  prob[n] = prob[n-1] + h[n] + t[n]}# m heads OR m tailsprob[N]`

Quote: hmmm23

2. What's the proper equation to use to arrive at that number? (Teach a man to fish, and all that.)

Thanks again.

There are recursive methods and Markov chain methods.
a bit more challenging than just adding a few #s together
Good Luck and have some fun

The Coin Toss: The Hydrogen Atom of Probability
Stefan Hollos, J. Richard Hollos

http://www.abrazol.com/books/cointoss/
The Coin Toss: Probabilities and Patterns

Summary of coin toss probability formulas (pdf, 8 pages) in this book.
http://www.abrazol.com/books/cointoss/cointossruns.pdf

markov chain matrix here
the transition matrix

raised to the 9th power (the 9th coin flip)

fractions

winsome johnny (not Win some johnny)
hmmm23
Joined: Jun 23, 2013
• Posts: 66
July 12th, 2013 at 1:29:31 PM permalink
Quote: 7craps

The trick while using that streak calculator repaired by BruceZ is to use
n-1 for n and
k-1 for k
this trick only works when p = 0.50 (1/2)
n=8 and k = 2 = 0.785156250000000

Wow, thanks very much to everyone who replied, especially 7craps, who definitely gave of his time and brain power. I'd also like to thank Tringlomane, and MathExtremist, who's helped me on some other things, as well.

You guys rock!

Sweet, now I get to surprise my buddy by beating him to the punch in his own area of strength (cue evil laughter), so thanks again.
7craps
Joined: Jan 23, 2010
• Posts: 1977
July 12th, 2013 at 1:36:19 PM permalink
Quote: hmmm23

Sweet, now I get to surprise my buddy by beating him to the punch in his own area of strength (cue evil laughter), so thanks again.

Many are excellent at math but yet can stumble with probability. They are in the majority.

Dr. Maths
"In the short run, chance may seem to be volatile and unfair.
Considering the misconceptions, inconsistencies, paradoxes and
counter intuitive aspects of probability, it is not a surprise that as
a civilization it has taken us a long time to develop some methods
to deal with this."

It gets easier when we first deal with the sample space.

402/512
512 = 2^9 (this should be intuitive)
The challenge (and fun IMO) is the 402
a fun method using Fibonacci numbers:

The exact formula in this case
(a run of at least 3 Heads or Tails in 9 flips) is
(2^9) - (2*(F2[9])) / (2^9)

where F2[9] is the 9th Fibonacci 2-step number.
(For a run of 3 we use k-1. There is proof of this on the net. I do not have a link handy)

The regular Fibonacci numbers are obtained by summing the previous 2 numbers (0,1,1,2,3,5,8,13,21,34,55...).
The First F#
F2[1]= 1 (0+1) (some do not use the 0, I do, in that case use the 8th F#)
F2[2]= 2 (1+1) and so on to the 9th F#
F2[9]=55
You want a run of Heads or Tails we multiply 55*2 = 110
This is the # of sequences in the 512 sample space that do NOT have a run of at least 3.
That must leave 512-110 that do (402)
Hey, it worked.
This method can get crazy and very unstable for large N so I use it for flips of 100 or less in a spreadsheet)

of course, I do check my answers with a sim or two
I used a BruceZ R code
`################################### Biased/unbiased  simulation of# Heads OR Tails# Heads AND Tails# Neither heads NOR tails# Code by BruceZ##################################N = 9     # number of flipsm = 3      # length of runp = 0.50    # P(heads)sims = 0count1 = 0count2 = 0while (1) {  flips = ifelse(runif(N,0,1) < p, "H", "T")  runs = rle(flips)  heads = runs\$lengths[runs\$values == "H"] >= m  tails = runs\$lengths[runs\$values == "T"] >= m  if ( sum(heads) | sum(tails) ) {count1 = count1 + 1}  if ( sum(heads) & sum(tails) ) {count2 = count2 + 1}  sims = sims + 1}p1 = count1/simserror1 = 3.29*sqrt(p1*(1-p1)/sims)p2 = count2/simserror2 = 3.29*sqrt(p2*(1-p2)/sims)# m heads OR m tailsp1p1 - error1p1 + error1# m heads AND m tailsp2p2 - error2p2 + error2# neither m heads NOR m tails1 - p11 - p1 - error11 - p1 + error1sims`

results
> # m heads OR m tails
> p1
[1] 0.7845934
> p1 - error1
[1] 0.7828374
> p1 + error1
[1] 0.7863494
> # m heads AND m tails
>>> this is a bit more advanced, but still can be done with Fibonacci numbers (answer 74/512 or 0.14453125)
> p2
[1] 0.1442022
> p2 - error2
[1] 0.1427017
> p2 + error2
[1] 0.1457027
> # neither m heads NOR m tails
> 1 - p1
[1] 0.2154066
> 1 - p1 - error1
[1] 0.2136506
> 1 - p1 + error1
[1] 0.2171626
> sims
[1] 593278
>

Good Luck
winsome johnny (not Win some johnny)
7craps
Joined: Jan 23, 2010
• Posts: 1977
July 12th, 2013 at 5:47:03 PM permalink
Quote: MathExtremist

Note that to get the probability of either 3 heads *or* 3 tails,
you need to double the reported probability.

I gots to disagree here and add some.
Maybe you were in a hurry to finish typing on your way out with your wife and family for an extended weekend?

BruceZ
"The probability of getting 3 heads OR 3 tails in a row in 14 flips is
the same as the probability of getting 2 heads in a row in 13 flips.
To see this, think about a sequence of changes rather than a sequence of heads and tails.
We need 2 consecutive no changes.
There are only 13 trials because we don't care about the result of the first trial."

Either/Or would be using the streak calculator again
n = n-1 (8)
k = k-1 (2)
We get exactly 402/512 or 0.78515625
as agrees with a previous post

Now if we are looking for both Head AND Tail runs of at least 3 in length,
ME is correct that we start by adding both together.

OP Question is 9 flips and both H and T run of 3

0.46484375 + 0.46484375 = 0.9296875
We should know this horribly over-counts the successful sequences
and need to use the inclusion-exclusion principle to remove that over-count
P(3 H) + P(3 T) - P(3 H or 3 T)
0.9296875 - 0.78515625 = 0.14453125 (or 74/512)
Looks like my sim data is close to this
(and I used Excel to list all 512 sequences and counted exactly 74 of them that did indeed have both runs)
and the markov chain method
transition matrix with absorbing states
p=

v=[1,0,0,0,0,0,0,0,0,0,0,0,0]
v*p^9 =
0, 17/256, 21/512, 47/256, 47/512, 23/512, 17/256, 21/512, 47/256, 47/512, 23/512, 37/512, 37/512
yep (37/512 + 37/512)
p^9 =

This thread really has enough info in it for one to become a world class expert on
everything you want to know about a coin toss and more.

Pool is open for the weekend
winsome johnny (not Win some johnny)
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5944
July 13th, 2013 at 9:59:25 AM permalink
Quote: 7craps

There are recursive methods and Markov chain methods.
a bit more challenging than just adding a few #s together

I tried calculating a non-recursive formula using matrix algebra.
P(3 in a row) = P(3 heads in a row) + P(3 tails in a row).
Since every streak has a "partner streak" where the Hs and Ts are switched (e.g. HHTH <--> TTHT), P(3 in a row) = 2 x P(3 heads in a row).
Let P(n) be the probability of getting 3 heads in a row in n tosses.
P(n) = 1/8 [for HHH] + 1/8 x P(n-3) [for HHT] + 1/4 x P(n-2) [for HT] + 1/2 x P(n-1) [for T].
This is rewritten as:
1/8 = -P(n) + 1/2 P(n-1) + 1/4 P(n-2) + 1/8 P(n-3)
Also, when calculating P(n-1):
1/8 = -P(n-1) + 1/2 P(n-2) + 1/4 P(n-3) + 1/8 P(n-4)
Thus, -P(n) + 1/2 P(n-1) + 1/4 P(n-2) + 1/8 P(n-3) = -P(n-1) + 1/2 P(n-2) + 1/4 P(n-3) + 1/8 P(n-4)
which becomes, P(n) = 3/2 P(n-1) - 1/4 P(n-2) - 1/8 P(n-3) - 1/8 P(n-4)
However, the eigenvalues of the recursion matrix are the roots of a 4th-degree polynomial, so I stopped there...
puzzlenut
Joined: Sep 19, 2013
• Posts: 71
September 19th, 2013 at 4:49:49 PM permalink
Quote: hmmm23

If you flip a coin 9 times, what are the chances you'll have at least one streak of 3 Heads or 3 Tails in a row?

This question can be answered literally, but the more usual form of this question would be "If you flip a coin 9 times what are the chances that you will see a run of 3 or more consecutive heads." I think that is the question that has been answered and may be the question that the poster meant to ask.

Here is the logic behind the probability calculator.

The probability that three heads will have been thrown in n + 1 tosses is the probability that they will have been thrown in n tosses plus the probability that they will be thrown for the first time on the n + 1 toss.

The probability that they will be thrown for the first time on the n + 1 toss is the probability that they will not have been thrown by the n - 3 toss times the probability that the last four tosses were THHH. The general formula is

P(n + 1) = P(n) + [1 - P(n-r)] * (1-p)*p^r, for n >= r

In this case p = 1/2 and r = 3 and our starting value is P(3) = 1/2^3 P(n) = 0 for n < 3

n

3 1/8

4 1/8 + 1/16 = 3/16

5 3/16 + 1/16 = 1/4

6 1/4 + 1/16 = 5/16

7 5/16 + (7/8)(1/16) = 47/128

8 47/128 + (13/16)(1/16) = 107/256

9 107/256 + (3/4)(1/16) = 119/256 = 0.4648437

This agrees with the probability calculator. The "trick" has not been fully explained.
7craps
Joined: Jan 23, 2010
• Posts: 1977
August 9th, 2018 at 11:33:06 AM permalink
Quote: 7craps

402/512
512 = 2^9 (this should be intuitive)
The challenge (and fun IMO) is the 402

and it has been pointed out to me that either Heads or Tails probability could be
Heads or Tails and not both
or

we have calculated the later in this post.
Sally will follow with her proof
but I do not see my error

take 4 flips
16 outcomes
`List has 16 entries.at least run2h,h,h,h 1h,h,h,t 1h,h,t,h 1h,h,t,t 12h,t,h,h 1h,t,h,t <<<<<h,t,t,h 2h,t,t,t 2t,h,h,h 1t,h,h,t 1t,h,t,h <<<<<t,h,t,t 2t,t,h,h 12t,t,h,t 2t,t,t,h 2t,t,t,t 2heads=8 (1/2)tails=8 (1/2)HandT (both)=2 (1/8) HoT not both=12 (12/16) (3/4)HoT or HandT (both)=14 (14/16) (7/8)`

Thanks
I see where Sally will take this now

It is a nice feature to have with Baccarat streaks
so I have warned the reader
winsome johnny (not Win some johnny)