Skip to main content
4 of 4
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Binary Sequences of Length 2n

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