5
$\begingroup$

I'm concerned with the total number of ones, and the total number of runs, but not with the size of any of the runs.

For example, $N=8$, $R=3$, $C=5$ includes 11101010, 01101011 among the 24 total possible strings.

I can compute these for small $N$ easily enough, but I am specifically interested in the distribution for $N=65536$. As this will result in very large integers, the log probability distribution is equally useful.

I found [1] and [2], which includes this:

Let $N_{n;g_k,s_k}$ denote the number of binary strings which contain for given $g_k$ and $s_k$, $g_k=0,1,…,⌊\frac{s_k}{k}⌋$, $s_k=0,k,k+1,…,n$, exactly $g_k$ runs of 1’s of length at least $k$ with total number of 1’s (with sum of lengths of runs of 1’s) exactly equal to $s_k$ in all possible binary strings of length $n$.

An expression for this is given in eq. (24):

$N_{n;g_k,s_k} = \sum_{y=0}^{n-s_k} {y+1 \choose g_k } {s_k-(k-1)g_k-1 \choose g_k-1} \sum_{j=0}^{⌊\frac{n-y-s_k}{k}⌋} (-1)^j {y+1-g_k \choose j} {n-s_k-kj-g_k \choose n-s_k-kj-y} $

for $g_k \in \{1, ..., ⌊\frac{s_k}{k}⌋\}$, $s_k \in \{k, k+1, ..., n\}$.

I think this is exactly what I'm looking for, with $k = 1$, $s_k = C$ and $g_k = R$. However, when I implemented this I did not get the expected results (Python shown below, edge cases omitted), based on comparing to counting all strings for N=8. I am working backwards to try to understand where I might have gone wrong, but not having much luck yet. I wonder if I am misunderstanding the result.

def F(x, y, n):
    # x = C or s_k (cardinality)
    # y = R or g_k (runCount)
    # n = N (total bits)

    a1 = 0
    for z in range(n-x+1):
        b1 = choose(z+1, y) * choose(x-1, y-1)
        a2 = 0
        for j in range(n-z-x+1):
            a2 += (-1) ** j * choose(z+1-y, j) * choose(n-x-j-y, n-x-j-z)
        a1 += b1 * a2

    return a1

Note that the choose function uses factorial, which I realize won't work for larger $N$ - but should be fine for $N=8$.

Edit: corrected a sign error typo in eq. (24) and the equivalent error in the python code.

[1] Counting Runs of Ones and Ones in Runs of Ones in Binary Strings, Frosso S. Makri, Zaharias M. Psillakis, Nikolaos Kollas https://file.scirp.org/pdf/OJAppS_2013011110241057.pdf

[2] On success runs of a fixed length in Bernoulli sequences: Exact and asymptotic results, Frosso S.Makria, Zaharias M.Psillakis http://www.sciencedirect.com/science/article/pii/S0898122110009284

$\endgroup$
10
  • $\begingroup$ so compositions of C with R parts, and hamming weight of binary strings may help. $\endgroup$
    – user451844
    Aug 13, 2017 at 0:21
  • 3
    $\begingroup$ A quick bit of combinatorial reasoning gets me the result for binary strings length $N$ with $C$ 1's and $R$ runs of 1's as $$\binom{C-1}{R-1}\binom{N-C+1}{R}$$ This checks out for N=8, R=3, C=5 giving $\binom{4}{2}\binom{4}{3}=2\cdot3\cdot 4=24$. However, I haven't checked this rigorously. $\endgroup$
    – N. Shales
    Aug 13, 2017 at 1:25
  • 1
    $\begingroup$ @N. Shales: I spot checked your formula for a lot of different values up to about N=24, various R and C and it checks out. $\endgroup$
    – Joe Knapp
    Aug 13, 2017 at 17:51
  • 1
    $\begingroup$ Thank you @JoeKnapp for putting the time in to check my formula! Much appreciated. If anyone is interested see G.Cab's great answer below for the reasoning which is essentially uses the same thought process I used. $\endgroup$
    – N. Shales
    Aug 13, 2017 at 19:39
  • $\begingroup$ Concerning the link you give, it seems that it does not correspond with the formula you cite: can you pls. check it? $\endgroup$
    – G Cab
    Aug 13, 2017 at 20:50

2 Answers 2

5
$\begingroup$

runs_ones_1

Consider a binary string and let's put an additional (dummy) fixed $0$ at the start of the it. We individuate as a run a $0$ followed by contiguous $1$'s.

So, given a string of length $N$, total of ones $C$, and number of runs $R$, we will have $N-C$ zeros, of which $N-C-R+1$ are "free", that is not tight to mark the runs.

The number of ways to constitute the runs is the number of (standard) compositions of $C$ into $R$ parts, that is $$ {{C-1} \choose {R-1}}$$.
The number of ways to place the "free" zeros will be equal to the number of weak compositions of their number into $R+1$ parts (in front of the first and then after each run), i.e.: $$ {{N-C-R+1+R+1-1} \choose {R}}={{N-C+1} \choose {R}}$$.

Which confirms N.Shales's answer, so that the merit should go to him.

Addendum

Concerning formula (24), for what I can see, it looks like that in the 3rd binomial ${{y+1+g_k} \choose {j}}$ there is a sign typo, and that it should be $\cdots -g_k$.
Then putting for instance $k=1,\; s_k=n-1 \; g_k=2$ it will correctly give $n-2$,
and with $k=1,\; s_k=C \; g_k=R$ it will give the formula above.
But not having the full text, I cannot check that further.

$\endgroup$
6
  • $\begingroup$ Thank you! However you surely deserve the credit for the excellent explanation, which is pretty much how I reasoned. $\endgroup$
    – N. Shales
    Aug 13, 2017 at 19:45
  • 1
    $\begingroup$ @N.Shales: unfortunately you did post your answer, otherwise I would have been glad to appraise it: hope to have other chances to do that. And in any case, morally, you have given the correct answer first. $\endgroup$
    – G Cab
    Aug 13, 2017 at 20:14
  • $\begingroup$ Great, simple and straightforward. I had another bit of code that, had I thought about its meaning, would have led me to a similar answer. Then I found those papers and thought I might be missing something, but I suppose they were overkill for the k=1 case. $\endgroup$
    – monguin
    Aug 13, 2017 at 21:03
  • 1
    $\begingroup$ @monguin: see the addendum to my answer. $\endgroup$
    – G Cab
    Aug 14, 2017 at 20:47
  • 1
    $\begingroup$ Good catch, the sign error was mine. $\endgroup$
    – monguin
    Aug 15, 2017 at 2:38
3
$\begingroup$

Perhaps there is some value in solving this with generating functions. In the present case we have the marked generating function using $z$ for ones and $w$ for zeros and $y$ for runs of ones

$$(1+y(z+z^2+z^3+\cdots)) \\ \times \left(\sum_{q\ge 0} (w+w^2+w^3+\cdots)^q y^q (z+z^2+z^3+\cdots)^q\right) \\ \times (1+w+w^2+w^3+\cdots).$$

This is

$$\left(1+\frac{yz}{1-z}\right) \times \left(\sum_{q\ge 0} \frac{w^q}{(1-w)^q} y^q \frac{z^q}{(1-z)^q}\right) \times \frac{1}{1-w} \\ = \left(1+\frac{yz}{1-z}\right) \times \frac{1}{1-ywz/(1-w)/(1-z)} \times \frac{1}{1-w}.$$

Extracting the coefficient on $[y^R]$ for $R$ runs we get

$$\frac{w^R z^R}{(1-w)^R (1-z)^R} \frac{1}{1-w} + \frac{z}{1-z} \frac{w^{R-1} z^{R-1}}{(1-w)^{R-1} (1-z)^{R-1}} \frac{1}{1-w}.$$

Next do the coefficient on $[z^C]$ for $C$ ones

$$[z^{C-R}] \frac{w^R}{(1-w)^R (1-z)^R} \frac{1}{1-w} + [z^{C-R}] \frac{w^{R-1}}{(1-w)^{R-1} (1-z)^{R}} \frac{1}{1-w} \\ = {C-1\choose R-1} \frac{w^R}{(1-w)^{R+1}} + {C-1\choose R-1} \frac{w^{R-1}}{(1-w)^{R}}.$$

Finally extract $[w^{N-C}]$ for the remaining zeros:

$${C-1\choose R-1} [w^{N-C-R}] \frac{1}{(1-w)^{R+1}} + {C-1\choose R-1} [w^{N-C-R+1}] \frac{1}{(1-w)^{R}} \\ = {C-1\choose R-1} {N-C\choose R} + {C-1\choose R-1} {N-C\choose R-1} \\ = {C-1\choose R-1} {N-C+1\choose R}.$$

This confirms the accepted answer, no credit claimed here.

$\endgroup$
4
  • $\begingroup$ I wouldn't have known how to start this, could you recommend a resource for understanding how to use generating functions to solve this kind of problem? $\endgroup$
    – monguin
    Aug 13, 2017 at 21:43
  • 1
    $\begingroup$ A generic resource for generating functions is the book by Wilf, Generatingfunctionology. $\endgroup$ Aug 13, 2017 at 21:47
  • $\begingroup$ Interesting to get the odf for this problem. However I cannot catch immediately its "construction" (your starting formula). Can you explain better, thanks $\endgroup$
    – G Cab
    Aug 13, 2017 at 22:02
  • $\begingroup$ This is the regular expression $1^*(0^+1^+)^*0^*.$ $\endgroup$ Aug 13, 2017 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .