7

Is this correct? using - http://en.wikipedia.org/wiki/Binomial_probability

Looks like values are from .0000000000000000 to .9999999999999999

Probability of happening twice = p^2 = (1/9999999999999999)^2 = 1.0 e-32

I think I am missing something here?

Also, how does being a pseudo random number generator change this calculation?

Thank You.

T.T.T.
  • 33,367
  • 47
  • 130
  • 168
  • 3
    one that may affect being a pseudo random, is calculating them so fast with no time to change the seed, so it will produce the same number. I guess mostly will affect it because it will be seed dependent. – Eric Fortis Dec 16 '10 at 01:19
  • 3
    Actually, @Eric, that's not correct. Changing the seed periodically actually makes the numbers no more random, and very probably less random because the initial state changes in a computable fashion. There are some lovely obscure crypto flaws that show up in that fashion. – Charlie Martin Dec 16 '10 at 01:30
  • 1
    @Charlie, that will depend on the implementation, I don't how JS random works. When I started programming that was one of my first problem getting the same random repeated. And I missed reading the title, so @Tommy that's probably wrong what I said. – Eric Fortis Dec 16 '10 at 01:34
  • 2
    @Eric: that's fine, all answers help out! – T.T.T. Dec 16 '10 at 02:03

5 Answers5

5

I think the probability of getting two numbers in a row is 1 divided by the range of the generator, assuming that it has a good distribution.

The reason for this is that the first number can be anything, and the second number needs to just be that number again, which means we don't care about the first number at all. The probability of getting the same number twice in a row is the same as the probability of getting any particular number once.

Getting some particular number twice in a row, e.g. two 0.5s in a row, would be p^2; however, if you just care about any number twice in a row, it's just p.

Tikhon Jelvis
  • 67,485
  • 18
  • 177
  • 214
  • 2
    I think so, yes. Pretend you have a die that goes from 1 to 6. The chances of rolling two sixes is 1/(6 * 6); however, the chance of rolling two same numbers is the sum of the probability of rolling two ones, two twos...etc. This is 6 * (1 / (6 * 6)) or just 1//6. – Tikhon Jelvis Dec 16 '10 at 01:33
  • isn't rolling two sixes the same as rolling two same numbers by definition? (only 1 die in these examples right?) – T.T.T. Dec 16 '10 at 01:42
  • 1
    Well, the difference is that "rolling two numbers" _also_ includes rolling two ones, two twos, two threes...etc while "rolling two sixes" is _only_ two sixes--the latter is really a subset of the former. – Tikhon Jelvis Dec 16 '10 at 01:44
  • Yes, @Tikhon Jelvis, you are correct and my comment (now deleted) at the top is not. – President James K. Polk Dec 16 '10 at 02:19
5

In an ideal world Math.random() would be absolutely random, with one output being completely independent from another, which (assuming p=the probability of any given number being produced) results in a probably of p^2 for any value being repeated immediately after another (as others have already said).

In practice people want Math.random to be fast which means pseudo-random number generators are used by the engines. There are many different kinds of PRNG but the most basic is a linear congruential generator, which is basically a function along the lines of:

s(n + 1) = some_prime * s(n) + some_value mod some_other_prime

If such a generator is used then you won't see a value repeated until you've called random() some_other_prime times. You're guaranteed of that.

Relatively recently however it's become apparent that this kind of behaviour (coupled with seeding the PRNGs with the current time) could be used for some forms tracking have led to browsers doing a number of things that mean you can't assume anything about subsequent random() calls.

olliej
  • 35,755
  • 9
  • 58
  • 55
  • 1
    Interesting, so then there could never be two numbers in a row using Math.Random()? – T.T.T. Dec 16 '10 at 01:54
  • 1
    Only in older browsers (i accidentally hit submit before finishing the post). To avoid certain tracking operations browsers may now periodically reseed the PRNG, not use LCGs, etc that make that no longer true. – olliej Dec 16 '10 at 01:56
  • 2
    Of course you're also assuming no one else is calling random() -- if you're calling random() on a timer (say) then another page may run before you, and call random() itself, which could change things. – olliej Dec 16 '10 at 01:57
  • I was simply giving those as examples of other ways that the PRNG state could change. In a modern browser you're not guaranteed that you won't see repeated values. – olliej Dec 16 '10 at 02:02
2

If the numbers were truly random, you'd expect them, indeed, to appear with probability 1/p, so twice that would be 1/p^2.

The value for p is not exactly the one you have though, because the numbers are being represented internally as binary. Figure out how many bits of mantissa the numbers have in javascript and use that for your combinatoric count.

The "pseudorandom" part is more interesting, because the properties of pseudorandom number generators vary. Knuth does some lovely work with that in Seminumerical Algorithms, but basically most usual PN generators have at least some spectral distributiuon. Cryptograp0hic PN generators are generally stronger.

Update: The amount of time shouldn't be significant. Whether it's a millisecond or a year, as long as you don't update the state The probabilities will stay the same.

Charlie Martin
  • 110,348
  • 25
  • 193
  • 263
  • Is there any chance greater than 0, that it could generate the same number twice, being represented by bits and pseudo random? – T.T.T. Dec 16 '10 at 01:29
  • Charlie, also see Tikhons take on the math, perhaps p^2 is incorrect? – T.T.T. Dec 16 '10 at 01:32
  • Looks like 52 bit mantissa: http://stackoverflow.com/questions/307179/what-is-javascripts-max-int-whats-the-highest-integer-value-a-number-can-go-to – T.T.T. Dec 16 '10 at 01:44
  • 1
    Tommy, it's an interpretation question. The probability that n_i is a pareticular value is 1/p. If the numbers are really random, the probability of n_i, and n_i+1 having the same value is 1/p^2. But as he says, the probability of finding a pair over the whole run of a PN sequence is p. On the other point, it depends entirely on your PN generator. A "linear shift register" generator, which is "not very random" in some senses but still quite useful, would have a probability of two sequential values being the same as exactly 0. – Charlie Martin Dec 16 '10 at 01:54
  • Prob(n_i+1 = n_i) = p, not p*p. – President James K. Polk Dec 16 '10 at 12:31
  • @GregS Took a long time to get there, but that's the conditional probability that n_i+1 is k given that n_i is k. The probability that that the pair (n_i,n_i+1) both equal k is as stated. – Charlie Martin Dec 16 '11 at 15:59
  • @CharlieMartin: There's only one question being asked and it is in the title. What is the probability that the i-th output is the same as the i+1-st output, and it is p. – President James K. Polk Dec 16 '11 at 22:01
  • No @GregS, there's only one question, and its whether the pair both equal k. (Actually the title admits of both interpretations, but if you're gonna be that way I will too.) – Charlie Martin Dec 17 '11 at 23:44
2

The probability that you would get 2 given numbers is (1/p)^2, but the probability that you get 2 of same numbers (any) is 1/p. That is because the first number can be anything, and the second just needs to match that.

delmet
  • 1,013
  • 2
  • 9
  • 23
0

You can kind of find out, just let it run a few days :)

var last = 0.1;
var count = 0 | 0;
function rand(){
    ++count;
    var num = Math.random();
    if(num === last){
        console.log('count: '+count+' num: '+num);
    }
    last = num;
} 
while(true) rand();
TeeraMusic
  • 452
  • 1
  • 5
  • 10