Pseudorandom
Numbers
15
A model or simulation is an abstraction. It provides a simplification of some complicated real-world thing or event, with many of the real-world details left out or 'abstracted away'. Think of a model airplane, which 'abstracts away' some of the details of a real airplane -- e.g., its size and weight, the materials its made of, and so on. What other models can we think of? The sculptor's model of Mt. Rushmore? A kitchen layout plan?
In this lesson we're going to look at a model of randomness.
Randomness
Real examples of random processes would be processes such as flipping a real coin, or rolling a pair of dice, or drawing a card from a shuffled deck, or picking a ping pong ball out of an air chamber (like they do when they pick the lottery numbers).
Randomness is used in lots of programs, especially games and simulations (Coin Flip, 4-bit Computer Simulator). Here are some examples of random events:
Pick 1 of 25 numbered marbles out of a completely mixed up jar of marbles. (1 in 25 chance of picking a particular number).
Flip a fair coin: 1 in 2 or 50/50 chance of it coming up heads.
Pick a card out of a thoroughly shuffled deck (4 in 52 chance of drawing an Ace).
What is a Random Event?
Think about the coin flip at the start of the Super Bowl (or some other sporting event).
What makes that a random event?
Why is it important that the coin flip have a 50/50 chance of coming up heads?
What sort of 'rigging' could occur to take away its fairness?
Could a deck of 52 cards be used (instead of a coin flip) to determine which team was on offense?
What other types of random events might suffice to select which team kicks off?
It's important that the coin flip be completely unpredictable. That's what we mean by a random event. Although we know that the chance of the coin coming up heads is 50/50, we don't know that it will come up heads when we flip it. If we did know, that would be predictable. And that would not be a random event. For example, suppose the coin used at the Super Bowl were replaced by one that had 'heads' on both sides. Then flipping the coin would be completely predictable: it will come up 'heads' the next time it is flipped.
It's even more subtle than that. Suppose you knew that a particular (unfair) coin had a 75% chance of coming up heads. That is, on average it would come up heads 3 times out of every 4 flips. Although flipping the coin is still a random event, the coin is not a good model for a 50/50 coin flip. Someone who knew that it was unfair could exploit that information to their advantage.
Technical Terminology
deterministic - A process that is completely predictable. A PRNG is deterministic.
PRNG - A pseudorandom number generator is an algorithm that generates a sequence of numbers that appears to be random but is completely determined by the algorithm. As such, a PRNG is a model or representation of randomness.
modular arithmetic - A system of arithmetic for whole numbers where the numbers "wrap around" upon reaching a certain value known as the modulus. An example would be clock arithmetic. On a 12-hour clock, the time wraps around to 1 after 12 o'clock.
Computer Randomness
Computers can't do real randomness -- they can't really flip a coin or pick a card out of the deck. Computers use a form of randomness known as pseudorandomness: that is, they simulate randomness. A pseudorandom event looks random but is completely predictable -- we say it is deterministic because its output can be known by someone who knows how the event was programmed. What looks random to the user is actually the result of a completely predictable mathematical algorithm.
When a computer application 'flips a coin', it's not really flipping a coin -- it is simulating a coin flip. Similarly, if you go to a casino and play computer poker on a machine, the computer is not really playing poker -- it is simulating a poker game. We want to understand how this works.
A Pseudo Random Number Generator
As you might expect, computers simulate randomness using numbers. For pseudo random events we use a pseudo random number generator (PRNG) which is a mathematical formula that generates a random-looking sequence. If you know the first number in the sequence, also known as the seed, then you can predict every number in the sequence.
PRNGs are useful in:
Cryptography: used to generate secret keys.
Computer games: card games, shooter games, adventure games, etc.
Simulations: weather models, astronomical models, models of biological systems, etc.
Randomness in App Inventor
App Inventor has several blocks for randomness in the Toolbox's Math drawer.
1. Random Fraction: Randomly selects a number between 0 and 1 (not including 1):
In other words, random fraction will generate numbers such 0, 0.1, 0.11, 0.2, 0.5, 0.999, and so on. It will never generate the number 1.
As you know from math class, there are an infinite number of values between 0 and 1. And they are evenly distributed between 0 and 1. A computer can't really have an infinite amount of numbers, but it can have lots of values between 0 and 1 and they would be evenly distributed along that range.
So in the real world and in App Inventor if you picked a random number between 0 and 1, you would have a 50/50 chance of getting a number that is less than 0.5. Knowing this, we could simulate a coin flip in App Inventor with the following code:
2. Random Integer: Randomly selects a number between two specified integers, inclusive:
For example, if you were modeling a die, which has the values 1 through 6 on its faces, you would use the following block:
And, if App Inventor's PRNG is a good one, you would expect to that the chances of getting a 1 or a 6 or any other value would be 1 chance out of 6.
3. Random Set Seed: Sets the seed for the PRNG:
As we will see, if you set the seed to a certain value, the PRNG will always generate the exact same sequence of numbers. This predictability can be useful when you're designing a game or a simulation.
1. Suppose your PRNG uses the following formula: Xi+1 = Xi * 2 + 1 And suppose that X1 is 12. What value will X2 have?
2.Suppose your PRNG uses the following formula: Xi+1 = Xi * 2 + 1 And suppose that X1 is 10. What are the next three numbers that the formula would generate?
3. Evaluate the following expression: 33 mod 5
4. Suppose your PRNG uses the following formula: Xi+1 = (Xi * 2 + 1) mod 13 What is the next number if the current number is 10?
5. Suppose your PRNG uses the following formula: Xi+1 = (Xi * 2 + 1) mod 13 What would the next five numbers be if the current number is 10?
Conclusion
To sum up, a PRNG is a model (or simulation) of randomness that approximates the behavior of a truly random number generator. Like our simple example, if you start from a given value (the seed) the PRNG will generate a sequence of numbers and will eventually return to the seed value. So it is completely predictable. As such it is an abstraction of true randomness. It uses a completely deterministic formula or algorithm to generate a sequence of numbers that resemble true random numbers.
What does it mean 'to resemble true random numbers'? Well, among other things, the PRNG is just as likely to generate a random fraction that is less than 0.5 as one that is greater than 0.5. If you used it to simulate a coin flip, it should generate a 'head' 50% of the time, on average. If you used it to simulate a die, it should generate a '1' every 1 in 6 rolls, on average.
Still Curious?
Read more about linear congruential generators on Wikipedia.
How Does a Slot Machine Work
Slot machines are special purpose computers that contain a random number generator chip. This no-nonsense video explains how they work and dispels some of the many myths that surround them. The bottom line: what is the only way to win on a slot machine?.
(note: watch in Firefox when not signed in)
Read more about linear congruential generators on Wikipedia.
PRNGs are also useful when securing the Internet, which is covered later in the course. For now, you can watch this video about CloudFlare and how lava lamps are helping to keep the Internet secure.