2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is $p+q=m$ here? If not then what is $p$? $\endgroup$
    – drhab
    May 4, 2014 at 16:49
  • $\begingroup$ Sorry, $p$ should have been $q$. To clarify, the third term counts only the good strings which end with exactly $n$ 1's. Hence the last $n+1$ elements are $011\ldots1$. Then we know there must be $(m+1) - (n+1)$ other elements that contain $q-n$ 1's, because there are $q$ 1's in total. So there are $\binom{m-n}{q-n}$ such strings. The fourth term then removes the good strings that were already included in the second term. $\endgroup$
    – G.L.
    May 4, 2014 at 16:59

1 Answer 1

Reset to default
5
$\begingroup$

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 $$R(b,a,k)=\sum_{i=0}^{\lfloor b/k\rfloor}(-1)^i\binom ai\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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.