[Math] Probability of an RNG

probabilityrandom

For fun (relatively speaking), I'd like to do a little research on probabilities related to a pseudo-random number generator.

Specifically, how would I get started figuring out ~~"what is the probability that a prng will generate the same random number twice?"~~

This is part of an investigation into a larger issue, but I'm not sure where to begin (or if my question is even relevant).

Edited to add:

After reading the comments and answers I see that my question isn't clear. As an example: the rng outputs a 5 What is the probability that another 5 will be the next output? How many "rolls" of the RNG must I make before I see another 5?

If we assume a good rng has uniform distribution, then is it 1 out of (2^32) (assuming 32bit integers)?

For a larger example, lets say I use the RNG to generate numbers that are used as an index into an array of characters. The array is 25 numbers long, so the output of the RNG is mod 25 I will generate a sequence of 5 characters.

How would I determine the probability of generating the same 5 character sequence?

If we assume that we have a uniform distribution of output numbers from the RNG, then the RNG's output shouldn't factor into the probability of generating the same character sequence.

However, is my assumption valid?

Best Answer

All pseudorandom number generators are periodic; you can thus expect any number you've seen to appear again if you do Monte Carlo long enough. What you really want to ask, I think, is how long their periods are. To list the ones I'm most familiar with, linear congruential generators (often used in calculators) typically have (very!) short periods (though two or more of these can be combined to produce a generator with a slightly longer period), the Marsaglia-Zaman generator has a period of $\approx 5\times 10^{171}$, and the now-popular Mersenne twister by Matsumoto and Nishimura has a period of $2^{19937} - 1\approx4\times 10^{6001}$. One necessary condition for a quality PRNG is a long period length (but this isn't a sufficient condition, as it should also pass a bunch of stringent statistical tests). Have a look at these two articles for more information.

Related Solutions

Random – Pseudo Random Number Generation on the GPU

I queried fellow students and they brought my attention to this paper: https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch37.html

Since the paper is quite long and might not be online forever below is the general idea:

Linear Congruent Generators are ideal for use on the GPU because they are simple and do not require much state (only the previously generated number). but they are not 'random enough' for, for example, Monte Carlo based simulation. A generator like a Mersenne Twister would be better but requires way too much state to be stored.

The solution proposed by the paper is combining several LCGs using a combined Tausworthe Generator (as used by the Mersenne Twister) this guarantees a much better randomness without having to store as much state as the Mersenne Twister. The final algorithm looks like this:

struct RandomResult
{
    uint4 state;
    float value;
};

uint TausStep(uint z, int S1, int S2, int S3, uint M)
{
    uint b = (((z << S1) ^ z) >> S2);
    return (((z & M) << S3) ^ b);    
}

uint LCGStep(uint z, uint A, uint C)
{
    return (A * z + C);    
}

RandomResult Random(uint4 state)
{
    state.x = TausStep(state.x, 13, 19, 12, 4294967294);
    state.y = TausStep(state.y, 2, 25, 4, 4294967288);
    state.z = TausStep(state.z, 3, 11, 17, 4294967280);
    state.w = LCGStep(state.w, 1664525, 1013904223);

    RandomResult result;
    result.state = state;
    result.value = 2.3283064365387e-10 * (state.x ^ state.y ^ state.z ^ state.w);

    return result;
}

Note that the initial seed values for state should be larger than 128! (For background information reed the paper) and that you should fill the seed with 4 good random numbers from the CPU + four values unique for that pixel to get a nice result.

[Math] Mathematically what are random numbers

OK, your problem with 1st point is your wrong interpretation of that. As I see, it means if you take a fixed number of outcomes the probability of every outcome is equal, i.e. if you generate 100 true-random numbers from 0-9 there are 10 0's, 10 1's and 10 of each (the values are uniformly distributed over a defined interval or set). This probability never changes, so your view that it might not give any 9's in first 100 outcome is, uh according to me, wrong. Even if we suppose no 9's came in first 100 outcomes (assumption, so just assume.) then you can't say what will happen in next generation since it must at least follow point 2 according to you. In real world there is nothing as random, but anything which is too complicated or difficult to establish a series is generally termed as random. In mathematical study of probability we assume true randomness, however there is nothing as such. There is the butterfly effect, because of which even if a butterfly flapped it's wing in different direction, it would lead to a storm. So every minor thing counts, even the air that is a kilometer far away from the place of tossing the coin, hence no accurate predictions can be done. If we are given godly (infinitely powerful) computer that could calculate that, we could predict the future. But there's something more, even if you take real world variables and repeat the experiment many times (say n times), then you find the probability of an event, you get that approaching true-random variable's probability when n tends to infinity, i.e. $n\to\infty$. You can look up an example of a probability calculation that I just did with the computer (yes computer are not truly random) for Coupon Collector's problem and repeated it a crore times (yes computers are fast) and I got 14.6999 or so which actually is 14.7. Think if we repeated it many many more times? (infinite indeed to be accurate, maybe since debatable) There are many other examples of such calculations which you can easily find.

I think that explains my view of random to all. :D

Best Answer

Related Solutions

Random – Pseudo Random Number Generation on the GPU

[Math] Mathematically what are random numbers

Related Question