Binary Sequences of Length 2n

Question

I had posted an urn probability problem that didn't have good motivation. I'd like to try to explain the motivation here, and reintroduce the problem.

Consider binary sequences of length $2n$. Let's say we put a marker in such a sequence as soon as we see a total of $n$ 0's or $n$ 1's, reading left to right. For example, if $n=4$, then the sequence 00101011 would receive a marker thus: 001010|11. Now write down the bits to the right of the marker. In the case of our example, this would be 11. Do this for every binary sequence of length $2n$. We observe that we have written down $2n\binom{2n}{n}$ bits, half 0's and half 1's. It is possible to prove this observation using binomial coefficient identities, but I wonder whether there is a simple bijective proof.

The previous urn problem was an equivalent probabilistic formulation of the case $n=5$.

Answer 1

Given the symmetry between 0 and 1 past the end of the first "run" of n equal digits, it does not matter whether we count zeros or ones after a "run" of n zeros. That is, if we only count zeros after n zeros and ones after n ones, we should get $n\binom{2n}{n}$. This count is the total number of excess (over n) digits in all the bit patterns of length 2n, and these are split evenly between zeros and ones, denote by $S=\sum_{k=0}^{n}k\binom{2n}{n+k}$ this half-count.

We have $\binom{2n}{n+k}(n+k) = \binom{2n}{n+k-1}(n-k+1)$ -- both are the number of partitions of 2n elements into sets of size n+k-1, n-k and 1. Hence $$S+\sum_{k=0}^{n} n\binom{2n}{n+k} = \sum_{k=0}^{n} \binom{2n}{n+k}(n+k) = \sum_{k-1=-1}^{n-1} \binom{2n}{n+(k-1)}(n-(k-1)) =$$ $$= \sum_{k-1=-1}^{n} \binom{2n}{n+(k-1)}(n-(k-1)) = \binom{2n}{n-1}(n+1) + \sum_{k=0}^{n} n\binom{2n}{n+k} - S$$ and we have $2S=(n+1)\binom{2n}{n-1} = n\binom{2n}{n}$ as required.

This is essentially counting all zeros in the patterns which have an excess of zeros with weight -1 and all ones in the patterns which have at least as many ones as zeros with weight +1, and noticing that we get $n\binom{2n}{n}$ by straight counting (only the n+n patterns are not pairwise annihilated with their complementary sequence) on one hand and $2S$ on the other hand (we can pair a bit pattern with a selected majority digit with a pattern with a selected minority digit and count each excess majority digit twice in doing so).

Answer 2

To see that you should get half 0s and half 1s: flip all the bits in a string which ends in k 1's and get a string that ends in k 0's. For example, 001010|11 is paired with 110101|00.

I'm not sure how to show bijectively that there are $n {2n \choose n}$ of each, though.

Answer 3

Let's say we consider the set of strings in which we see $n$ zeros first (by symmetry, this should be half the total number). Fix the number of 1s also encountered to be $k$. then the total remaining number of bits is $n-k$, and so we can see all possible strings on n-k bits, each of which is of length $n-k$.

But there are $\binom{n+k-1}{k}$ ways of placing the $k$ ones to give distinct prefixes, and so the desired sum appears to be (replacing $k$ by $n-i$) $$ \sum_{i=0}^n i 2^i \binom{2n-i-1}{n-i}$$

I'm not adept enough at manipulating binomial identities to figure out what this should be.