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.