1
$\begingroup$

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?

$\endgroup$

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.