0
$\begingroup$

I ran into an interesting answer on gamedev. He uses an interesting formula and ran it 100.000 time to get the average percentages.

The formula is as following:

For f(x, y), take a random number between 0 and x, take a random number between 0 and y. Give the odds that the first number is larger than the second.

Next, it get more interesting, because we can also run multiple iterations. For every iteration, the sum of values is used. So for n iterations:

For f(x, y, n), take the sum of n random numbers between 0 and x, take the sum of n random numbers between 0 and y. Give the odds that the first number is larger than the second.

How do you calculate this formula?

$\endgroup$
1
  • $\begingroup$ Ps. I did find if (x < y) then 1 - x / ( 2 * y ) else y / ( 2 * x ) but that's a weird formula and i do not understand why it works. $\endgroup$
    – Dorus
    Jul 19, 2016 at 13:49

2 Answers 2

1
$\begingroup$

You have two entities (call them Thing1 and Thing2) with powers $A$ and $B$. You generate independent uniform random numbers $a$ on $(0, A)$ and $b$ on $(0,B)$. Thing1 wins if $a>b$ and Thing2 wins if $a< b$ (we don't worry about equality of $a$ and $b$ as this occurs with probability $0$, but if it does worry you draw again).

The outcome is uniformly distributed over the rectangle $(0,A)\times(0,B)$ in the $(a,b)$ plane (drawing a picture will help at this point).

Now I will assume that $A\ge B$.

enter image description here

Then Thing2 wins if the random point $(a,b)$ is above the line $a=b$ and within the rectangle. This region has area $B^2/2$. The total area of the rectangle is $AB$, so the probability than Thing2 wins is:

$$ P_2=\frac{B^2/2}{A\times B}=\frac{B}{2A} $$ This is the probability that the weaker (or equal) wins when the powers are $A\ge B$

The rest can be deduces from symmetry considerations.

$\endgroup$
1
  • $\begingroup$ Great answer, now i understand why the formula i got works. Still, can you extend this to the second half of my question, with n iterations? $\endgroup$
    – Dorus
    Jul 19, 2016 at 21:21
1
$\begingroup$

You are using $x$ in two places, one for the range of the random numbers and one for the number picked. I will use $X$ and $Y$ for the numbers picked and $x$ and $y$ the ranges they come from. If you draw a rectangle that has its lower corner at the origin, extends $X$ units to the right and $Y$ units up, you are picking a random point inside the rectangle. You then ask what the chance is that the point is below the line $x=y$. If $X\lt Y$ the acceptable area is a $X,X,\sqrt 2 X$ right triangle, so the chance is $\frac {\frac 12X^2}{XY}=\frac X{2Y}$. If $X\gt Y$ you can just reflect it to find $1-\frac Y{2X}$.

For the sum of $n$ randoms, the sums will converge to $\frac 12nX$ and $\frac 12nY$. The greater of $X,Y$ will become dominant.

$\endgroup$
3
  • $\begingroup$ I'm not sure if i understand the last sentence (beside the missing ` before frac). Remember there are n` random numbers, not the same random number n times. $\endgroup$
    – Dorus
    Jul 19, 2016 at 21:20
  • $\begingroup$ I lost a backslash, now fixed. The point is the central limit theorem. The sum of $n$ random numbers between $0$ and $X$ will converge to $\frac 12 nX$ with variance about $X \sqrt n$. When $n$ gets large enough, the larger sum will (almost) always be the larger of $X$ and $Y$. $\endgroup$ Jul 19, 2016 at 22:43
  • $\begingroup$ Ah yes, that makes sense. And if they are equal, it will always be 50%. Still doesn't tell me how to calculate the odds for only a few iterations, but does give great insight. Thanks :) $\endgroup$
    – Dorus
    Jul 19, 2016 at 23:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .