Re: Chances of (random(0,n) + random(0,n) <= m)
poespam-trap_at_yahoo.com
Date: 11/03/04
- Next message: Van Jacques: "Re: Simple group of order 60"
- Previous message: shedar: "Re: Fermat's Last Theorem"
- In reply to: Brendan Sechter: "Chances of (random(0,n) + random(0,n) <= m)"
- Next in thread: Robert Vienneau: "Re: Chances of (random(0,n) + random(0,n) <= m)"
- Messages sorted by: [ date ] [ thread ]
Date: 3 Nov 2004 14:16:01 -0800
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
>
> The chance of the random sum being less than m is 10 / 25. If m is
> less than or equal to n, the chances are 0 + 1 + ... m + (m + 1).
You've got the basic idea.
P(X1 + X2 <= m) = P(X1=0 & X2<=m) + P(X1=1 & X2<=m-1) + ...
+ P(X1=m & X2<=0)
That covers all the possibilities by which these two
numbers can add up to <=m.
If m<=n then the first term is (m+1)/(n+1)^2, the second term is
m/n^2, ... and the last term is 1/(n+1)^2.
That's exactly the sum you came up with, except that
your denominator should be (n+1)^2, not n^2 (there are
n+1 possible values of X1 or X2).
> If m is greater than n, the chances are n squared minus something. I
> can see the "something", but I'm having trouble putting it in terms
of
> m and n. I'm also not happy with an if-else answer.
The above expression is completely general, but some
terms will be zero in the case m>n. That's the "minus
something" you want.
X1 can't exceed n, so all the probabilities X1=n+1,
X1=n+2,... X1=m are 0. There are m-n of these.
(Useful general formula: For a and b integers, a<=b,
there are b-a+1 integers from a to b inclusive.]
Also, the probability that X2 <=m is 1 for m>n.
So the first term is 1/(n+1). The formula
(m+1)/(n+1)^2 should be replaced with
min(n+1, m+1)/(n+1)^2 or (min(n,m)+1)/(n+1)^2
> Side note: What is my real problem?
> This is a death spell calculation that may be used in a game. n is
> the spell's power level and m is the target's remaining life. It
> would be nice to be able to display the chance of killing the target.
> It's not strictly necessary that I understand why a given solution
> works, but as a matter of personal pride I'd like to.
The above should be enough to write a loop that could
do the general calculation in a computer program.
Here's another way to look at it that you might find
useful. Instead of calculating P(X1+X2<=m) directly,
let's look at the distribution P(X1+X2=m)
P(X1+X2 = 0) = 1/(n+1)^2
P(X1+X2 = 1) = P(0+1 or 1+0) = 2/(n+1)^2
(I hope my shorthand is clear)
P(X1+X2 = 2) = P(0+2 or 1+1 or 2+0) = 3/(n+1)^2
...
P(X1+X2 = n) = P(0+n or 1+(n-1) or ... or (n-1)+1 or n+0) =
(n+1)/(n+1)^2
P(X1+X2 = n+1) =
P(1+n or 2+(n-1) or ... or (n-1)+2 or n+1) = n/(n+1)^2
P(X1+X2 = n+2) =
P(2+n or 3+(n-1) or ... or (n-1)+3 or n+2) = (n-1)/(n+1)^2
...
P(X1+X2 = 2n-1) = 2/(n+1)^2
P(X1+X2 = 2n) = 1/(n+1)^2
See the pattern?
The numerators form a triangle shape, increasing from 1
to n+1, then decreasing back to 1 as m goes from 1 to
n to 2n.
The numerator in P(X1+X2 <=m) is thus a triangular number
if m<=n, and the sum of two triangular numbers if m>n.
This is long enough, I think I'll stop here.
- Randy
- Next message: Van Jacques: "Re: Simple group of order 60"
- Previous message: shedar: "Re: Fermat's Last Theorem"
- In reply to: Brendan Sechter: "Chances of (random(0,n) + random(0,n) <= m)"
- Next in thread: Robert Vienneau: "Re: Chances of (random(0,n) + random(0,n) <= m)"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
