Probability that random $n/2$ Hamming weight $n$-bitstring has a particular $k$ bit substring Let $x\in \{0,1\}$ be a random $n$-bit string with Hamming weight $n/2$. (Suppose $n$ is even.) There are $\binom{n}{n/2}$ many such bitstrings.
I am interested in the probability that some $k\ll n $ bits (say WLOG the first $k$ bits) are equal to a fixed $k$-bitstring $y \in \{0,1\}^k$, i.e.
$$\mathrm{P}\left(x_{1:k} = y\right)$$
In the paper, I am reading, the following bound is given: For any $y$, we have that the probability is at most
$$\mathrm{P}\left(x_{1:k} = y\right)\leq \frac{n/2}{n}\times\frac{n/2}{n-1}\times\dots \times \frac{n/2}{n-(k-1)}$$
I cannot wrap my head around why this holds, please explain!
 A: An equivalent question is this:

You have a shuffled deck of $n$ cards, where half of the cards are labeled with "0", and the other half with "1". When you deal $k$ cards from this deck in a row, what is the probability that the string of card faces spells out the word $y$?

Using this paradigm, let us focus on the particular case $k=5$ and $y=$ 01101.

*

*The probability that the first card you deal is zero is $\frac{n/2}{n}$, since there are $n/2$ zeroes in the deck, and $n$ cards total.


*Given the first letter is 0, the probability that the second card you deal is one is $\frac{n/2}{n-1}$, since there are $n/2$ ones in the deck, and $n-1$ remaining cards in the deck.


*Given the first two letters are 01, the probability that the third card you deal is one is $\frac{n/2-1}{n-2}$, since there are $n/2-1$ ones remaining in the deck, and $n-2$ remaining cards in the deck.


*Given the first three letters are 011, the probability that the fourth card you deal is zero is $\frac{n/2-1}{n-3}$, since there are $n/2-1$ zeroes remaining zeroes in the deck, and $n-3$ remaining cards in the deck.


*Given the first four letters are 0110, the probability that the fifth card you deal is one is $\frac{n/2-2}{n-4}$, since there are $n/2-2$ ones remaining ones in the deck, and $n-4$ remaining cards in the deck.
Putting those altogether, the probability that the observed word is 01101 is
$$
\frac{n/2}{n}\times\frac{n/2}{n-1}\times\frac{n/2-1}{n-2}\times\frac{n/2-1}{n-3}\times \frac{n/2-2}{n-4}
$$
To get the bound in the paper you are reading, simply replace all of the numerators with the upper bound of $n/2$.
