Why is it hard for a program to generate random numbers?

Question

My kids asked me this question and I couldn't really give a concise, understandable explanation.

So I'm hoping someone on SO can.

Coastline

there are many questions on random numbers on SO, plesae take a lookat those... – Airman

en.wikipedia.org/wiki/Random_number_generator – Airman

I did actually search SO via Google but I couldn't find any questions that answer this one. – Coastline

xkcd.com/221 :) – Euphemize

-1 for the question in the title and nothing in the body to expand on the subject. Like for example, your own thoughts about the subject. – Chaing

I still like the question. ;) – Chaing

Maybe you should change your question to "How should I explain to a child why its hard to generate random numbers"? This fits your question body as well as giving you more kid-friendly answers (instead of answers aimed at programmers. no offense to everyone). – Buoy

Many thanks for all the answers. The kids had fun reading through them all and getting a far better understanding. – Coastline

Is it any easier for a human to generate random numbers? By all accounts they're pretty bad at it. Why not ask your kids how they would generate a random number? – Passive

Answer 1

How about, "Because computers just follow instructions, and random numbers are the opposite of following instructions. If you make a random number by following instructions, then it's not very random! Imagine trying to give someone instructions on how to choose a random number."

Wynn

My instructions - take dice, roll it - voila, a random number! – Susannahsusanne

@Neil Butterworth - Well, I guess a computer could do that, too! – Wynn

hmmm, not sure where heisenberg, chaos, or indeed quantum chaos would fall under that description! – Airman

The quantum universe is too stubborn to follow instructions ;-) although quantum physics doesn't (yet) govern computing... – Medico

@jder I've heard tell of a computer that used a radioactive element for randomness, and another that used a camera looking at a Lava Lamp. – Congenital

@tlholaday Yeah, definitely. Or it could use a mechanical arm + camera to roll a die. – Wynn

Simply measuring the thermal noise in the signal you get from measuring the voltage over a resistor would do the trick. – Cacuminal

Interestingly, the proposed solutions in these comments are not "a program to generate random numbers". Instead, they are a program reading a random number generated by some other means. – Erudition

Answer 2

Here's a kid friendly explanation:

1. Get a Dice (the number of sides doesn't matter)

2. Write these down on a piece of paper:

   • Move right
   • Move up
   • Move up
   • Turn the dice over
   • Move down
   • Move right

3. Show them the dice and paper. Explain that the dice represents the computer and the paper represent the math or algorithm that tells the computer what number it will return.

4. Now, roll the dice. Tell them that you are "seeding" or asking the computer to start at a random dice position.

5. Follow each step in the paper (move right) by moving the dice.

   • Let's say that you threw a 6 sided die and it was seeded at 5. By moving right, you get a 4.

6. Explain that the computer must start with a starting value. This could be given by any number of sources such as the date or mouse movement. Show them that how they throw the dice determines the starting value.

7. Explain that the piece of paper is how the computer get the next number. Tell them that the instructions on the paper can be changed as easily as the algorithm for the random generator can be changed by the programmer.

8. Have fun showing them the various possibilities that is only limited by their imaginations.

Now for the answer to your question:

Tell them that when a good mathematician knows the starting value and what step the computer is currently at, the mathematician can tell what is the next value of the random number.

1. Ask the child were to hide the paper and throw the dice.
2. Then ask the child to follow the steps on the paper, you then write down how he gets the next random number.
3. Afterwards, show them your paper. Now that you have a copy of their random number generator, its easy for anyone else to "guess" the next random to come out.

No matter how creative the child is with their algorithm, you should still be able to deduce their algorithm. Tell your child that in the computer world, nothing is hidden and just by observation, even if its just the numbers that was observed, the random number algorithm can be discovered.

...as a side effect, if the child was able to come up with a good algorithm that confused you, in which you can't deduce the next sequence, then you have a bright child. :D

Buoy

That is a good explanation for a 11-year old who is showing some inclination towards mathematical games. – Goldman

If I were to devise such algorithm, it would be self-modifying, the algorithm would be modified based on the number that appears on the dice. This would confuse most people enough, that they won't be able to easily follow the instruction. Great kid-friendly explanation though. [do I get a candy for this?] – Pricefixing

Answer 3

Here's my attempt at explaining randomness at an approximately eighth-grade level. Hope your kids find it useful!

Surprising as it may seem, a computer is not very smart. Computers must follow their instructions blindly, and are therefore completely predictable. A computer that doesn't follow its instructions in this manner is, in fact, broken! We want computers to do exactly what we tell them.

That's precisely what makes it hard to do things randomly. Computers must be told a sequence of instructions on how to generate random numbers. But that's not really random, because if you gave anybody else the instructions and the same starting point, they could come up with the same answers. So computers can't be truly random just by following instructions.

Raynor

I wouldn't say computers "[are] not very smart" because that kind of implies that they're a tiny bit smart. But that's not true - they are not smart at all. As you say, they strictly follow instructions, nothing more. – Nablus

That's true. On the other hand, I don't want to to completely destroy the sense of wonder that they can evoke, though. Also, even something that follows instructions blindly could theoretically be "smart" -- there is much speculation about this in the cognition/AI space. – Raynor

does eight-grade kids today think about computers as 'smart' things? i think they're just appliances to them – Phosphoprotein

I would say that computers are actually quite smart. However because they're so smart, we designed them so that they only did exactly as we tell them, so that they don't take over. – Maggy

I would also say that computers "must" be smart since we "must" use computers to design new computers. If computers were wiped off the face of the earth, how could we create a new one? – Yarak

as i've always been told, the IQ of a computer is 0 – Scandian

Answer 4

Ask them to devise a step-by-step method to generate a random number.

And don't accept "pick a number from 1 to 10" as an answer ;)

Trying out a problem should illustrate the difficulty of having to generate random numbers from a set of instructions, just like what computers actually have to do.

Kitts

It's not hard to make statistically distributed numbers. Just take a computable normal number and iterate over the digits. The issue is that this number still isn't random, it's still deterministically-determined. – Gutta

Ah, thank you for letting me know :) It just shows the topic of random numbers is a complex subject for a non-expert like me! – Kitts

Yep; a key element of randomness is unpredictability. If you know the next number, it isn't random at all. – Raynor

is really randomness = unpredictability ? Cant you use probability to game randomness after studying a stream of random numbers and find out that 8 (by randomness) hasent been shown in a loong time. I know that by definition, next random number "reset the history", but at the same time, – Chaing

the randomness will se to that all numbers will be eventually choosen distributed equal. So probability should be a tool to make some random numbers predictable in some cases when the randomness happend to do that a number didnt show up in a long time. ? ;) – Chaing

Randomness is more like "nondeterministicability". You can come up with a theory about the probabilities of different numbers and then maybe predict that, say, the next number will not be 8, but you can't say what it will be. – Medico

Being random only means that as you approach infinity, that the numbers will be distributed equally....... – Maggy

.... Flip a coin a hundred times, or a million times, you still don't know what the next flip will result in. Probability can let you assume that 50% it will be heads, but nothing stops it from being 75% heads over 1000 flips of the coin. – Maggy

If a number isn't coming up as often as you'd expect, it more likely means that it is not random and (for example) your die is weighted. e.g. if I flip a coin 10 times and don't get any heads I might question whether it is a trick coin! It definitely doesn't mean I am 'due' for heads, and if anything means that heads are less likely. – Mannose

@Kibbee: Having uniform distribution is not a necessary property of random number; some random number generators generates a normally distributed random number (i.e. Gaussian distribution). @KirkBroadhurst,@Stefan: For a uniform random number, the Gambler's Fallacy apply: the statistical distribution of past numbers have zero effect on future numbers, i.e. the fact that number 8 hasn't shown for a long time does not affect its chance of showing as the next number. – Pricefixing

Answer 5

Because computers are deterministic machines.

Favian

That's a good answer but not for kids - the next question is "Which means?" and you kind of end up where I was. – Coastline

Exactly what I think. This is the right answer for another question, but not for this one. – Gutta

I hope this answer was meant as a joke? – Vlissingen

Answer 6

Generating random numbers on a computer is like playing "Eenie meenie miney moe" when choosing who's It first in a game of tag. On the surface it does look random, but when you get into the details, it's completely deterministic. It's hard to make eenie meenie miney moe into a scheme that a person really can't predict the outcome of.

Also there's some difficulties with getting the distribution nice and even.

Mispleading

Answer 7

Because given any input, an algorithm produces the exact same output every single time. And you can't just provide a "random" input, because you're trying to generate the random number in the first place.

Mudguard

well actually you can provide random input from humans, some apps do it: will you please move the mouse randomly and hit some random keys? (whether humans can really produce true random numbers is another question) – Vlissingen

I would say that moving the mouse around in a random fashion would be random. There's probably a very low chance you could create a repeatable mouse movement, without trying really hard. – Maggy

Answer 8

"Kids, unless they're broken, computers never lie, and they always do what you tell them to do. Even when we are disappointed by the results, it always turns out that they were doing what they were told to do with complete fidelity. They can only do two things: add one and one, and move a number from one place to another. If you want them to produce random numbers, you need to explain to them how to do that in terms of adding one and one and moving. Once you have explained that, the results will not be random."

Congenital

And you get some confused stares – Pricefixing

Answer 9

Because the only true source of randomness exists at the quantum level. With suitable hardware assists, computers can access this level. for example, they can sample the decay of a radioactve isotope or the noise from a thermionic valve. But your basic PC doesn't come with this cool stuff.

Susannahsusanne

Answer 10

A simple explanation for the children:

The definition of randomness is a philosophical and mathematical question, beyond the scope of this answer, but by definition there is no such thing as a "random" number. In a metaphysical sense, a number is only random in sequential form; however, there is a probability that a sequence follows certain statistical distributions depending on the sample size. A random number generator (in our case a pseudo-random number generator, or PRNG) is simply a device to produce a quasi-random sequence of numbers that we can only estimate (based on the given probability inherent within the sequence) to be random.

You should explain to the children that programs can only mimic these devices using complex mathematical formulas (which guarantee a lack of "randomness" by definition because they are a result of some function, or procedural algorithm). Typically, rigorous statistical analysis is necessary in order to differentiate the use of a quantum hardware PRNG (use this as an opportunity to explain to your kids the Heisenberg Principle!) and that of a strong software PRNG.

Homestretch

Good answer. I also think in a philosophical sense it depends on one's belief in infinity. If you assert some notion of infinite universe then all permutations must by definition exist. I think random is just a matter of scale. If our computers or perceptual apparatus are not able to detect the repetitious pattern then it is from our perspective "random enough". Take a dice roll. We except it as random, but if we were able to perceive it as the infinite set of all dice rolls we would see the pattern. Basically the entire set or permutations of dice rolls everywhere in the universe. – Mucro

Answer 11

Had to be done really

Source: http://xkcd.com/221/

Peewit

@JaredNielsen the posting was from '09 it was original then! – Peewit

Answer 12

Because there is no such thing as a random number.

Random is a human concept that we use when we cannot comprehend data and do not understand it. If we are to believe that science will ultimately lead to an understanding of how everything works then surely everything is deterministic.

Take away the human and there is no random there is only "this". It happens because it happens, not because it is random.

Pinta

This oversimplification makes it incorrect in many points. There is a lot of material to read in en.wikipedia.org/wiki/Randomness . – Patsis

In what points exactly? I can interpret many different ways in which you might disagree with me from that source. Definition being one of them. – Pinta

ever heard of quantum events? – Susannahsusanne

Yeah because we really understand quantum physics. We got that one sussed. Right? As far as i'm concerned randomness does or don't exist. It's like God, difficult/impossible to prove one way or another. Let me edit my post and put a maybe in to satisfy us all. – Pinta

I like this explanation. Mostly because we often use "random" as "now come a number we cant guess or know in beforehand what it is" – Chaing

We know we can't know everything about anything en.wikipedia.org/wiki/Uncertainty_principle. Randomness is part of our understanding of how "everything works" – Rhumb

"Random" is not a boolean concept so that you can say that something is either random or not-random. It is relative. Throw a fair dice and that is considered random, even if you could have a omniscient understanding of everything that influenced the dice to fall with that face up. – Patsis

IOW, random numbers are generally accepted to exist. Everything may be random for some value of "random". See xkcd.com/221 . Random does not describe data we can't comprehend, but the failure to relate current events to previous events. – Patsis

LOL "generally accepted to exist". So that means true, right? Random is a human interpretation. Take away the human and there is no random there is only "this". It happens because it happens, not because it is random. – Pinta

Answer 13

Because a program is a system and everything in a system is made to run with consistency and regularity. Randomness has no place in a system.

Harter

Answer 14

It is hard because given the same sets of inputs and conditions, a program will produce the same result everytime. This by definition is not random.

Moises

-1, that's not really true; computers can't be random but they certainly can appear to be random – Tedi

dude, what part of "my kids" don't you understand? – Vlissingen

I'd like to know how you can make a computer appear "random." – Moises

dude, what part of "my kids" implies an age? – Moises

To argue against that, what term would your use for your kids when they grow up? Your offspring? – Maggy

Answer 15

Algorithms to generate random numbers are inevitably deterministic. They take a small random seed, and use it to obtain a long string of pseudo-random digits.

It's very difficult to do this without introducing subtle patterns into the data. A string of digits can look perfectly random but have repeated patterns which make the distribution innappropriate for applications where randomness is required.

Naos

Answer 16

Computers can only execute algorithmic computations, and a truly random number isn't an algorithmic thing. You can get algorithms that produce numbers that behave like random numbers; such algorithms are called 'Pseudo-Random number generators'.

At various times in the past, people have made random number generators from analog-digital converters connected to sources of electronic noise, but this tends to be fairly specialised kit.

Kildare

Answer 17

Primarily because computers don't have any functions that behave in discrete, non-random ways. A computer is predictable, which allows us to program reliable software. If it wasn't predictable it would be easier to generate a random number (since our software could rely on this unpredictable method).

While it's possible to generate pseudo-random numbers, and numbers that are distributed randomly, you cannot generate truly random numbers without separate hardware. There is hardware that generates truly random numbers based on "quantum" interactions (at least according to the manufacturers). Online poker sites sometimes use these adapters for their generators.

Apparently there are even online services to provide random numbers - random.org for example.

Jhelum

Answer 18

As surprising as it may seem, it is difficult to get a computer to do something by chance. A computer follows its instructions blindly and is therefore completely predictable. (A computer that doesn't follow its instructions in this manner is broken.) There are two main approaches to generating random numbers using a computer: Pseudo-Random Number Generators (PRNGs) and True Random Number Generators (TRNGs).

Inclement

Answer 19

Actually, on most modern computers it's not hard to produce numbers that are "random enough" for most purposes. As others have noted, the critical thing is having a source of randomness. You can't just write a program that will produce randomness algorithmically, but you can observe randomness in the various activities of most computers of reasonable complexity, i.e., the ones we typically think of when writing programs. One such source is timing data of interrupts from various system devices.

At one time many computers had no way to get at this data and could only offer pseudorandomness, that is, a random, but repeatable distribution of numbers based on a particular seed. For many purposes this is sufficient -- choosing a different seed each time results in good enough randomness. For other purposes, such as encryption, this isn't strong enough and you need some randomness to start with that isn't repeatable or predictable. Today, most computers (with the exception of embedded devices, perhaps) are sophisticated enough to have a source of randomness that can generate encryption-strength random numbers. For instance, Linux has /dev/random and the .NET framework supports the cryptographically strong RandomNumberGenerator class which has a number of implementations.

Qualitative

Answer 20

Its probably helpful to distinguish between a number that is hard to predict (which a computer can create) from something that is not deterministic (which is a bit tougher for computers, and theoretically, any physical being).

Meghannmegiddo

Answer 21

It's easy to come up with an algorithm that generates unexpected numbers, that appear random in some sense. But to design an algorithm that generates true random numbers, well, that's hard.

Imagine designing an algorithm to simulate a dice roll. You can easily formulate some procedure to generate different numbers on each iteration. But can you guarantee that, in the long run (I mean, up to the infinity), the amount of times that 6 came out will be the same as any other number? When designing a good random number generator, that's the kind of commitment that you have to assume. You have to provide strong guarantees (i.e. mathematical proofs) about the randomness, if the application (e.g. lottery) requires it.

Apus

Answer 22

It is relevant to note that humans perform very poorly at generating random numbers. Computers are worse because they just follow a strict set commands. Humans can only generate good (pseudo) random numbers when following an algorithm, a set of commands. Computers are the same.

Although it should be noted that computers can gather entropy from the "environment" connected to it, like keyboard and mouse actions, what aids in generating random numbers (either directly or by seeding a PRNG).

Patsis

Answer 23

To make the computer generate a random number, the computer has to have a source of randomness to start with.

It has to be feeded a seed that can't be expected or calculated by just looking at the seed, if the seed comes from a clock then it can be predicted or calculated by knowing the time, if the seed comes from like filming a lavalamp and get numbers from the picture stream then it's harder to just look at the seed to know what next number will be.

The computer does not have an built in lava lamp to generate that randomness, thats whats make it hard, we have to substitute real randomness with some input that exists in the computer, maybe by logging passing tcpip-packets or other things, but its not many ways to get that randomness sources in.

Chaing

Answer 24

Computers just don't have suitable hardware. Ordinary computer's hardware is meant to be deterministic. With suitable hardware like mentioned here random numbers are not a problem at all.

Sutler

"Sign in required to view pre-release products and confidential documentation." – Gebelein

Answer 25

Awhile back I came across the "Dice-O-Matic"

http://GamesByEmail.com/News/DiceOMatic

Kind of interesting real world application of the problem.

Mucro

Answer 26

Its not hard, here's a couple for free: 12, 1400, 397.6

Meghannmegiddo