There are two rows of 10,000 bits, one on top of the other, currently all set to 0.
00000000000000000...
00000000000000000...
Now imagine that in each row, 40 of the bits are randomly flipped to a 1. My question is, given that the first 20 ones in the top row line up perfectly with the first 20 in the bottom row: (probably a lot more spaced out with 10,000 indices)
0100000110001010010...
0100000110001010010...
what is the probability that ALL of the 40 bits that are 1 in the top row occur in the same indices as the ones in the bottom row?
More generally, if k bits out of n total (n > k) are randomly flipped to one, and it is given that the first x ones occur in the same place in each row, what is the chance that all k ones occur in the same place? Thanks guys!
Hint: Consider the $1$'s in the top string fixed and count the number of ways to place the $1$'s in the lower string. There are $10,000-20$ bits which are unknown. Of those exactly $20$ are $1$'s. There are $\binom{10,000-20}{20}$ ways to put those $1$'s into the bottom string. Each of those placements are equally likely... and only 1 of those lines up perfectly with the top string.
Can you take it from here?
In general, if there were $N$ bits total, $n$ bits to be $1$'s and $k$ bits already set to $1$, then instead of $\binom{10,000-20}{20}$ you would have $\binom{N-k}{n-k}$.