I am trying to prove, given a random sequence of $2k$ bits, the probability that the sequence contains exactly $k$ ones is less than or equal to $1/2$. I tried ${2k \choose k}/{2^{2k}}=\dfrac{(2k)!}{k!k!2^{(2k)}}=\dfrac{\prod\limits_{i=1}^k (k+i)}{4^kk!}=\prod\limits_{i=1}^k \dfrac{k+i}{4i}$. Then i got stuck.
Asked
Active
Viewed 49 times
2 Answers
0
Let $X=\{0,1\}^{2k}$ be the space of all binary sequences over $\{0,1\}$. This is a vector space over the field with two elements, which I'll denote by $F_2$.
The subset of $X$ consisting of all binary subsets with exactly $k$ ones is contained in the space: $$ Y=\{x=(x_i)_{i=1}^k\in X : \sum_i x_i =k \; in \; F_2\} $$
If $k$ is even, then $Y$ is a subspace of $X$ which is not all of $X$, thus has dimension at most $k-1$. If $k$ is odd, then all the elements of the form $y+(1,0,...,0)$ form a subspace of $X$ of dimension at most $k-1$. In both cases, one finds that:
$$ \#\{binary\; sequences\; with \; k\; ones\}\le|Y|\le2^{k-1} $$
Which implies: $$ Prob(random \; binary \; sequence\;has\;k\;ones)\le \frac{2^{k-1}}{2^k}=\frac{1}{2} $$
Miel Sharf
- 525
0
It suffices to show that the number of ways to get exactly $k$ ones is no greater than the number of ways to get either $k-1$ or $k+1$ ones. We use relationships in Pascal's triangle.
\begin{eqnarray*} \text{#Ways to get $k$ ones} &=& \binom{2k}{k} \\ &=& \binom{2k-1}{k-1} + \binom{2k-1}{k} \qquad\text{(going up one level in the triangle)}\\ &\leq& \binom{2k}{k-1} + \binom{2k}{k+1} \qquad\text{(going back down one level)}\\ &=& \text{#Ways to get $k-1$ or $k+1$ ones.} \end{eqnarray*}
Mick A
- 10,208