# Probability that the sum of randomly selected integers from a (random) set S is odd even?

How can I approach questions like this?

Problem:

Let $S$ be a finite set of random positive integers. What is the probability that the sum of $N$ randomly selected integers from this set $S$ is even?

Does the answer depend on $N$ (i.e., depending on whether $N$ is even or odd) or is it always equal to 1/2.

-
If all the numbers in S are even, the odds are very good. If all the numbers in S are odd, it depends on the parity of N. – Ross Millikan Aug 5 '12 at 15:02
Set S contains random positive numbers. I missed this part in question :) – Sharad Dixit Aug 5 '12 at 15:05
@RossMillikan Means answer of such questions can't be evalutated ? correct me if i am wrong . – Sharad Dixit Aug 5 '12 at 15:12
@Sharad: Please put all relevant information in the question. People shouldn't have to dig through the comments to understand the question. Above in a comment you write that $S$ contains random numbers. That information is not in the question -- also you'll need to specify a distribution to make the question well-defined. – joriki Aug 5 '12 at 15:14
There is not a single answer. The probability cannot be calculated without more information. – Ross Millikan Aug 5 '12 at 15:18

You can work $\pmod 2$ as you only care about even or odd. If you are asking about the probability for a randomly selected set $S$, then the probability is in fact $\frac 12$. In fact the set $S$ is a red herring-you can just think about flipping a coin, with heads giving an even number and tails giving an odd one. If $N=0$, the probability of an odd number of tails is $0$. But if $N$ is any greater, the chance of an odd number of tails is $\frac 12$, which you can prove by induction.

-
You mean "If $N=0$, the probability of an odd number of tails is $0$". – Robert Israel Aug 5 '12 at 17:14
@RobertIsrael: Thanks. – Ross Millikan Aug 5 '12 at 17:20

The problem with your question is that we don't know how $S$ is distributed. Are the integers uniform, and if so within what range? Or are they distributed according to another probability distribution?

In truth, because you specify that all elements of $S$ are integers, we don't really need the entire probability distribution, just: the number $n_o = |S_o|$ of integers which are odd, and the size of the set $n=|S|$...

Then, supposing that you are sampling the elements without replacement (i.e., you cannot take the same element twice), then your probability of the sum being odd, is the probability of drawing an odd number of odd numbers. Thus it's the sum on all odd values of a hypergeometric distribution.

UPDATE: here are more details and a nice illustration.

We are defining an hypergeometric random variable $O$, the total size of the population is $n$ (the size of the set), the size of successes is $n_o$, the size of our sample is $m$ (what you call $N$).

The probability of being odd is:

$$\sum_{i=0}^n \mathbb{P}[O=2i+1]=\sum_{i=0} \frac{\binom{n_o}{2i+1}\binom{n-n_o}{m-(2i+1)}}{\binom{n}{m}}$$

(where the binomial coefficient is zero where there parameters are non-sensical :-)

Interestingly there is a regime where this probability is $1/2$ but it is not necessarily so, as illustrated by the following example. Take a sample of size $n=100$. Below is the plot of the probability of having an odd sum from drawing $m$ integers ($m$ is the $x$-axis, and the probability is the $y$-axis). As time goes by, we add more and more odd numbers to the set (first there are none, so the probability is always 0 then there is 1 so the probability of the sum being odd is equal to the probability of drawing that number, etc.).

As all integers are odd, then the probability of having an odd sum (since all integers are odd) depends deterministically on the size $m$ of the sample, hence the final saw-shaped plot.

(Plot of the probability that the sum of $m$ integers taken from $S$ is odd. The size of $S$ is $n=100$; $m$ varies on the $x$-axis from $0$ to $100$; each successive plot is $n_o$, the number of odd elements in the set $S$, varying from $0$ to $100$.)

MINOR EDIT: I accidentally called $n_e$ the number of odd elements... changed that to $n_o$.

-

If the numbers are replaced after being picked and they are picked uniformly at random, then the answer is straightforward.

Let $n_j$ denote the $j^{th}$ number picked, $a$ denote the number of numbers in $S$, $a_o$ denote the number of odd numbers in $S$ and let $X_i= 1$ if $\sum^i_{j=1}n_j$ is odd, $X_i = 0$ otherwise.

The probability of the first number being odd is simply the number of odd numbers divided by the total amount of numbers, $P(X_1 = 1) = \frac{a_o}{a}$. Then, $P(X_1 = 0) = 1-P(X_1 = 1)=\frac{a-a_o}{a}$. Now notice,

$P(X_{i+1} = 1 | X_i = 1) = P(X_{i+1} = 0 | X_i = 0) = P(${$n_i$ was even}$) = \frac{a-a_o}{a}$.

Similarly,

$P(X_{i+1} = 1 | X_i = 0) = P(X_{i+1} = 0 | X_i = 1) = P(${$n_i$ was odd}$) = \frac{a_o}{a}$.

By the total rule of probability and bayes rule,

$P(X_{i+1} = 1) = P(X_{i+1} = 1 | X_i = 1)P(X_i = 1) +P(X_{i+1} = 1 | X_i = 0)P(X_i = 0) = \frac{a-a_o}{a}P(X_i = 1)+ \frac{a_o}{a}P(X_i = 0)$, $P(X_{i+1} = 0) = P(X_{i+1} = 0 | X_i = 1)P(X_i = 1) +P(X_{i+1} = 0 | X_i = 0)P(X_i = 0)= \frac{a_o}{a}P(X_i = 1)+ \frac{a-a_o}{a}P(X_i = 0)$,

or more compactly,

$\begin{bmatrix} P(X_{i+1} = 1)\\ P(X_{i+1} = 0)\end{bmatrix} = \begin{bmatrix} \frac{a-a_o}{a}&\frac{a_o}{a}\\\frac{a_o}{a}&\frac{a-a_o}{a}\end{bmatrix} \begin{bmatrix} P(X_{i} = 1)\\ P(X_{i} = 0)\end{bmatrix}=A\begin{bmatrix} P(X_{i} = 1)\\ P(X_{i} = 0)\end{bmatrix}$ (1).

One then can simply iterate the above expression back to get the desired probabilities;

$\begin{bmatrix} P(X_{N} = 1)\\ P(X_{N} = 0)\end{bmatrix} = A^{N-1} \begin{bmatrix} P(X_{1} = 1)\\ P(X_{1} = 0)\end{bmatrix} = A^{N-1} \begin{bmatrix} \frac{a_o}{a}\\\frac{a-a_o}{a}\end{bmatrix}$.

All that remains is to find a closed form expression for $A^{N-1}$, this can be done in a variety of ways, i.e. see http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors. Alternatively one can use the total rule of probability to obtain a scalar difference equation from the first equation of $(1)$ (i.e. subbing $P(X_i=0)=1-P(X_i=1)$ and solving for $P(X_i)=1$) and then apply again the total rule of probability, plus the fact that if $A$ is symmetric then so is $A^k$ for any integer $k$, to work out the other entries of $A^{N-1}$. The actual solution is given by

$\begin{bmatrix} P(X_{N} = 1)\\ P(X_{N} = 0)\end{bmatrix} = \begin{bmatrix}\frac{1}{2}+\left(\frac{a-2a_o}{a}\right)^{N-1}&\frac{1}{2}-\left(\frac{a-2a_o}{a}\right)^{N-1}\\\frac{1}{2}-\left(\frac{a-2a_o}{a}\right)^{N-1}&\frac{1}{2}+\left(\frac{a-2a_o}{a}\right)^{N-1}\end{bmatrix} \begin{bmatrix} \frac{a_o}{a}\\\frac{a-a_o}{a}\end{bmatrix}$.

So yes the answer does depend on $N$, however notice that as $N$ gets very large this dependence dies out making it equally likely the sum is odd or even. This is a standard discrete time Markov chain question and a brief but excellent introduction to the subject can be found in http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf.

-