CODEWITHSUNDEEP
javascriptnode.jsrandom
avo
avo

Reputation: 10711

When does Math.random() start repeating?

I have this simple test in nodejs, I left it running overnight and could not get Math.random() to repeat. I realize that sooner or later the values (or even the whole sequence) will repeat, but is there any reasonable expectancy as to when it is going to happen?

let v = {};
for (let i = 0;; i++) {
  let r = Math.random();
  if (r in v) break;
  v[r] = r;
}
console.log(i);

Upvotes: 9

Views: 2523

Answers (2)

EJoshuaS - Stand with Ukraine
EJoshuaS - Stand with Ukraine

Reputation: 12181

Related (on another site): Acceptable to rely on random ints being unique?

Also extremely related: How many double numbers are there between 0.0 and 1.0?

Mathematically, there are an infinite number of real numbers between 0 and 1. However, there are only a finite number of possible values that Math.Random could generate (because computers only have a finite number of bits to represent numbers). Let's say that there are N possible values that it could generate. Then, by the Pigeonhole Principle, there is a 100% chance of getting at least one duplicate value once you generate exactly N + 1 values.

At this point, the Birthday Paradox demonstrates that you should start seeing duplicates surprisingly quickly. According to this "paradox" (which isn't a true paradox, just counterintuitive), given a room with only 23 people, there's a greater than 50% chance of two of them having the same birthday.

Returning to our example, the rule of thumb for calculating this (see the linked Wikipedia article) suggests that Math.Random reaches a 50% probability of duplicates once you generate approximately sqrt(N) numbers.

From the linked Stack Overflow question, if we assume that there are 7,036,874,417,766 numbers between 0 and 1 like the accepted answer says (and please read the linked question for a more detailed explanation of how many there actually are), then sqrt(7036874417766) is just over 2.652 million, which isn't actually all that many. If you are generating 10,000 random numbers per second, you'd reach 50% probability in approximately 737 hours, which is just under 31 days. Less fortunately, even at 10,000 per second, it would take approximately 195,468 hours (which is approximately 22.3 years) to reach 100% probability.

Some of the other answers give much higher figures for how many numbers there are, so take your pick.

Also, beware the Gambler's fallacy - the fact that you just generated a value doesn't make it any less likely that the same value will occur again. So, regardless of how many times you've already generated a particular value, the probability of the next random number being the same value is still 1/N (with N being the number of possible values).

Upvotes: 4

dwjohnston
dwjohnston

Reputation: 11852

It is browser specific:

https://www.ecma-international.org/ecma-262/6.0/#sec-math.random

20.2.2.27 Math.random ( ) Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Each Math.random function created for distinct code Realms must produce a distinct sequence of values from successive calls.

The requirement here is just pseudo-random with uniform distribution.

Here's a blog post from V8 (Chrome and NodeJs's Javascript Engine).

https://v8.dev/blog/math-random

Where they say they are using xorshift128+, which has a maximal period of 2^128 -1.

Upvotes: 7

Related Questions