How can I derive the probability that an arbitrary Heads/Tails string of length K occurs M times, when flipping a biased coin N times? [I've now edited my question and partly answered it]

Lets say the probability of heads is p, and the probability of tails is 1-p, and the coin flips are independent. An example Heads/Tails string of length K=6 is HHTHTH.

If 1<=K<= N, how can I derive the probability of an arbitrary string of length K in N flips of my biased coin occurring once, or M times (M<=floor(N/K))?

I know the probability of a sequence with H heads and N-H tails is (p^H)*(1-p)^(N-H).

Also, a string of length K can occur in N flips (with 1<=K<=N) at N+1-K starting positions. So I think the probability my string occurs exactly once is simply: (N+1-K)(p^H)(1-p)^(N-H). This is the M=1 case.

If M>=2, the analysis becomes more complicated. Now, there are 2 or more repeats of my string, and those repeats could start in many places. There is an upper bound on the number of non-overlapping repeats, M, which is floor(N/K). For example, if K=3, N=8, I can have at most floor(8/3) = 2 non-overlapping repeats (e.g. I can't have 3 repeats of a K=3 string since that would require at least N flips total).

The following values of M will be allowed: M=1,...,floor(N/K). For a given M, there will be MK spaces taken up by the string repeats, and N-MK spaces taken up by nonstring flips.

I believe the solution will look something like this:

$\sum_{m=1}^{m=floor(N/K)} (p^H (1-p)^{K-H})^m W(m)$

where H is the number of heads in the arbitrary string, p is the probability of heads, K is the string length, N is the total number of flips, and m is the number of string repeats.

So now my question becomes simply what is the form of W(m), the number of ways of partitioning the flip sequence to have m repeats of the string?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.