Wednesday, October 15, 2008

True randomness

Yesterday I was teaching my Intro to Programming class about making the computer pick a random number. The interesting thing about this exercise is that the computer can't pick a truly random number. It can only pick pseudo-random numbers.

Here's why: Computers usually calculate random numbers based on mathematical formulas or pre-computed tables in memory. While this gives a good approximation to truly random numbers, they are bound to produce patterns and/or distributions which aren't truly random.

In other words, if the computer were to flip a coin 100 times, you would expect 50 heads and 50 tails. The computer would probably be close, but you may eventually see a pattern if you flipped the coins long enough. Check this out if you'd like to learn more about generating random numbers.

So, how do we choose truly random numbers? Random.org uses atmospheric noise. The figure below which I obtained from their website shows the difference between random numbers from atmospheric noise (left) and using the rand() function in PHP (right). Notice the repeating patterns in the right image.

       


A lack of understanding in how random numbers are generated by computers has had serious consequences for some. Several game shows have failed in the past to produce truly random numbers, leaving themselves susceptible to gaming.

By the way, people aren't very good at choosing random numbers either. Supposedly if you ask a large number of people to choose a number between 1 and 20 (inclusive), they are more likely to pick 17 than any other number.

3 comments:

  1. Hi Frank! First I thought surely you can write a program that generates pi digits, and pi digits are random, so you can generate truly random numbers by computer... but then I found this: http://alienryderflex.com/pi.shtml :)

    ReplyDelete
  2. More about the above:
    http://en.wikipedia.org/wiki/Software_for_calculating_%CF%80

    ReplyDelete
  3. Interesting... So if you can't keep producing pi digits infinitely, you would eventually have to restart at the beginning, thus creating a repeatable pattern.

    ReplyDelete