Two Plus Two Poker Forums Flipping Coins, Getting 3 in a Row
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read Video Directory TwoPlusTwo.com

 Notices

 Probability Discussions of probability theory

 Thread Tools Display Modes
 08-12-2012, 01:36 PM #1 Pooh-Bah     Join Date: Feb 2007 Location: LOL Math... Posts: 5,622 Flipping Coins, Getting 3 in a Row A fellow gambler offers you a simple game. He flips a fair coin 14 times, and if he gets a stretch of 3 consecutive heads AND a stretch of 3 consecutive tails, you pay his bet at 2-1. He also offers a different bet, where if he gets neither 3 heads in a row nor 3 tails in a row on 14 flips, he'll pay you 9-1. Should you take either bet? What's your preferred approach to solving this game?
 08-12-2012, 03:35 PM #2 adept   Join Date: Aug 2011 Location: Nova Posts: 736 Re: Flipping Coins, Getting 3 in a Row I guess the n-nacci method can't be used here since we're talking about 2 different stretches needed instead of just one. Unless there's some kind of multinomial version of the formula that I'd be dying to know? Lol Bruce???? I'm sure some recurrence relation could be used, but I don't feel like doing that lol. I'll see if I can find a different approach.
08-12-2012, 04:33 PM   #3
Carpal \'Tunnel

Join Date: Sep 2002
Posts: 8,899
Re: Flipping Coins, Getting 3 in a Row

Quote:
 Originally Posted by findingneema A fellow gambler offers you a simple game. He flips a fair coin 14 times, and if he gets a stretch of 3 consecutive heads AND a stretch of 3 consecutive tails, you pay his bet at 2-1. He also offers a different bet, where if he gets neither 3 heads in a row nor 3 tails in a row on 14 flips, he'll pay you 9-1. Should you take either bet? What's your preferred approach to solving this game?

You shouldn't take either bet. He will win the first with probability 37.0%. You will win the second with probability 7.44%.

These are done using 3 clever tricks together. First, I've posted before how to find the probability of r or more consecutive heads in n tosses of a coin having probability p of heads. To review, that is computed from the recurrence:

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

P(r) = p^r

P(n) = 0, for n < r

In words this says that the probability of getting it by the nth flip is the probability that we already got it by flip n-1, plus the probability that we get it for the first time on the nth flip. The probability that we get it for the first time on the nth flip is the probability that the last r were heads p^r, times the probability that the preceding one was tails (1-p), times the probability that we didn't get it before that which is 1 minus the probability that we did get it before that P(n-r-1).

You can easily compute the value of P(n) in Excel using the above recurrence, or you can use a streak calculator like this one to compute it for you. A fancier streak calculator that I created to run in Excel can be found here, and that will also compute the probabilities of multiple streaks with a different recurrence relation that I derived. We won't need that here though. We can get everything we need from the simple streak calculator.

To answer these questions with the simple streak calculator, we need 2 more tricks. You should try to figure these out for yourself as it is a nice puzzle. The solution is below.

Spoiler:

Last edited by BruceZ; 08-13-2012 at 02:41 AM.

 08-12-2012, 05:23 PM #4 enthusiast   Join Date: Jun 2011 Posts: 78 Re: Flipping Coins, Getting 3 in a Row My solution would come from listing all the 2^14 sequences in Excel and just counting them. Only takes a few minutes and I can see if I did it right. Question #1 I get =6068/16384 My second solution would be to run a sim, like Bruce did to verify, and have it do all the counting like in R. (I need to work on my R programming) Another interesting question would be if you were reaching into a bag with 52 red balls and 48 green balls (or flipping an unfair coin) and drawing with replacement 14 times. Bruce's tricks, I think, would then not work. Simulation would then be preferred or Excel by counting and adding the sequence probabilities. A combinatorial approach would be very challenging with an unfair coin. Sally
 08-13-2012, 01:54 AM #5 Pooh-Bah     Join Date: Feb 2007 Location: LOL Math... Posts: 5,622 Re: Flipping Coins, Getting 3 in a Row As always, Bruce has the elegant (and correct) solution. I did a full recursive calc in Excel (didn't take that long to setup the equations), which allowed basically any number of flips and an unbiased coin. Using 13 flips (instead of 14) makes the above bets much closer to fair (p=0.326, p=0.908). For a heavily biased coin and a (relatively) large number of flips, you can basically assume the biased side hits its streak ~100% and use a streak calculator for the opposite side. For example, at p(Head)=0.75 and 20 flips, p(3H)=0.9952, p(3T)=0.2002, and p(3H & 3T)=0.1977, for a relatively small error.
08-14-2012, 05:13 AM   #6
journeyman

Join Date: Sep 2004
Posts: 360
Re: Flipping Coins, Getting 3 in a Row

Quote:
 Originally Posted by BruceZ To answer these questions with the simple streak calculator, we need 2 more tricks. You should try to figure these out for yourself as it is a nice puzzle. The solution is below.
The first trick (second question) I thought of, just because you've mentioned it before in a previous thread. I missed the second trick (first question), perhaps it would have popped up if I would have solved the second question first.
Without the hints I would have brute-forced the calculations.

08-17-2012, 04:40 AM   #7
Carpal \'Tunnel

Join Date: Sep 2002
Posts: 8,899
Re: Flipping Coins, Getting 3 in a Row

Quote:
 Another interesting question would be if you were reaching into a bag with 52 red balls and 48 green balls (or flipping an unfair coin) and drawing with replacement 14 times. Bruce's tricks, I think, would then not work. Simulation would then be preferred or Excel by counting and adding the sequence probabilities.
I took this as a challenge and developed recurrence relations that give you the probability of heads or tails for a biased coin. The answer to your question is 92.617% for 3 red or 3 green, so 7.383% for neither. You can use the old recurrence for 3 reds and for 3 greens separately as that also works for a biased coin. Then you can use inclusion-exclusion to get 3 reds and 3 greens as before.

The new recursion is in the following R script. The recurrence uses 3 separate arrays. h[n] is the probability that a streak of heads occurred at the nth flip and this was the first streak of either heads or tails. t[n] is the same for tails. prob[n] is the probability that a streak of either heads or tails occurred by the nth flip. In the main loop, where we get say 3 heads in a row, we need a tail before that, but we have to subtract the cases where that that tail made 3 in a row for the first time, and also subtract the cases where we already had 3 heads or tails in a row before we got that tail. Same for the head.

Code:
```##############################################
# Biased/unbiased  recursion of heads OR tails
##############################################

N = 14     # 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]```

Of course you can also use this for an unbiased coin by setting p = 0.5. To check it, we can set p = 0.5 and compare the result to the old recursion with the trick of setting N = 13 and m = 2. I did this, and they are identical. Here is the R script for the old recursion. Note that this also works for biased coins, but only for just heads, not heads or tails.

Code:
```##########################################
# Biased/unbiased  recursion of heads
##########################################

N = 13     # number of flips
m = 2      # length of run (must be < N - 1)
p = 0.5    # P(heads)

prob = rep(0,N)
prob[m]= p^m
prob[m+1] = prob[m] + (1-p)*p^m
for (n in (m+2):N) {
prob[n] = prob[n-1] + (1-prob[n-m-1])*(1-p)*p^m
}

prob[N]```

Note that the conditions I've imposed on m in these programs are just to simplify the code to make the method clear. The code can be easily modified to accommodate all possible values just by making parts of it conditional, but those values aren't generally of interest.

Quote:
 My second solution would be to run a sim, like Bruce did to verify, and have it do all the counting like in R. (I need to work on my R programming)
The rle function works great for that. It returns a data structure that tells you how many of each run of heads and tails there were. It's the inverse function of rep. I wrote the following simulation, and I also used that to check the new biased recursion:

Code:
```##################################
# Biased/unbiased  simulation of
# Heads OR Tails
# Heads AND Tails
# Neither heads NOR tails
##################################

N = 14     # number of flips
m = 3      # length of run
p = 0.6    # 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```

Last edited by BruceZ; 08-18-2012 at 09:58 AM. Reason: And the crowd goes wild!

 08-17-2012, 08:54 AM #8 Carpal \'Tunnel     Join Date: Jun 2005 Location: Psychology Department Posts: 7,426 Re: Flipping Coins, Getting 3 in a Row The first two of those scripts won't work unless 'n' is defined. If they worked for you Bruce it must be because you defined 'n' somewhere else in your workspace. But as they are printed here, they shouldn't work. For what it is worth, you do have 'N' defined, so maybe they are meant to be the same thing?
08-17-2012, 12:54 PM   #9
Carpal \'Tunnel

Join Date: Sep 2002
Posts: 8,899
Re: Flipping Coins, Getting 3 in a Row

Quote:
 Originally Posted by Sherman The first two of those scripts won't work unless 'n' is defined. If they worked for you Bruce it must be because you defined 'n' somewhere else in your workspace. But as they are printed here, they shouldn't work. For what it is worth, you do have 'N' defined, so maybe they are meant to be the same thing?
I fixed them in the original post. N is a constant, n is a variable. It should have been N, but it was working in my space because they are always the same at the end of the program if it runs once.

I also changed the last simulation program so that you don't have to change an array of H and T when you change the probability. Instead of using sample, it now uses runif. So for all 3 programs, you only have to change the first 3 numbers.

I ran them all again in a fresh space, and they are working.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are Off Pingbacks are Off Refbacks are Off Forum Rules

All times are GMT -4. The time now is 10:18 PM.

 Contact Us - Two Plus Two Publishing LLC - Privacy Statement - Top

Powered by vBulletin®
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0 ©2011, Crawlability, Inc.
Copyright © 2008-2010, Two Plus Two Interactive