Take the 2-minute tour ×

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$.

share|improve this question
(I added a link to the earlier question and I reformatted a little for readability.) –  François G. Dorais Jun 28 '10 at 17:40

3 Answers 3

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).

share|improve this answer

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.

share|improve this answer
Note that the digits after the marker need not be all 1s or all 0s, because the original string needn't have an equal number of 1s and 0s. This doesn't affect your answer, but it's important to remember when you're trying to solve the bigger question. –  Jonah Ostroff Jun 29 '10 at 1:20
I don't think Martin was asking for a proof of the fact that half are 0's and half are 1's. That part is pretty obvious from symmetry. For every bit sequence being considered, so is its complement. So the counts of 1's and 0's to the right of marker, when summed over all the possible bit strings, will be the same. –  I. J. Kennedy Jun 29 '10 at 5:25
Jonah, you're right. I was misled by the example string which did have an equal number of 0s and 1s. –  Michael Lugo Jun 29 '10 at 14:38

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.

share|improve this answer

Your Answer


