Flipping Coins, Getting 3 in a Row - Gambling and Probability

findingneema · 08-12-2012, 01:36 PM

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?

heehaww · 08-12-2012, 03:35 PM

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.

**BruceZ** · 08-12-2012, 04:33 PM

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:

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. The probability of a no change is 0.5. Using the streak calculator, we have

P(3 H or 3 T) = 0.925537109375

So the answer to the second question is 1 minus this or about 7.44%.

Now for the first question, the trick is to note

P(3 H or 3T) = P(3 H) + P(3 T) - P(3 H and 3 T)

By the inclusion-exclusion principle. We just found P(3 H or 3 T). We can use the streak calculator again to find P(3 H) = P(3 T) = 0.64794921875. Now we can solve for P(3 H and 3 T) which comes out to 37.0%.

I also verified these by R simulation.

sallymustang · 08-12-2012, 05:23 PM

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

findingneema · 08-13-2012, 01:54 AM

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.

cyberfish · 08-14-2012, 05:13 AM

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.

**BruceZ** · 08-17-2012, 04:40 AM

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

Sherman · 08-17-2012, 08:54 AM

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?

**BruceZ** · 08-17-2012, 12:54 PM

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.