Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

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

share|improve this answer
    
Unless $N = 1$. –  David Harris May 2 '12 at 22:11
    
@David: $N=1$ is fine. –  Brian M. Scott May 2 '12 at 22:15
add comment

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}$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.