2
$\begingroup$

Suppose you generate an $N$-bit string (composed of only $1$'s and $0$'s). The sum of all of these $0$'s and $1$'s is $X$.

  • What is the probability that $X$ is odd, if $N$ is odd?
  • What is the probability that $X$ is odd, if $N$ is even?

Since the chance of any bit being a $0$ or $1$ is $50\%$, I would just assume that both answers are $50\%$. However, I don't think this is quite right. Can I get some ideas on how to solve this problem? Any help would be greatly appreciated.

4 Answers 4

4

After you have generated $N-1$ bits, the chance that the next bit makes $X$ odd or even is 50%.

  • 0
    @David: $N=1$ is fine.2012-05-02
2

The easiest way of seeing it is probably through a reflection argument: for every string with digit-sum even, there's another one with digit-sum odd (just flip the first digit), and vice versa - therefore their numbers must be identical, and the probability that a random string belongs to either one is 1/2.

This can be turned into a pretty straightforward recursive argument, too; let $P^n_{odd}$ be the probability that an $n$-digit string has odd digit sum, and $P^n_{even}$ be the probability that it has even digit-sum. Obviously for $n=1$ then $P^1_{odd} = P^1_{even} = \frac{1}{2}$; and for each $n$ $P^{n+1}_{odd} = \frac{1}{2}P^n_{odd} + \frac{1}{2}P^n_{even}$, so if $P^n_{odd} = \frac{1}{2}$ (and thus $P^n_{even} = \frac{1}{2}$) then $P^{n+1}_{odd} = \frac{1}{2}(\frac{1}{2}) + \frac{1}{2} (\frac{1}{2}) = \frac{1}{4}+\frac{1}{4} = \frac{1}{2}$.

1

Let $A$ be the set of bit positions that are $1$; the sum is even or odd according as $|A|$ is even or odd, so the problem really amounts to comparing the numbers of even- and odd-sized subsets of $\{1,\dots,N\}$. It's well known (and easy to prove, e.g., by induction) that for $N>0$ the set $\{1,\dots,N\}$ has equal numbers of even- and odd-sized subsets, so the probability is indeed $1/2$ in both cases.

1

For a more concrete approach: $X$ follows a binomial distribution with parameters $(N,1/2)$, so the probability that $X=r$ is equal to ${N \choose r} \frac{1}{2^N}$.

Consider $0 = (\frac{1}{2}-\frac{1}{2})^N = {N \choose 0} \frac{1}{2^N} - {N \choose 1}\frac{1}{2^N} + \ldots + (-1)^{N-1} {N \choose N-1} \frac{1}{2^N} + (-1)^N {N \choose N} \frac{1}{2^N}$. Notice that the negative terms sum to the probability that $X$ is odd, and the positive terms sum to the probability that $X$ is even. Since these cancel to give 0, they must be equal, so must both be 1/2.