Sample Space of Longest Run - heads and tails

Question

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?

Answer 1

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<s$, $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)$.

Answer 2

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
```