9

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);
avo
  • 10,101
  • 13
  • 53
  • 81
  • 2
    This here probably answers it: https://hackernoon.com/how-does-javascripts-math-random-generate-random-numbers-ef0de6a20131 – dwjohnston Oct 26 '18 at 05:35
  • One issue with your code, is that Math.random() is seeded on the current time, so even if / when it eventually finds a duplicate, your results arn't repeatable. – Ryan Leach Oct 26 '18 at 05:36
  • I mean... it _is_ intended to be random, not a repeating sequence of seemingly random numbers. I wouldn't expect it to start repeating... Unless I'm misunderstanding something... – Alexander Nied Oct 26 '18 at 05:36
  • https://rawgit.com/lordpoint/xorshift-sandbox-and-visualizer/master/index.html for a live version of the link at the end of the article – Ryan Leach Oct 26 '18 at 05:40
  • @AlexanderNied 'non cryptographically secure' random number generators are rarely random. and probabilistic-ally it's possible for even truly random number generators to repeat for non trivial sections, depending on the range of values produced. If they wern't they wouldn't be random. – Ryan Leach Oct 26 '18 at 05:41
  • @RyanTheLeach, a duplicate is OK as long as doesn't happen more often then let's say once in a few milliseconds, as I'm combining this value with `new Date().valueOf()` to make it more unique. – avo Oct 26 '18 at 05:42
  • 1
    Then you have an X Y problem. use UUID or a clock value that always increments, that resets when Date().valueOf() returns a different value. UUID's have a scheme involving a 'machine id' a local time source that can give you unique values for a very very long time. – Ryan Leach Oct 26 '18 at 05:44
  • 1
    @RyanTheLeach - I understand now. I didn't closely review your code and thought you were looking for sequential repetitions, not simply any one repeated value. Impressive it made it overnight w/o finding a duplicate, although by the end of the evening I wonder how long a single check would take to iterate over every value you'd recorded in `v`-- it may have slowed significantly... – Alexander Nied Oct 26 '18 at 05:45

2 Answers2

7

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.

dwjohnston
  • 11,163
  • 32
  • 99
  • 194
  • 2
    `2^128` sounds more likely – Mat Oct 26 '18 at 05:48
  • Interesting. So would that be safe to assume that something like `Math.random() + "_" + new Date().valueOf()` would be generating unique strings (to a particular context), until it gets stopped? – avo Oct 26 '18 at 05:48
  • 4
    There's never a guarantee that you won't get 2 numbers in a row that are duplicates, the point is it's pseudo random. If you need uniqueness, avoid random. If you still want to use random as part of an ID, use a well tested schema like UUID – Ryan Leach Oct 26 '18 at 05:50
  • 2
    See https://stackoverflow.com/questions/23164474/how-unique-and-random-are-javascript-generated-uuids Using UUID's is clear, unambiguous, and well documented of their chance of collision. rolling your own will have significant cost of maintenance. – Ryan Leach Oct 26 '18 at 05:53
4

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

EJoshuaS - Stand with Ukraine
  • 11,977
  • 56
  • 49
  • 78