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: 5988
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: 5988
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: 1883
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]
 0.375
So that looks right for 4 flips

9 Flips
> # m heads OR m tails
> prob[N]
 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 flips
m = 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^m
t[m] = (1-p)^m
prob[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 tails
prob[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

added: IMO best reading on coin flips is
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: 1883
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.

added: for your 9 flip example the exact answer is
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)) / (2^9)

where F2 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 (0+1) (some do not use the 0, I do, in that case use the 8th F#)
F2= 2 (1+1) and so on to the 9th F#
F2=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 flips
m = 3 # length of run
p = 0.50 # P(heads)

sims = 0
count1 = 0
count2 = 0

while (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/sims
error1 = 3.29*sqrt(p1*(1-p1)/sims)
p2 = count2/sims
error2 = 3.29*sqrt(p2*(1-p2)/sims)

# m heads OR m tails
p1
p1 - error1
p1 + error1
# m heads AND m tails
p2
p2 - error2
p2 + error2
# neither m heads NOR m tails
1 - p1
1 - p1 - error1
1 - p1 + error1
sims

results
> # m heads OR m tails
> p1
 0.7845934
> p1 - error1
 0.7828374
> p1 + error1
 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
 0.1442022
> p2 - error2
 0.1427017
> p2 + error2
 0.1457027
> # neither m heads NOR m tails
> 1 - p1
 0.2154066
> 1 - p1 - error1
 0.2136506
> 1 - p1 + error1
 0.2171626
> sims
 593278
>

Good Luck
winsome johnny (not Win some johnny)
7craps Joined: Jan 23, 2010
• Posts: 1883
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: 3738
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...