# Sample Space of Longest Run - heads and tails

I am trying to find a way to calculate all possible combinations of a sequence that have a certain length of long run.

When answering questions regarding sequences of heads and tails, sometimes participants will consider a sample space of longest run.
For a sequence of five coin flips, this is easy enough to calculate using a brute-force method - writing out all 32 possible sequences and then categorising them based on their longest run.
So, for example, a sequence with the longest run of 5 has a probability of 2/32 as there is only one way to have a longest run of 5 with a sequence of length 5.

However, I now have a sequence of length 10. I want to find out exactly how many sequences out of the 1024 possible sequences that have a longest run of 2 or 3.
I am assuming that it doesn't matter if the longest run is of heads or tails.

Is there a formula or code that could be used to calculate this?

• If it doesn't matter whether the longest run is heads or tails, there should be a $2/32 = 1/16$ probability of a longest run of $5$ in a sequence of $5$. Commented Jul 2, 2019 at 1:28
• Ah yes! My mistake, corrected! Thanks :) Commented Jul 3, 2019 at 2:01

Let $$f(n, l, s)$$ be the number of flip combos with $$n$$ flips remaining, a maximum streak $$\leq s$$, and a streak of length $$l$$ directly before the flip sequence. For example, if we are trying to find the number of streaks of length $$10$$ with a streak of $$3$$ heads directly before the $$10$$ and a maximum streak of $$5$$, the coin flip sequence can be represented by HHH_ _ _ _ _ _ _ _ _ _, where a "_" is an unflipped sequence. Then $$f(10, 3, 5) = f(9, 1, 5) + f(9, 4, 5)$$, with the cases of the next flip being a T or an H respectively.

What you are asking is to find $$f(n, 0, s)-f(n, 0, s-1)$$. If $$s = 1$$, then $$f(n, 0, s) = 2$$. The rules for $$f(n, l, s)$$ are as follows.

If $$n = 0$$, $$f(n, l, s) = 1$$.

If $$l, $$f(n, l, s) = f(n-1, 1, s) + f(n-1, l+1, s)$$.

If $$l = s$$, $$f(n, l, s) = f(n-1, 1, s)$$.

Searching in the OEIS, I found [A048003]. This is essentially what you are looking for. On the OEIS, it says that, letting $$T(n, s)$$ be your function, the following rules dictate $$T(n, s)$$:

If $$s < 1$$ or $$s > n$$, T(n, s) = 0

If $$s = 1$$ or $$s = n$$, T(n, s) = 2

Otherwise, $$T(n, s) = 2*T(n-1, s) + T(n-1, s-1) - 2T(n-2, s-1) + T(n-s, s-1) - T(n-s-1, s)$$.

Figured it out!

Here is the code I have:

install.packages('gtools')
library(gtools)

x <- c(0, 1) # heads = 0, tails = 1

p = permutations(n = 2, r = 10, v = x, repeats.allowed = T)

p.df = as.data.frame(t(p))

q = apply(p.df, 2, function(x){
max(rle((x == 0))\$lengths)
}
)

length(which(q == 10)) #where q == the length of the longest run
$$$$
`