Probability of even sum of $n$ integers with uniform distribution from $\{1,2,\dots, 2n\}$.

Question

Choosing with Uniform distribution $n$ numbers from $\{1,\dots,2n\}$ with returns and the order is important. What is the probability that the sum of these number will be even?

Thanks.

Answer 1

You can prove that the answer is $1/2$ by induction. Denote with $E_n$ the event that after $n$ draws the sum is even.

• Base case: $n=1$. You draw $1$ number from $\{1,2\}$. Obviously, the probability that the sum is even, is equal to the probability that you draw $2$, is equal to $1/2$, i.e. $$P(E_1)=\frac12$$
• Induction step. Assume this holds for $n$, i.e. that $P(E_n)=\frac12$. Then for $n+1$ you draw $n+1$ numbers from $\{1,2,\dots, 2n+2\}$. Hence \begin{align}P(E_{n+1})&=P(E_{n+1}\mid E_n)P(E_n)+P(E_{n+1}\mid E_n^c)P(E_{n}^c)\\[0.2cm]&=P\left(\text{draw even number from}\{1,2,\dots, 2n+2\}\mid E_n\right)\frac12\\[0.2cm]&\phantom{.}+P\left(\text{draw odd number from} \{1,2,\dots, 2n+2\}\mid E_n^c\right)\frac12\\[0.2cm]&=\frac12\frac12+\frac12\frac12=\frac12\end{align}

Note that order did not play a role.

Answer 2

If a number can appear more than once, then this is easily seen to be $\frac12$. You can see this if you stop to catch your breath after you've drawn the first $n-1$ numbers. Then you realize that whether the total sum will become even or odd depends only on whether the last number (that you haven't drawn yet) is even or odd (the sum might end up having the opposite parity of the last number, if the sum of the first $n-1$ numbers is odd, but that doesn't change things).

Since the last number has equal odds of being even or odd, the whole sum has equal odds of being even or odd.