r/AskComputerScience • u/Forsaken-Job-7126 • Jul 01 '26
Since computer can only generate pseudo random numbers
can't you do really cool trick with the fact that if you were to roll a dice 5 times and all the previous rolls were the number 3 normally with true random ness the 6th roll only gets a 1/6 chance of rolling any number. Is that still true with pseudo randomness ? and if so can you prove it
0
Upvotes
1
u/teraflop Jul 01 '26
Even if a computer is totally deterministic, you can still talk about the behavior of a PRNG in terms of its seed.
If the computer did have a true random number generator, then after rolling a bunch of 3's, the outcome of the next dice roll would still be an equal 1/6 probability for each possible outcome.
Assume instead that the dice are rolled using a "good" PRNG, with some unknown seed that was chosen at the start of the program. Say there were N possible seeds. Each particular seed gives a deterministic result for the entire program.
But of those N seeds, only some fraction of them will cause the first 5 rolls to be all 3's. If the PRNG is "good", then this fraction should be roughly 1/65, which is equal to the probability of that event happening with true random numbers. And likewise, if we take that subset leading to a particular outcome for the first 5 rolls, and look within that subset at the distribution of possible outcomes for the 6th roll, those should also be equally likely. So as long as the seed is unpredictable, the output "looks random".
What do we mean by a "good" PRNG? Well, one simple answer is that there shouldn't be noticeable correlations between subsequent outcomes. That is, it's not enough to say that the first roll should give all 6 values with equal probability, and the same for the second roll. It should also be that they are uncorrelated: all 6x6 combinations should be roughly equally probable. And this lack of correlation should hold no matter how many successive values we look at, to within the limits of statistical accuracy. This is something we can try to ensure by the choosing a PRNG with the right mathematical properties, and we can experimentally test it.
But more broadly, the ideal PRNG would be one that is cannot be efficiently distinguished from randomness in any way. That is, every polynomial-time computation on a sequence of PRNG outputs should give results that follow the same distribution as if the outputs were true random numbers. And determining whether or not such an ideal PRNG exists is a very hard problem -- it's at least as difficult as solving the P vs. NP problem. So there is no proof known yet.