1 in 619 million chance simulation

[Wictorian]

So I wanna simulate an event that has 1 in 619 million chance of happening, and calculate how many tries it took to happen. How can I do this. I tried generating two random numbers between 1 and 24000 (root of 619 million) and check if they are the same, but it yielded unexpected results. Was it correct? If not, how can I simulate it?

[Alvin853]

20 minutes ago, Wictorian said:

So I wanna simulate an event that has 1 in 619 million chance of happening, and calculate how many tries it took to happen. How can I do this. I tried generating two random numbers between 1 and 24000 (root of 619 million) and check if they are the same, but it yielded unexpected results. Was it correct? If not, how can I simulate it?

Yeah that's not correct, a 1 in 619 million event would be both random numbers being a specific value, like number 1 being 1 and number 2 being 24000... because there are 24000 possibilities for them to be the same, so the chance of them being the same is actually 24000 in 619 million. 

[mariushm]

You're dealing with 30 bits of information  ... 2³⁰ = 1,073,741,824   ... so whatever is easier, depending on the programming language you choose...

a lot of programming languages will have a pseudo-random function that returns a floating point number between 0 and 1 ... so just multiply that by 619,000,000 and truncate to an integer.

Or, pick a random 32 bit number and set the first two bits to 0, and 0 out the 30th bit if the number is higher than 619 million

 

How often the same random number occurs will vary, and will depend on the algorithm used by the programming language... a good random number generator will have a pretty good distribution .. as in if you do random ( 0 ,99) 1 million times, each number will be more or less evenly present.

 

Example code in php doing random numbers with mt_rand which uses Mersenne Twister random number generator

 

<?php

$r = [];
for ($i=0;$i<100;$i++) $r[$i] = 0;
for ($i=0;$i<999999;$i++) {
  $rand = mt_rand(0,99);
  $r[$rand]++;

}

echo "Distribution:\n";
echo json_encode($r);
?>


d:\Programs\php7>php random.php
Distribution:
[10041,10077,10037,10236,9943,10162,10068,9975,10161,9833,10274,10012,9883,9876,9953,9803,9951,10044,9919,9963,10249,9921,9839,10058,9826,10170,9899,10065,9987,10098,10131,9909,10000,10114,9988,9969,1
0015,9983,9875,9716,9935,10053,10086,9789,10042,10023,10143,10098,10047,9922,10112,9925,10140,10246,9955,9993,9893,9960,9942,9835,9984,10009,9941,9844,10224,10078,9959,10208,9943,10121,10037,10059,100
74,9956,9843,9769,10001,9944,9946,9992,9849,9967,9973,10059,9944,9942,9925,9896,10035,9967,10093,9993,9999,10038,10158,10006,10051,10018,10089,9903]

 

[Sauron]

2 hours ago, Wictorian said:

So I wanna simulate an event that has 1 in 619 million chance of happening, and calculate how many tries it took to happen. How can I do this. I tried generating two random numbers between 1 and 24000 (root of 619 million) and check if they are the same, but it yielded unexpected results. Was it correct? If not, how can I simulate it?

Generate a number between 1 and 619M, repeat until that number is equal to 42.

[Wictorian]

2 hours ago, Alvin853 said:

Yeah that's not correct, a 1 in 619 million event would be both random numbers being a specific value, like number 1 being 1 and number 2 being 24000... because there are 24000 possibilities for them to be the same, so the chance of them being the same is actually 24000 in 619 million. 

So it would work with 4 random numbers right? It would check if num0 == num1 and num2 == num3.

[OrionFOTL]

15 hours ago, Wictorian said:

So it would work with 4 random numbers right? It would check if num0 == num1 and num2 == num3.

This question makes me think we're dealing with an XY problem here. https://xyproblem.info/

[shadow_ray]

16 hours ago, Sauron said:

Generate a number between 1 and 619M, repeat until that number is equal to 42.

This is the way! A zero is missing from the end, otherwise it's perfect.

[WhitetailAni]

3 hours ago, shadow_ray said:

This is the way! A zero is missing from the end, otherwise it's perfect.

No, 42 is correct.

After all, 42 is the answer to Life, the Universe, and Everything.

[Franck]

it should be as simple as that

var rnd = new Random();
ulong tries = 1;
var prefix = "";

while (rnd.Next(1, 619000001) != 1)
{
  if (tries == ulong.MaxValue)
  {
    prefix = "no ";
    break;                    
  }
  tries++;
}


Console.WriteLine($@"{prefix}match found after {tries} tries");

 

[Eigenvektor]

4 hours ago, Franck said:

it should be as simple as that

…

Of course, ideally, you want to run that in a loop. This way you can determine the probability that you get the expected result after n tries.

 

I just did this in Java, using JFreeChart to plot the graph. To keep the run time manageable I used 1/100 instead of 1/619M

Spoiler

Not quite the result I would've expected.

 

Code (excluding chart generation)

Spoiler

	private static final int BOUND = 100;
	private static final int TARGET = 0;
	private static final int LOOPS = 10_000_000;

	public static void main(final String[] args) {
		final var random = new SplittableRandom();
		final var distribution = new HashMap<Long, AtomicLong>();

		for (int n = 0; n < LOOPS; n++) {
			var tries = 0L;
			while (random.nextInt(BOUND) != TARGET && tries < Long.MAX_VALUE) {
				++tries;
			}

			if (tries < Long.MAX_VALUE) {
				distribution.computeIfAbsent(tries, k -> new AtomicLong(0L)).incrementAndGet();
			}
		}

		plotChart(distribution);
	}

 

 

[shadow_ray]

@Eigenvektor Thanks! I was wondering what the distribution looks like.

There is a 1/100 chance that the first try gonna be a hit hence 100k results.

For the 100  it needs 99 miss and 1 hit which is (1 - 0.01)^99 * 0.01  = 0.003697... this times 10 mill is around 37k. It checks out.

 

Geometric distribution

[Eigenvektor]

1 hour ago, shadow_ray said:

@Eigenvektor Thanks! I was wondering what the distribution looks like.

There is a 1/100 chance that the first try gonna be a hit hence 100k results.

For the 100  it needs 99 miss and 1 hit which is (1 - 0.01)^99 * 0.01  = 0.003697... this times 10 mill is around 37k. It checks out.

 

Geometric distribution

Yeah, it makes sense once you start to think about it :) For some reason, intuitively, I expected some kind of bell curve. But that makes no sense since every number (should have) equal probability. The documentation for random says as much.

 

I've extended the code a bit to test for multiple numbers. As expected the probability of getting any one of these numbers on the n-th try is roughly identical.

Spoiler