If you flip a fair coin 100 times, what are the chances of getting tails 6 times in a row during those 100 tosses.
This is probably pretty easy but hopefully someone can help me.
It's not easy. I thought about it for a while and came up with the correct answer, but I would not characterise it as easy. I'll start by noting you can find the answer
here but that doesn't really offer any insight into where it comes from (and I couldn't find an explanation anywhere).
The following is how I worked out the answer, but there may be a simpler way to think of it.
Denote the number of ways to get N tails in a row in A flips by f(A). Obviously, if we flip the coin fewer than N times, there's no chance of getting N tails, so f(A)=0 for A<N. Also obvious is that for A=N, there's exactly one way to do it, so f(N)=1.
Suppose we know the value of f(V) for some V>N. Now what is f(V+1)? Well, we are just adding a flip to the end, which can come up either tails or heads, so each of the ways in f(V) counts twice -- once with a tail at the end and once with a head at the end. But that's not all because there are some positions of V flips where:
(1) there were N-1 tails at the end;
and
(2) nowhere in the position were there N tails in a row
Each of
those positions of V flips gives rise to one position of V+1 flips where there are N tails in a row because adding one more tail to the end makes it N rather than N-1 tails. Note that condition (2) is important because otherwise we will
double count positions that contain N tails in a row.
I will denote the "number of ways of flipping a coin V times such that (1) the last N-1 flips are all tails
and (2) nowhere in the V flips are there N tails in a row" by Q(V).
So putting that together, f(V+1) = 2 * f(V) + Q(V)
But what is Q(V)? Well, we know that out of the V flips, the last N flips are fixed: the last N-1 flips have to be tails, and the flip before the tails has to be a head, because otherwise there would be N tails in a row, which would violate condition (2) and mean it's not actually in Q(V). So N flips are fixed which leaves V-N flips free. If those free flips could be totally anything, there would be 2^(V-N) total positions. But in those V-N flips, there can't be N tails in a row. By definition, there are f(V-N) ways of getting N tails in a row in V-N flips, which we have to subtract off.
Therefore, Q(V) = 2^(V-N) - f(V-N).
It turns out that Q(V) is precisely the definition of the V-th
Fibonacci N-step number, which is where the formula on that page comes from.
So now we have the following recurrence relation:
f(A) = 0 for A < N,
f(A) = 1 for A = N,
f(A) = 2 * f(A - 1) + Q(A - 1),
Q(V) = 0 for A < N, and
Q(V) = 2^(V-N) - f(V-N) for A >= N.
Using the recurrence relation, you can evaluate f(A) using a
computer program or a spreadsheet. And of course, the answer to the original problem is f(100)/2^100 where N=6. The
exact answer is 692255904222999797557597756576/2^100.0. This turns out to be approximately 54.61%.
Note that the answer is
not 75%. If you mistakenly
double count positions where "the last N-1 flips are tails
and N tails in a row occurs somewhere", then you will get 75%. In other words, if you incorrectly define Q(V) to be 2^(V-N), then you will get 75%, but it's wrong.
