Randomness – C# mini tutorial

Note: This was some teaching material I used on the degree and professional courses to explain a little about using randomness- why and how -in your applications. The courses were based around C#, but are easily adapted to many other languages, including Java and Javascript. Just ask for a translation! Because they were slides used as part of an in-class tutorial, some parts may raise questions as much as answer them…

Note 2: A Visual Studio project is available with some starting code, and some questions (in the form of comments) for you to try to answer, available here: rand.zip

Randomness

  • What is randomness?
  • Where can we use it in our programs?
  • How can we acquire random values?
  • How can we make some values more likely than others (weighting/non-uniform distribution)?

Randomness

Randomness is the quality of having unpredictable values. Knowing previous values should not allow us any insight into the forthcoming values.

Computers are pretty hopeless at making random numbers, and most “random number generators and really pseudo-random at best.

Randomness

Random numbers are of vital importance in cryptography, but we can also use them to balance loads across a networked system, or make a game more fun by having monsters behave differently each time we play.

We might need to make a routine “fairer” by selecting things randomly to reduce bias.

What is fairness?

Acquiring a random number

In the .net world, our main friend for getting randomness is the well-named Random class.

We need to create a Random instance (object) which becomes the engine, generating random numbers that we can use in a variety of ways.

Like many RNGs (Random Number Generators), we can seed it, to have it start what is really a predictable sequence, at a different (unknown to others) point.

Or we can just use the current time, as is default.

https://msdn.microsoft.com/en-us/library/system.random(v=vs.110).aspx?cs-save-lang=1&cs-lang=csharp

Acquiring a random number

// Create a new Random instance
Random prng = new Random();

// Get the next random integer
int r1 = prng.Next();

// Get next random int from 0 to <10 (i.e. 9)
int r2 = prng.Next(10);

// Get next random int from 5 to <20 (19)
int r3 = prng.Next(5, 20);

Find a random array element

// Let's have an array
String[] msg = { "Hi", "Bye", "Umm" };

// Create a new Random instance
Random prng = new Random();

// Print a random message
Console.WriteLine(
    msg[prng.Next(msg.GetUpperBound(0) + 1)]
);

prng.Next(msg.GetUpperBound(0) + 1) needs to evaluate to (be worth) a number from 0 to the biggest index.
By telling prng.Next() what that upper limit is, we achieve that.
msg.GetUpperBound(0) is what is worth that biggest index. For a one-dimensional array, the argument is always 0, the zeroth rank.

Find a random array element

Another common problem is where we have a constraint on our choosing that we cannot make the same choice again, but other than that, the choice should be random.

Given a list of four options, we have full choice for the first “out of the hat”, but after that, we only have three to choose from, then two…for instance.

There’s a whole bunch of possible solutions here, but here’s mine (until I change my mind).

Find a random array element

Let’s duplicate the list of options, then remove random elements until the list is empty.

Since on each iteration, we’ve removed the chosen element, we can’t choose it again!

We can’t remove elements from a real array, but we can from the fancier List<>.

If you don’t need the original list to be preserved, you can skip the duplication part, of course.

Find a random array element

// make a list of options
List<int> opts = new List<int> {1, 2, 3, 4, 5};

// duplicate list items (duplicating the refs,
// not the actual objects in the collection, nor
// the collection ref itself!
List<int> optcopy = new List<int>(opts);

// Using a loop of some kind, make a random 
// selection, and remove that element.
while (optcopy.Count > 0)
{
    int i = prng.Next(optcopy.Count);
    Console.WriteLine(optcopy[i]);
    optcopy.RemoveAt(i);
}

A weighted coin (or trick dice)

With the previous example, all elements were equally likely to be chosen.

That’s because Random.Next() has a balanced distribution.

What if we want to skew that balance?

A few options present themselves. First, the easiest to understand- unbalance the options.

A weighted coin (or trick dice)

// Let's have an array
// two-thirds of the time it'll be true
Boolean[] doIt = { true, true, false };

// Create a new Random instance
Random prng = new Random();

// Print true or false
Console.WriteLine(
    doIt[prng.Next(doIt.GetUpperBound(0) + 1)]
);

A weighted coin (or trick dice)

The next option is to have a list of possible outcomes, and then a list of weights for those outcomes- i.e. likelihoods.

This avoids having to duplicate values and is much easier to edit when you change your mind. Let’s look again at the simple example of a trick coin, which comes up heads more often than tails.

First I’m going to make life a bit easier to read by having an enum called Coin that has named values for true and false- sort of aliases.

A weighted coin (or trick dice)

enum Coin
{
    HEADS, TAILS
}

Enums are a lot like classes (let’s say that for now), except we predefine all allowable instances.

For our needs, we’re using it to name values. We don’t even care what the values are (behind the scenes, they’re ints), just that we have values called HEADS and TAILS.

See in the next bit of code how they’re used.

A weighted coin (or trick dice)

Coin[] sides = { Coin.HEADS, Coin.TAILS };
double[] weights = { 0.7, 0.3 };

See how it is used to fill an array of Coin instances, the first called HEADS and the second is TAILS.

The second array, of doubles, each element corresponds to the list of sides options.

There’s a 0.7 likelihood of a HEADS outcome, 0.3 of tails.

I’m not too keen on having data that should be linked (each element in sides has an associated element in weights) being stored in independent arrays or lists.

Safer, neater, would be to create a class that is comprised of a Coin and a double- plus we would get to write encapsulation-preserving methods to prevent, say, a value for a weight being greater than 1.

A weighted coin (or trick dice)

Double r = prng.NextDouble();
Coin? selected = null;
Double band = 0.0;
for (int x = 0; x <= sides.GetUpperBound(0); x++)
{
    band += weights[x];
    if (band > r)
    {
        selected = sides[x];
        break;
    }
}
Console.WriteLine(selected);

Curves

Another approach to creating a skewed, non-uniform distribution to your random numbers, is to use a mathematical function.

This is used when we need a continuum of output, not discreet options, like in the previous examples.

You may find this useful for graphical applications especially.

Take a look at the following site, and have a play. The code is in Javascript, but you shouldn’t be afraid to take a look at some of the expressions used- Javascript and C# have a shared family tree.

http://pmb.neongrit.net/wpca/clouds/

Change the frequency setting to “English Summer”, and click the Auto button.

Clouds start to appear from the left of the screen and move across.

Note how far more clouds (although smaller) appear at the base of the screen than at the top. This is to simulate the wider field of view.

There is just one random number being generated to control the vertical position, so why is the distribution so skewed?

Curves

The usual distribution of the output from a good pseudo-random number generator looks like this:

even distribution graph

Think of each of those four bars as being buckets we can put a random number into. If it is from 0 to 0.25 it goes into the first bucket. If it is more than 0.25, and up to 0.5, it goes in the next bucket, etc. Each of these buckets will fill up, on average, to the same amount (if we run the experiment enough). This is an even distribution. No one number is more likely to come up than any other.

Curves

But what if we don’t want that? What if we want to make, for instance, bigger numbers more likely? We can’t directly change the PRNG, but we can feed the output into a function, a mathematical device for taking an input, changing it, and outputting the result.

We can picture a function as a graph. At the moment, with no change, it is like a null-function, a do-nothing function- i.e. what goes in, comes out:

null function (aka in equals out)

If we consider the horizontal axis to be the input, to find the output, we go vertically up from that point, until we hit the orange line, then look horizontally across to the vertical axis, where we can find the output value.

null function (aka in equals out)

Here we can see that for an input value of 0.25, the output is 0.25. For an input of 0.75, the output is 0.75.

Curves

So, without worrying just yet about how we do it in code, visually, you can hopefully see that if we can change the shape of that orange line, we can start to transform our input values. Imagine if the line looked like this:

graph for f(x) = x^2

If we try the same technique as before, finding an input value on the horizontal axis, and looking up the output value on the vertical axis, we can see that input no longer matches output.

graph for f(x) = x^2

Now an input of 0.25 is maybe 0.1, and even 0.75 is only perhaps 0.3 or so.

Curves

Curves like the last example are described by a function that contains exponents- numbers being multiplied by themselves. In maths we might say that f(x) = x2. The computer code might look something like:

output = input * input

How does it work? Well, remember that we’re dealing with numbers from 0 to (usually) almost 1. And when you multiply a number by less than 1, the answer is smaller. So if the number you start with is less than one, and you multiply it my itself, is gets smaller. And a tiny number gets really little!

Curves

If we go back to our earlier histogram, and ran the experiment again, but this time using our new friend the function, we will see the skewed distribution:

skewed distribution histogram

Curves

To explore curve-making functions, you could do worse than check out this site, which I have pre-filled with a few curves:

GraphSketch.com function graphs

Leave a Reply

Your email address will not be published. Required fields are marked *