AP Computer Science A

Randomness

Many programs need to have some random component, e.g. making a random choice or rolling a virtual die in a game. Computers, being deterministic machines, can’t actually generate truly random values but most programming languages provide a way to get pseudo random values which are random enough for all practical purposes but which are actually generated in a deterministic, mathematical way.

In Java the starting point for (pseudo) randomness is the method Math.random(). This method returns a uniformly distributed value between 0.0 and 1.0, including 0.0 and excluding 1.0. That is, it returns a value that may be exactly 0.0 but will always be at least very slightly less than 1.0. (It can get as close as 0.9999999999999999). And uniformly distributed that all the values in that range are more or less equally likely.

However, usually we don’t just want a random number between 0 and 1. So it’s useful to know a few recipes for turning values in that range into more useful random values.

A random coin flip

Perhaps the simplest kind of random value is a coin flip: heads or tails; yes or no. In a program that will often look like an if statement where the condition should be true half the time and false half the time so we can then do one thing or another.

if (something here) {
  System.out.println("Heads: I win!");
} else {
  System.out.println("Tails: you lose.");
}

To fill in “something here” we just need to use Math.random() in an expression that will be true half the time and false the rest of the time:

if (Math.random() < 0.5) { ... }

Because half the values between zero and one are less than one-half, this will be true, on average, half the time.

Do something with a given probability

Mathematicians express probabilities with numbers between 0 and 1, with 0 meaning zero chance of happening and 1 meaning a 100% chance of happening. So another way to think about the 0.5 in that coin-flip expression is as the probability of a coin coming up heads. If we replace the 0.5 with an arbitrary probability, p, the expression Math.random() < p will evaluate to true with that probability.1

if (Math.random() < 0.9) {
  // something that will happen 90% of the time
}

A random integer in a range.

Another common scenario is to generate a random integer from a given range, such as 1 to 6 to represent the roll of a die. Again there’s a simple recipe using Math.random(). First let’s generate a random number in the range 0.0 to n, not including n itself, by scaling the value in the zero to one range up to a number in the 0 to n range:

Math.random() * n // between 0 and n, but never exactly n

Clearly if Math.random() return 0, then 0 * n is 0 so that’s the lowest value it can produce. And it can get very close to n but not quite ever n since Math.random() will never return exactly 1.0. So if n was 10 the largest value it could generate would be 9.999999999999998.

To translate the value to an integer value we just need to discard the fractional part by casting to int.

(int) (Math.random() * n)

Now if the range we want doesn’t start at zero we need to also shift the generated number up or down by adding or subtracting something. For instance to translate numbers in the range 0 to 5 to the range 1 to 6 we just need to add 1:

(int) (Math.random() * 6) + 1

Random element of an array or string

If we need to pick a random element out of an array or another indexed data structure like a String or ArrayList it’s as easy as generating a random index in the range zero to one less than the length of the array or the length() of a String or size() of an ArrayList and using it with the index operator:

int i = (int) (Math.random() * somearray.length);
somearray[i] // do something with this element

This can be extended to pick an element from a 2d-array:

int r = (int) (Math.random() * grid.length)
int c = (int) (Math.random() * grid[0].length)
grid[r][c] // do something with this element

Random sample

Sometimes we want to pick a random element from a data structure where we’re not sure how many we’re picking from but we are able to iterate over all the candidates. For instance, suppose we have an array where some unknown number of positions are already filled and we want to pick a random empty position in the array and fill it with an "X".

We could pick a random index into the array but then there’d be a chance that the index we picked would point to an already filled position. We could fix that by using a while loop to loop until we find an actually empty position.

boolean done = false;
while (!done) {
  int i = (int) (Math.random() * grid.length)
  if (array[i] == null) { // we've found an empty position
    array[i] = "X"; // put an X in the position
    done = true; // and set done to true to end the loop
  }
}

If array is not too big and not too full, this is fine because we’ll probably find an empty position fairly quickly. But it’s a bit gross that it could take an arbitrary number of tries and might try the same already filled positions multiple times before it finds an empty position.

But there’s a cleverer way. We can loop through array just once but only consider the positions that are empty and pick one at random. Since we don’t know how many empty positions there are, we need a way to choose, each time we hit a new empty position, whether to make that the empty position we’ll use or to stick with one we’ve already picked. The cleverness comes in carefully choosing the probability of switching each time we see a new empty position so each empty position has an equal chance of being picked. The code to implement it is shorter than a description in English:

int p; // where we'll store the position to use
int n = 0; // the number of empty positions we've seen
for (int i = 0; i < array.length; i++) {
  if (array[i] == null) { // position is empty
    n++; // increment the number of empty positions
    if (Math.random() < 1.0 / n) {
      // the current empty position takes over
      p = i;
    }
  }
}
array[p] = "X"; // put an X in the chosen position

To see why this works consider what happens when i is the index of the first empty position. Our count n gets incremented to 1 and 1/1 = 1 so with probability 1, we set p to the current value of i. If that’s the only empty position in the array, at the end of the loop it will be the value of p.

Now consider what happens if we find a second empty position. Again we increment n and then randomly decide whether to switch to the new position with probability 1/2 which means both the first empty spot and the new one each have an equal chance of being chosen.

Now consider a third empty position. This time there’s a 1/3 chance that we switch to the new empty position and a 2/3’s chance that value of p is unchanged. And since each of the two previous empty spots had a 1/2 chance of being the current value of p, they each have 1/2 of that 2/3s chance or a 1/3 chance of being the choice after we’ve dealt with third empty spot.

And so on: for each new empty position, switch to it with probability 1 / n where n is the number of empty positions we’ve seen. At the end, however many empty positions there were, they will all have had an equal chance of being the final value of p.

This algorithm is a simple application of a technique is called “reservoir sampling” which can be extended to select an arbitrary number of elements at random in a single pass rather than just one.

Other kinds of random numbers

These randomness recipes will cover most of the common uses of randomness in programs though more complex programs such as complex simulations may need more sophisticated techniques. If you need those you should look up the java.util.random package that has a rich collection of random generators with different characteristics.

The underlying theory of generating good pseudo random numbers is also a deeply researched topic in computer science but, thankfully, not one you have to dip into unless you are particularly interested.