Coin toss problem

Assume that n is nonzero.

The probability is the number of permutations with at least one run of m or more heads ("qualifying permutations"), divided by the total number of permutations.

The total number of permutations is 2^(m+n).

The length of runs of heads in qualifying permutations ranges from m to m+n. Because m > n there is no qualifying permutation with two sets of m or longer runs separated by one or more tails. Each qualifying permutation therefore has just one qualifying run of heads, of length between m and m+ n (inclusive).

It's easy to see that there is just one qualifying permutation of length m+n, two of length m+n-1, and if applicable, three of length m+n-2, etc.

The number of qualifying permutations depends on the size of n.

If n =1 there are 1+2 = 3 qualifying permutations.

If n = 2 there are 1+2+3 = 6 qualifying permutations.

If n = 3 there are 1+2+3+4 = 10 qualifying permutations.

And so on, with this arithmetic progression.

Again, probability = qualifying permutations / total permutations.

This is not correct, but I can't come up with the right formula. Just as a check, for m=4, n=3, there are 128 permutations and 20 qualifying permutations. For m=5, n=2, there are 8 and for m=6, n=1 there are three.

I think it is right, and that you are in error.

For example, if m = 5 and n = 2, just draw seven hash marks (short vertical lines) in a row on a piece of ruled paper.

There is one qualifying permutation of length seven. There are two of length six, one of which includes the rightmost mark, and one of which includes the leftmost. Starting from the leftmost, there are three of length five (which is obvious if you move progressively right until you start counting on the third from the left and stop counting on the far right). That's six.

The other cases are also exactly as I said. Visual confirmation is a very easy way to see this. If I have made an error, point it out.

p = (n + 2) / [2 ^ (m+1)]

For m=3, n=2, the eight permutations are:

HHHTT
HHHTH
THHHT
TTHHH
HTHHH
HHHHT
THHHH
HHHHH

Eight, not six. The two highlighted ones are the ones you missed in your answer. I made a spreadsheet with all permutations for n=3, the answer is 20. For n=4, the answer is 48.

That seems to work, but how did you get that? That makes the number of permutations

[(n+2) * 2^n] / 2

That looks the form I expected but I can't quite get there.

Doh!

OK, thanks for pointing that out.

A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?

(1/2)^m + (1/2)^(m+1) + ... + (1/2)^(m+n)

(1/2)^m [ 1 + (1/2)n]

(1/2)^m [ ( 2 + n ) / 2]

( 2+ n ) / [ 2 ^ ( m + 1)]

A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?

(1/2)^m + [(1/2)^(m+1) + ... + (1/2)^(m+1)]n

(1/2)^m [ 1 + (1/2)n]

(1/2)^m [ ( 2 + n ) / 2]

( 2+ n ) / [ 2 ^ ( m + 1)]

A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?

(1/2)^m + [(1/2)^(m+1) + ... + (1/2)^(m+1)] for n terms equal to (1/2)^(m+1)

(1/2)^m [ 1 + (1/2)n]

(1/2)^m [ ( 2 + n ) / 2]

( 2+ n ) / [ 2 ^ ( m + 1)]

I never understood your solution (although it is correct), but I came up with my own. There are (n+1) groupings of m consecutive objects in m+n positions. Since the other n coin tosses can be anything, you get (n+1)*2^n passing permutations. However, that overcounts because it is double counting runs of m+1 or more. The number double counted is n * 2^(n-1) or (n/2) * 2^n. So the total number of good permutations is (n+1)*2^n - (n/2)*2^n or (n+2)/2 * 2*n. Divide by 2^(m+n) and I get the same answer you did.