Generating random numbers

Have you ever wondered how deterministic machines like computers are able to make random choices? A computer program has to tell a computer exactly what to do at every stage; the computer cannot make decisions by itself. You can’t just tell the computer, `Do this, or do that, it’s up to you’. But random choices frequently need to be made by computers. For example, in 2048, the computer has to decide whether to spawn blocks of value 2 or 4, and it has to decide where to put them. How does it do this?

First, note that the problem of making random choices can be reduced to the problem of generating random numbers, since the choices can be numbered, a random number from among the numbers given to the choices can be generated, and then the choice numbered by the generated number can be taken. So, how do computers generate random numbers? The answer is, basically, that computers cheat. Their numbers they generate follow an entirely predictable pattern. The pattern is just chosen to be sufficiently obscure that nobody will recognise it. So they don’t really generate truly random numbers; the numbers they generate are said to be pseudo-random.

Here’s one simple, easy-to-understand way in which pseudo-random numbers can be generated. Suppose you want pseudo-random numbers in the range 0-99 (inclusive). Take a number which is bigger than 100 by several orders of magnitude to begin with, such as 127229878. That’s a 9-digit number. This initial number is called the seed. Now, we can get another 9-digit number from 127229878 by multiplying it by another 9-digit number, such as 851028006 and looking at the final 9 digits of the result. In this case, the result turns out to be 108276189377963268, and, putting the last 9 digits together, we get the new 9-digit number 377963268. By repeating this process, multiplying the last 9-digit number generated by 851028006 and looking at the final 9 digits each time, we get the following sequence:

307283608, 192725648, 922497888, 163851328, 948291968, 632855808, \\ 367758848, 102297088, 820246528, 152263168, 250283008, 233922048, \\ 68876288, 37321728, 760314368, \dotsc

Since we wanted numbers in the range 0-99 (inclusive), we take the first 2 digits of each number:

30, 19, 92, 16, 94, 63, 36, 10, 82, 15, 25, 23, 68, 37, 76, \dotsc

This is our sequence of pseudo-random numbers. Now, of course, we know the pattern behind this sequence, and we can work out what the numbers are arbitrarily far into the sequence; it’s completely predictable. But to someone who doesn’t know how this sequence was made, it’s pretty much impossible to see the pattern just by looking at the sequence. To them, it is practically indistinguishable from a sequence of truly random numbers. Of course, if they run the program multiple times, and the seed is the same each time, they might notice that the sequence is always the same: but this can be avoided by making the seed different each time the program is run, e.g. by making it correspond to the current time. There is, however, a more serious problem: this method of generating pseudo-random numbers only works if you only need to generate a small amount of random numbers. If you need to generate more than one billion (109) random numbers, it is less than ideal, because the sequence above is actually a recurring sequence with period one billion. That is, the (109 + 1)th number in the sequence is the same as the first number in the sequence, the (109 + 2)th term is the same as the second number in the sequence, and so on. (If you want to know why this is the case, it’s because the period of this sequence is the order of 851028006 in the multiplicative group of integers modulo one billion, and this order is at most one billion; that will make sense to you if you have some familiarity with number theory. In fact, the order of 851028006 could be much smaller than one billion; I haven’t checked what it is. If you were going to actually use a generator like this one, you’d make sure to choose a multiplier whose order is as high as possible.)

There are better ways of generating pseudo-random numbers than this one—no computer in practice uses an algorithm quite as simple as this. However, all of them work in essentially the same way: generate a sequence of numbers in a way that is completely predictable, but sufficiently obscure that it is hard for a human to distinguish the sequence from a truly random sequence, at least if they don’t look very far into the sequence. The only way computers can generate truly random numbers is by taking advantage of something external to the computer, e.g. low-volume atmospheric noise (which is what they use at RANDOM.ORG) which fluctuates unpredictably. However, even these numbers are, in a way, not truly random, because they are calculated from properties of natural processes which are themselves completely determined by physical laws. In theory, with enough knowledge about the atmosphere and whatever else might affect the atmospheric noise levels, you would be able to calculate the atmospheric noise levels and thus predict what numbers RANDOM.ORG will generate for you. It is only the fact that this is not practically possible that makes RANDOM.ORG a true random number generator. (There are also phenomena that can be taken advantage of which are non-deterministic at a fundamental level, such as radioactive decay. According to current theories, the precise moment when a radiactive materal will decay is truly unpredictable. I don’t know enough physics to say whether RANDOM.ORG’s atmospheric noise is actually influenced by non-deterministic quantum phenomena; it may well be, in which case it is truly random. But even if it is predictable given perfect information, it’s still practically as random as it would be otherwise, since nobody has that perfect information.)

Naturally, pseudo-random number generators can be taken advantage of. In order to predict what sequence will be generated, all you need to do is find out the seed. For this reason, online gambling websites usually generate their random numbers in a similar way as RANDOM.ORG. However, video game designers are not always so careful. In Pokémon Emerald, for example, they decided to make the seed start at a constant value whenever the Game Boy Advance was switched on. Therefore, players were able to work out the sequence of pseudo-random numbers that would be generated, and they could use this knowledge to make sure the sequence was at the right point before, say, encountering a legendary Pokémon, so that they could ensure that the Pokémon had exactly the attributes they wanted. The seed generation process became more complicated in later games, but people still managed to work it out. (If you’re interested, here’s a guide.)

Advertisements

One response to “Generating random numbers

  1. Reblogged this on cho(u/w)dhurykids and commented:
    Didn’t really feel like reading about Pokemon. But great read on determinism.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s