If you have a random binary string of length $2n$. What is the probability that every substring of length $n$ has the same number of $1$s and $0$s? We can assume $n$ is even.
For one substring this is just ${n \choose n/2} 1/2^{n}$.
Asked
Active
Viewed 114 times
1 Answers
2
Look at the first $n$ bits $b_1,\ldots, b_n$. There are $n\choose n/2$ allowed substrings. The next substring $b_2,\ldots, b_{n+1}$ will match the condition iff $b_{n+1}=b_1$. This goes on, i.e. all the rest is determined by the first $n$ bits. Thus the overall probability is good divided by all = $$ {n\choose n/2}\frac 1{2^{2n}}.$$
Hagen von Eitzen
- 374,180