Re: Chances of (random(0,n) + random(0,n) <= m)
From: Robert Vienneau (rvien_at_see.sig.com)
Date: 11/03/04
- Next message: Virgil: "Re: operator precedence -3^2 ; 10-3^2"
- Previous message: Ross A. Finlayson: "Re: sci.math.moderated?"
- In reply to: Brendan Sechter: "Chances of (random(0,n) + random(0,n) <= m)"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 03 Nov 2004 17:21:08 -0500
In article <76facea6.0411031205.ed74349@posting.google.com>,
sgeos@granicus.if.org (Brendan Sechter) wrote:
> If I am going pick two numbers at random, both from zero to n and add
> them, what is the chance of the sum being less than or equal to m?
>
> This seems like it should be easy, but my math is really rusty.
>
> If n is 5 and m is 3 I can draw this diagram:
>
> | m n
> | 0 1 2 3 4 5
> -----+-----------------------
> |
> 0 | 0 1 2 3 / 4 5
> | /
> 1 | 1 2 3 / 4 5 6
> | /
> 2 | 2 3 / 4 5 6 7
> | /
> m 3 | 3 / 4 5 6 7 8
> | /
> 4 | 4 5 6 7 8 9
> |
> n 5 | 5 6 7 8 9 10
Notice the above table has n + 1 rows and n + 1 columns. So there
are (n + 1)(n + 1) = n^2 + 2 n + 1 entries, each equally probable.
In how many of these is the entry, that is, sum, less than or
equal to m?
Three cases suggest themselves to me.
Case 1: m less than or equal to n.
In this case, the first column has (m + 1) entries with a sum
less than or equal to m. The next column has one less, and so on.
So the number of entries in which the sum does not exceed m
is
(m + 1) + m + (m - 1) + ... + 1
Observe (for k even):
1 + 2 + 3 + ... + k = (1 + k) + (2 + (k - 1)) + ...
+ ( (k/2) + (k - (k/2) + 1) )
= (k/2)(1 + k)
= k (k + 1)/2
You can check that that formula works as well for k odd. (There's
a story about Gauss to go along with this formula.
So the number of entries meeting the constraint on the sum is
(m + 1)(m + 2)/2
That is, the probability that the sum is less than or equal to
m in this case is:
[(m + 1)(m + 2)]/[2 (n + 1)(n + 1)]
Case 2: m greater than n and less than or equal to 2 n
The first column with the last entry equal to m is the
(m - n + 1)th column.
The entry in the (n +1)th column adding up to m is the entry in
the (m - n + 1)th row.
So the number of entries which meet the constraint is
(n + 1)(m - n) + (n + 1) + n + ... + (m - n + 1)
= (n + 1)(m - n)
+ (n + 1) + n + ... + 1
- [ (m - n) + (m - n - 1) + ... + 1]
= (n + 1)(m - n) + (n + 1)(n + 2)/2 - (m - n)(m - n + 1)/2
= (n + 1)(m - n)/2 + (n + 1)(n + 2)/2
+ (n + 1)(m - n)/2 - (m - n)(m - n + 1)/2
= (n + 1)(m + 2)/2 + (m - n)(2 n - m)/2
So the the probability that the sum is less than or equal to
m in this case is:
[(n + 1)(m + 2) + (m - n)(2 n - m)]/[2(n + 1)(n + 1)]
There's probably a more compact way of writing that.
Case 3: m greater than 2 n
This case is trivial. In all the entries, the sum is less than m.
Thus, the probability of the sum being less than or equal to m is
unity.
I welcome correction to any of the above, if any is needed.
-- Mostly economics: <http://www.dreamscape.com/rvien/#PublicationsForFun> r c v s a Whether strength of body or of mind, or wisdom, or i m p virtue, are found in proportion to the power or wealth e a e of a man is a question fit perhaps to be discussed by n e . slaves in the hearing of their masters, but highly @ r c m unbecoming to reasonable and free men in search of d o the truth. -- Rousseau
- Next message: Virgil: "Re: operator precedence -3^2 ; 10-3^2"
- Previous message: Ross A. Finlayson: "Re: sci.math.moderated?"
- In reply to: Brendan Sechter: "Chances of (random(0,n) + random(0,n) <= m)"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
