Number of binary strings containing at least n consecutive 1

Question

Let $Z_{m, n, q}$ be the number of binary strings (ordered lists of 0's and 1's) of length $m$, containing exactly $q$ 1's and at least $n$ consecutive 1's at any part of the string. I'm trying to find a formula for this number that is easily calculated (by a computer). I've managed to find the following recurrence relation:

$$Z_{m+1, n, q} = Z_{m, n, q} + Z_{m, n, q-1} + \binom{m-n}{q-n} - Z_{m-n, n, q-n}$$ Explanation:

Let us call the strings we want to count good strings. The first term contains all good strings that end with a 0. The second terms contains all good strings that end with a 1 and have n consecutive 1's in the first $m$ elements of the string. The third term contains all good string which have n consecutive 1's in the last n elements of the string. Finally the fourth term accounts for the overlap between the second and third terms, by removing all good strings which end with n consecutive 1's but also have n consecutive 1's in the first m-n elements.

Is this formula correct? I think it is, but I also have the feeling that it is overly complicated, and have no clue how to simplify it (or tackle the recurrence relation). Could anyone help me?

PS: I'm interested in this formula because I am trying recreate this graph: http://wizardofodds.com/gambling/betting-systems/martingale.gif . Don't worry, I know you can't beat the house edge, just curious to see how it changes for unfair coins and numbers.

Answer 1

A direct counting (not via a recurrence relation):

Lemma 1: (balls and sticks)The number of non-negative integer solutions of $$x_1+x_2+\dots +x_a=b$$ is $$\binom{b+a-1}{a-1}$$

---

Lemma 2: Let $R(b,a,k)$ number of non-negative integer solutions of $$x_1+x_2+\dots +x_a=b$$ where each $0\le x_i<k$

By inclusion-exclusion, the number of solutions to the above equation with at least one part being not less than $k$ is $$\sum_{i=1}^{\lfloor \frac{b}{k}\rfloor}(-1)^{i+1}\binom{a}{i}\binom{b-ki+a-1}{a-1}$$

Hence,$$R(b,a,k)=\binom{b+a-1}{a-1}-\sum_{i=1}^{\lfloor \frac{b}{k}\rfloor}(-1)^{i+1}\binom{a}{i}\binom{b-ki+a-1}{a-1}$$

---

Solution: The problem is equivalent to finding the number of non-negative solutions to $$x_1+x_2+\dots +x_{m-q+1}=q$$ such that there is at least one part is not less than $n$. Hence, $$\binom{q+(m-q+1)-1}{(m-q+1)-1}-R(q,m-q+1,n)$$ gives the required answer.