I came up with a recurrence relation. Let P(h, k) = n(h, k) / 2^k be the probability, where n(h, k) is the number of sequences of length k containing a run of h or more heads.

If h > k then n(h, k) = 0. Otherwise we have two possibilities for a sequence containing h or more heads in a row:

- an initial run of h heads, followed by k-h "don't care" tosses or
- a prefix of length j < k-h-1 not containing a run of h heads, followed by a tail, followed by h heads, followed by k-j-h-1 "don't care" tosses.

n(h, k) = 2^(k-h) + sum (j in 0..k-h-1) (2^(k-j-h-1).nbar(h, j))

where nbar(h, j) = 2^j - n(h, j) is the number of sequences of length j that do not contain a run of h or more heads. This gives

n(h, k)

= 2^(k-h) + sum (j in 0..k-h-1) (2^(k-j-h-1).2^j - 2^(k-j-h-1).n(h, j))

= 2^(k-h) + (k-h).2^(k-h-1) - sum (j in 0..k-h-1) (2^(k-j-h-1).n(h, j))

Let's try this out. Consider the case h = 2.

- k = 2 sequences are {HH};

n(2, 2) = 2^0 = 1. - k = 3 sequences are {HH*, THH};

n(2, 3) = 2^1 + 2^0 - 2^0.n(2, 0) = 3. - k = 4 sequences are {HH**, THH*, *THH};

n(2, 4) = 2^2 + 2.2^1 - 2^1.n(2, 0) - 2^0.n(2, 1) = 8. - k = 5 sequences are {HH***, THH**, *THH*, T*THH, HTTHH}.

n(2, 5) = 2^3 + 3.2^2 - 2^2.n(2, 0) - 2^1.n(2, 1) - 2^0.n(2, 2) = 19. - ...

## No comments:

Post a Comment