A string is chosen uniformly at random from the set of all binary strings of length n. Show that the expected number of zeroes is n/2

Question

This was a problem on a past exam.

A string is chosen uniformly at random from the set of all binary strings of length $n$. Show that the expected number of zeroes in the string is $\frac{n}{2}$.

Can someone please provide a proof?

Answer 1

The expectation of the total amount of zeros on a string of length $n$ equals to the sum of the expectations of the amount of zeros at any position, by linearity of expectation. However, the expected amount of zeros at a given index is simply $1\over2$, so that the expectation you’re asking for is $$n\cdot\frac12=\frac n2.$$ $\blacksquare$

Answer 2

Alternatively, the number of 0's follows a binomial distribution $\mathcal{B}(n, p)$ where $n$ is the length of the string and $p=0.5$ (since, each character in the string has a 50/50 chance of being a 0 or a 1). The expected value of a binomial distribution is $np$ which, in this case, is $n\times0.5$ or $\frac{n}{2}$.

Answer 3

The number of $0$s in an $n$-bit string is a binomial variate with probability of success $p=P(0)=P(1)=1/2$. The expectation is given by $np=n/2$, and the variance by $np(1-p)=n/4$.

Answer 4

Let $X$ be the number of zeros in a string. Then $P(X=k)=2^{-n}\binom{n}{k}$ for $0\leq k\leq n$. The expected number of zeroes in the string equals $$ \begin{align} \sum_{k=0}^nk P(X=k)=\sum_{k=0}^n k \frac{1}{2^n}\binom{n}{k}&=2^{-n} \sum_{k=1}^n\binom{n}{k}\binom{k}{1}\\&=2^{-n} \sum_{k=1}^nn\binom{n-1}{k-1}\tag{0}\\ &=n2^{-n}\sum_{u=0}^{n-1}\binom{n-1}{u}\\ &=n2^{-n}2^{n-1}\tag{1}\\ &=n/2 \end{align} $$ where in (0) we used the fact that $$ \binom{n}{k}\binom{k}{1}=\binom{n}{1}\binom{n-1}{k-1} $$ and in (1) we used the binomial theorem.