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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer
    
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? – Guacho Perez Jan 24 at 6:01
    
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. – eipi10 Jan 24 at 6:28
    
Also see the book Generatingfunctionology. – eipi10 Jan 24 at 6:30
    
In terms of generalizability, generating functions have applications in combinatorics, probability, recurrences, and probably other areas. Zeitz refers to generating functions as a "crossover tactic" because they connect different areas of mathematics. – eipi10 Jan 24 at 6:35

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.