How do I represent the smallest ever possibility in JavaScript?

Question

I want to design a function that would return true most of the time but theoretically could return false.

So far, all I've come up with is (with comments added, due to some confusion):

function true(seed) {
  // Poop, you can't `seed` Math.random()!
  return Math.random() !== Math.random();
}
// but if I had that seed, and Math.random() was seedable, 
// I could make this function return false.

However, this runs into a few limitations.

1. Math.random() by implementation is not seedable therefore calling a random number generator twice in a row (with no other entropy) will never return the same number twice.
2. Math.random() will return a value between 0.0000000000000000 and 0.9999999999999999, which is sixteen digits of precision. So according to Binomial Distribution the probability of true not being true is (1/9999999999999999)^2. Or 1.0 e-32.

What I am trying to build is something that would only return false in the probability of 1/some integer that grows larger and larger. This is purely a thought experiment. There is no constraint on space and time, although if your answer has considered that as well then that's a bonus.

EDIT: I guess, here is another way to ask this question.

Take a look at this Plunker. https://plnkr.co/edit/C8lTSy1fWrbXRCR9i1zY?p=preview

<script src="//cdnjs.cloudflare.com/ajax/libs/seedrandom/2.4.0/seedrandom.min.js"></script>

function f(seed) {
  Math.seedrandom(seed);
  return 0.7781282080210712 === Math.random();
}

console.log(f());              // Behaves as expected
console.log(f(Math.random())); // Pretty much everything returns false

function t(seed) {
  Math.seedrandom(seed);
  return 0.7781282080210712 !== Math.random();
}

console.log(t());              // Returns true.
console.log(t(Math.random())); // All is well with the world.


// But, if you have the right seed!
console.log(f('Udia'));        // Holy shit, this returned true!
console.log(t('Udia'));        // Holy shit, this returned false!

What is the most interesting way to write a function that returns true? It can run forever, take up as much space as possible, etc. But it must return true. (and have the smallest probability of returning false.)

Answer 1

Fill buffers of whatever size you want with random data, and compare them.

Untested, but try something like this:

const length = 32768;
let values = [
  new Uint8Array(length),
  new Uint8Array(length)
];
window.crypto.getRandomValues(values[0]);
window.crypto.getRandomValues(values[1]);

let i;
for (i=0; i<length; i++) {
  if (values[0][i] === values[1][i]) {
    break;
  }
}
if (i === length-1) {
  console.log('The (nearly) impossible has occurred!');
}

Answer 2

Since Math.random() will not yield the same number twice in a row, do this:

var improbabilityDrive = Math.random();
var discard = Math.random();

function true() {
  return Math.random() !== improbabilityDrive; 
}

Or, if you don't want global variables, just discard the next few results:

function true() {
  var improbabilityDrive = Math.random();
  var discard = Math.random();
  discard = Math.random();
  discard = Math.random();
  //... more discards, if necessary
  return Math.random() !== improbabilityDrive; 
}

Edit: Drop Probability each time it's called

OP asked if it's possible to make it less and less likely to return (false, I think is what you meant?)

var hitsRequired = 0.0;
var improbabilityDrive = Math.random();

//Increasingly Lower Chance of 'false' With Each Call
function superTrue() {
  hitsRequired += 0.1; //Set Growth Factor here (algebraic: +=, geometric: *=)

  for (int i = 0; i < hitsRequired; i++) {
    if (trueish()) return true;
  }

  return false;
}

//Same Theoretically Low Chance of 'false' Each Call
function trueish() {
  var discard = Math.random();
  discard = Math.random();
  discard = Math.random();
  //... more discards, if necessary
  return Math.random() !== improbabilityDrive; 
}

Edit 2: Insanely Low Probability

After re-reading your question, I think you're after the most-low probability you can get. This is far, far, below reason:

//Increasingly Lower Chance of 'false' With Each Call
function superDuperTrue() {

  for (int i = 0; i <= 9007199254740992; i++) {
    if (trueish()) return true;
  }

  return false;
}

The probability that this produced a false is:

(1/4503599627370496) ^ 9007199254740992 = 10 ^ ( - 10 ^ 17.15)

That would, by almost any reasonable measure, be such an absurdly low probability that it could just be assumed to never happen. I'd be surprised if it would return a single false if tried a trillion times per second until the heat death of the universe - putting that into wolfram alpha didn't even drop the number of the probability (1 trillion * 10^100 years until heat death of the universe * 3,156,000 seconds / year * that probability = that probability, subject to 14 decimal places of accuracy).

Basically, it would never happen, but it theoretically possible.

At 1,000,000,000,000 tries per second:

• For n=0, 38 minutes would yeild a 50% chance of a single false.

• For n=1, 325 billion years would yeild a 50% chance of a single false.

• For n=2, 1500000000000000000000000000 years (1.5 * 10^17), or 110000000000000000 times the age of the universe would yeild a 50% chance of a single false.

• ... Increase n up to the 9007199254740992, above, to make it as implausible as you desire.

Answer 3

One way to tune this yourself would be to repeat the process. E.g.:

function true() {
  var n = 1000;

  var first = Math.random();
  for (var i = 0; i < n; i++) {
    if (Math.random() !== first) {
      return true;
    }
  }
  return false;
}

Now your code in the original question is just the special case of n = 2, and the odds of returning false are 1/9999999999999999^(n-1).

Answer 4

You can get an adjustable probability with

return Math.random() > 0.00000001; // play with that number 

Answer 5

Numbers in js are IEEE 754 doubles. So Math.random() returns values between 0 and 0.999999999999999888977697537484.

To calculate the number of possible unique return values is simpler. IEEE 754 doubles have 52 bit mantissa. So the number of possible return values is: 2^52 or 4503599627370496.

Which means, the smallest ever possibility is 1/4503599627370496.

Now, if you REALLY want the smallest possible probability just compare the output of Math.random() to one of it's unique outputs. Note that since not all decimal numbers are representable as floats you should use a number that has an exact representation. For example 0.5.

So, the smallest possible probability is:

Math.random() === 0.5

Which has exactly 1 in 4503599627370496 chance of happening. The theoretical smallest probability.

So if you want your function to return true most of the time you should do:

function true() {
    return Math.random() !== 0.5;
}

Warning

Note that this may not be what you want. It is very, very rare for this smallest probability to happen. As a test I ran the following code:

for (i=0;i<1000000000;i++){ // loop to one billion
    foo=Math.random();
    if (foo === 0.5) {
        console.log('>>> ' + i)
    }
}

I ran the above loop five times and only observed the console.log() output once. In theory you should expect to see the event happen once every 4.5 quadrillion times you call that function. Which means that if you call the function once each second it will see the it return false roughly once every 143 million years.