Say for every natural number z $\ge$ 1, we choose a number $a_z$ from the set {${1,...,z}$} randomly with equal probability for each number 1 to z. For example, $a_3$ we can choose 1, 2, or 3 all with probability 1/3. If b $\ge$ 2 what is the probability that the sum of $a_1$ + ... + $a_b$ is even for any b.

I know that whenever b is an even number the probability that the number chosen is odd is 1/2. I tried to use the fact that $a_1$ has to be 1 to try to see when I can have the sum of two odds since that is even. However, I am stuck on figuring out the probability that the entire sum is even.

  • $\begingroup$ Why did you delete all the text in the question? I have rolled it back to your original. $\endgroup$ – Henry Mar 10 at 17:47

Let's call the sum $S_b = a_1+a_2+\cdots+a_{b-1}+a_b$.

If $b$ is even and $b\ge 2$ then the probability is $\frac12$ that $a_b$ is odd and so changes the parity of the sum, and $\frac12$ that $a_b$ is even and so does not change the parity of the sum, making the probability that $S_b$ is odd or even $\frac 12$ each.

If $b$ is odd then $b-1$ is even. So as long as $b-1\ge 2$, we can now say $S_{b-1}$ is equally likely to be odd or even. Meanwhile $a_b$ is odd with probability $\frac{b+1}{2b}$ and even with probability $\frac{b-1}{2b}$. So the probability $S_b$ is even given $b$ is odd and $b\ge 3$ is $\frac12 \frac{b+1}{2b}+\frac12 \frac{b-1}{2b}= \frac12$ too.

That leaves the cases $b=0$ and $b=1$, which are easy to handle.

  • When $b=0$ then $S_0=0$ and even (the empty sum) so $\mathbb P(S_0 \text{ is even})=1$.
  • When $b=1$ then $S_0=1$ and odd so $\mathbb P(S_1 \text{ is even})=0$.
  • When $b\ge 2$ then $\mathbb P(S_b \text{ is even})=\frac12$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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