Re: Chances of (random(0,n) + random(0,n) <= m)

mensanator_at_aol.com
Date: 11/03/04 

Date: 3 Nov 2004 14:08:19 -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.

Two mistakes:

First: 10 would be for <=m not <m (which would be 6)

Second: denominator is 36 not 25. It's not n^2 because you're
counting from 0, so it should be (n+1)^2.

> If m is
> less than or equal to n, the chances are 0 + 1 + ... m + (m + 1).

Use the sum of integers formula (adjusting for counting from 0):

sum(m+1) = ((m+1)^2 + (m+1))/2

So for m=3, you get ((3+1)^2 + (3+1))/2 = (4^2 + 4)/2 = 20/2 = 10

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

It's symmetric. Instead of breaking off the corner of the square and
keeping it, you break off the opposite corner and discard it.
Keeping the corner is the SumOfIntegers. Discarding it is
(n+1)^2 - SumOfIntegers.

But you'll need an if-else to decide which to use.

Summarizing, if

m<n

probability of <m = sum((m+1)-1) / (n+1)^2
probability of <=m = sum((m+1)) / (n+1)^2
probability of =m = (m+1) / (n+1)^2
probability of >=m = (n+1)^2 - sum((m+1)) / (n+1)^2
probability of >m = (n+1)^2 - sum((m+1)-1) / (n+1)^2

m=n

probability of <m = sum((m+1)-1) / (n+1)^2
probability of <=m = sum((m+1)) / (n+1)^2
probability of =m = (m+1) / (n+1)^2
probability of >=m = sum((m+1)) / (n+1)^2
probability of >m = sum((m+1)-1) / (n+1)^2

m>n

probability of <m = (n+1)^2 - sum((m+1)-1) / (n+1)^2
probability of <=m = (n+1)^2 - sum((m+1)) / (n+1)^2
probability of =m = (m+1) / (n+1)^2
probability of >=m = sum((m+1)) / (n+1)^2
probability of >m = sum((m+1)-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.
>
> -Brendan

Relevant Pages

  • Re: Why are they more secure?
    ... And whenever the second one changed, either reset session or discard ... cookie sent. ... It is a bit off-topic here as it is a matter of lower-level network conflict ... You have little chance to detect such ...
    (comp.lang.php)
  • Re: All those poor people
    ... > and I'm so comfortable with it I instantly discard the answers to a, ... there it may have a chance to kill itself in isolation and not ... Prev by Date: ...
    (uk.rec.sheds)
  • Re: MVC - Model binding to collection
    ... Sorry I've been tied up all of last week and not had chance to try our work ... FormCollection approach in my project and received the same result. ... please feel free to let me know and discard. ... Microsoft Online Support ...
    (microsoft.public.dotnet.framework.aspnet)
Loading