6
$\begingroup$

We have the numbers $1$ through $10$ in a box, we pick one at random, write it down and put it back in the box. We pick another of those numbers at random and write it down again. If we add the two numbers, what is the probability that it will be greater than $5$?

At first I though that I could count the number of ways we could add two numbers to get six, i.e. $2+4$ and see what are the chances to get numbers bigger than those choices. Then adding all the probabilities that relate to each way. However, I get numbers greater than $1$ which is impossible. I also thought about the chance of getting a $1$ and then a number equal to or bigger to $5$, $P(x \ge 5) = \frac 12$ multiplying them together and repeating until all numbers run out. Again, wrong answer.

My question is: how do we get to the correct answer? Is it possible to generalize? Say that the probability of $n$ numbers picked at random from $N$ choices add to something greater than $k$.

$\endgroup$
7
$\begingroup$

In this case, it is easier to find the probability $p$ that the sum is $\le 5$. Then the answer to the original problem is $1-p$.

We can list and count the ordered pairs $(a,b)$ of numbers that have sum $\le 5$.

If $a=1$ there are $4$, if $a=2$ there are $3$, and so on down to $1$.

So there are $10$ ordered pairs. Each has probability $\frac{1}{10^2}$, so $p=\frac{10}{10^2}$.

Remark: The same idea will work in your general case, as long as $k\le n+1$. A modification will take care of the rest of the $k$.

$\endgroup$
3
$\begingroup$

I would start with looking at each case and then derive the probability: The first column states the number at first pick, and the second the number that is needed at least during 2nd pick to have $>5$. The third shows the probability for the given case:

1  5 = 1/10 * 6/10
2  4 = 1/10 * 7/10
3  3 = 1/10 * 8/10
4  2 = 1/10 * 9/10
5  1 = 1/10 * 10/10
6  0 = 1/10 * 10/10
7  0 = 1/10 * 10/10
8  0 = 1/10 * 10/10
9  0 = 1/10 * 10/10
10 0 = 1/10 * 10/10

So the whole probability is

$p = 6/100 + 7/100 + 8/100 + 9/100 + 6 * 1/10 = 9/10$

From this, you can derive a general formula for arbitrary $n$ and $k$:

$p = {1\over n^2} ((k + 1) + \dots + n) = {n^2-{k(k-1)\over2}\over n^2} = 1 -{k(k-1) \over 2n^2}$

$\endgroup$
3
$\begingroup$

You could solve this with generating functions. The generating function for this situation, equivalent to rolling a fair 10-sided die twice, is:

$$(x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})^2$$

which expands to

$$x^2 + 2 x^3 + 3 x^4 + 4 x^5 + 5 x^6 + 6 x^7 + 7 x^8 + 8 x^9 + 9 x^{10} + 10 x^{11} + 9 x^{12} + 8 x^{13} + 7 x^{14} + 6 x^{15} + 5 x^{16} + 4 x^{17} + 3 x^{18} + 2 x^{19} + x^{20}$$

The coefficient of each $x^n$ is the number of ways of getting a sum of $n$ from the two random draws. There are 100 total possibilities ($10 \cdot 10$) with two draws from 1...10 with replacement. Looking at the polynomial above, the coefficients of the monomials $x^2$ through $x^5$ show that there are a total of 10 ways to get a sum of 5 or less. Thus, the probability of a sum greater than 5 is 90/100 or 0.9.

Perhaps a simpler way is to first eliminate the cases where at least one draw is 5 or greater, since these guarantee a sum greater than five. There are 84 of these, leaving only the 16 cases in which both draws are 4 or less. This can also be done with a generating function (though counting manually is easy too):

$$(x + x^2 + x^3 + x^4)^2 = x^2 + 2 x^3 + 3 x^4 + 4 x^5 + 3 x^6 + 2 x^7 + x^8$$

once again giving 10 out of 100 cases where the sum is 5 or less.

$\endgroup$
  • $\begingroup$ Wow, what is the exact name of this method of generating functions applied on probabilities? Nice stuff, I'd like to read more on it. Would this be easily generalizable? $\endgroup$ – Guacho Perez Jan 24 '16 at 6:01
  • $\begingroup$ I like the introduction to generating functions in Paul Zeitz's text The Art and Craft of Problem Solving (FYI, a new edition is coming out soon). There are also lots of materials on the web. Here, here, and here, for example. $\endgroup$ – eipi10 Jan 24 '16 at 6:28
  • $\begingroup$ Also see the book Generatingfunctionology. $\endgroup$ – eipi10 Jan 24 '16 at 6:30
1
$\begingroup$

The general case can be handled formally as follows. Define $P(X_1)=...=P(X_n)=1/N$. Then $$ \mathbb{P}\left(\sum_i X_i>k\right)=\sum_{r=k+1}^{Nn} \mathbb{P}\left(\sum_i X_i=r\right)=\sum_{r=k+1}^{Nn} \sum_{\bf X} P(X_1)\cdots P(X_n)\delta_{\sum_i X_i,r}\ , $$ where $\delta_{a,b}$ is the Kronecker delta, and $\sum_{\bf X}$ stands for the sum over all possible values taken by all variables $X_i$. Therefore you get $$ \frac{1}{N^n}\sum_{r=k+1}^{Nn}\int_0^{2\pi}\frac{d\xi}{2\pi}e^{\mathrm{i}r\xi} \sum_{\bf X}e^{-\mathrm{i}\xi\sum_{i=1}^n X_i}=\frac{1}{N^n}\sum_{r=k+1}^{Nn}\int_0^{2\pi}\frac{d\xi}{2\pi}e^{\mathrm{i}r\xi} \left(\sum_{X_1}e^{-\mathrm{i}\xi X_1}\right)^n\ , $$ where I used the integral representation of the Kronecker delta, and the fact that the draws are independent. Specializing to our case with $n=2$ and $N=10$, we get $$ \frac{1}{10^2}\sum_{r=6}^{20}\int_{0}^{2\pi}\frac{d\xi}{2\pi}e^{\mathrm{i}r\xi}\left(\sum_{j=1}^{10}e^{-\mathrm{i}\xi j}\right)^2=90/100\ . $$

$\endgroup$
0
$\begingroup$

The generalisation of calculating probabilities for sums of random variables is done through convolution, so that is the term to look up if you're interested in this.

Your first idea was good, but maybe you've made a mistake at calculating the probabilities before you add them. The probability to obtain 6 for example is:

$P( (5,1) ) + P((4,2)) + P((3,3)) +... =$

$P(5)\cdot P(1)+ ... =$

$0.01 + ...=$

So you're allowed to add probabilities if they stand for disjoint events, i.e. events that cannot occur at the same time. The probability of obtaining two specific numbers for two draws independently is obtained through multiplication.

$\endgroup$

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.