Mathematics in action: Risky Random Walks


A game of Risk (photo: A.R.N. Rødner)

The board game Risk, though far from being my favourite game (and rated only 5.59/10 on Board Game Geek), nevertheless has some interesting strategic aspects and some interesting mathematical ones.


Combat units in Risk (photo: “Tambako The Jaguar”)

A key feature of the game is a combat between a group of N attacking units and a group of M defending units. The combat involves several steps, in each of which the attacker rolls 3 dice (or N if N < 3) and the defender rolls 2 dice (or 1 if M = 1). The highest value rolled by the attacker is compared against the highest rolled by the defender, and ditto for the second highest values, as shown in the picture below. For each comparison, if the attacker has a higher value, the defender loses a unit, while if the values are tied, or the defender has a higher value, the attacker loses a unit.


Comparing attacker (left) and defender (right) dice in Risk (photo: “Val42”)

Working through the 65 possibilities, the attacker will be down 2 units 29.3% of the time, both sides will have equal losses 33.6% of the time, and the attacker will be up 2 units (relative to the defender) 37.2% of the time. On average, the attacker will be up very slightly (0.1582 of a unit). A fairly simple computation (square each of the outcome-mean differences −2.1582, −0.1582, and 1.8418; multiply by the corresponding probabilities 0.293, 0.336, and 0.372 and sum; then take the square root) shows that the standard deviation of the outcomes is 1.6223.

When this basic combat step is repeated multiple times, the result is a random walk. For example, with 10 steps, the mean attacker advantage is 1.582 units, and (by the standard formula for random walks discussed in a previous post) the standard deviation is 1.6223 times the square root of the number of steps, i.e. 5.1302.

The histogram below shows the probability of the various outcomes after 10 steps, ranging from the attacker being 20 units down (0.0005% of the time) to the attacker being 20 units up (0.005% of the time). Superimposed on the plot are a bell curve with the appropriate mean and standard deviation, together with five actual ten-step random walks. While the outcome does indeed favour the attacker, there is considerable random variability here – which makes the game rather unpredictable.


Mathematics in action: Probability


Dice

Today we begin a series of three posts on probability. We begin with some experiments on rolling dice. To save my wrists, I’ve used random numbers from www.random.org instead.

We begin with individual dice rolls. Rolling 1200 times, we expect each number to come up about 200 times, and the histogram below shows that that’s pretty much what happens. We expect the average (mean) of the numbers rolled to be 3.5, and for my 1200 rolls it was actually very close to that (3.495833). We expect the standard deviation of the numbers rolled to be sqrt(s − 3.52) = sqrt(35/12) = 1.707825, where s is the mean of the squares of the numbers (1, 4, 9, 16, 25, 36). The actual sample standard deviation was 1.704133. It is generally more convenient to work with the variance, however, which is the square of the standard deviation (2.904069, which is very close to 35/12 = 2.916667).


Histogram of 1200 individual dice rolls. The dark blue dots and line show the expected results.

Rolling pairs of dice, we expect a sum of 2 to come up, on average once in 36 rolls. We expect 3 to come up twice (as 1+2 and as 2+1), 4 to come up three times (as 1+3, 2+2, and 3+1), etc. The histogram below shows what actually happens.

We expect the average (mean) of the numbers rolled to be 7, and it was actually very close to that (7.019167). The great thing about adding random numbers is that the variance of the sum is the sum of the individual variances, so we expect the variance to be 70/12 = 5.833333. The actual sample variance for my 1200 rolls was 5.831993.


Histogram of 1200 dice pair rolls. The dark blue dots and line show the expected results.

There is an amusing take on dice pair rolls in Asterix and the Soothsayer, where the soothsayer is trying not to predict the result of a dice pair roll. Given the choice of numbers from I to XII, he guesses VII, which is of course the most likely outcome, and the one which actually comes up (which is the least likely outcome?).

Rolling a larger number of dice, the expected outcome follows a bell curve. The expected mean for twenty dice is 20 × 3.5 = 70 (for my 800 rolls of twenty dice it was actually 70.12). The expected variance is 20 × 35 / 12 = 58.33333 (for my 800 rolls of twenty dice the sample variance was actually 60.42113). The standard deviation (the square root of the variance) determines the “width” of the bell curve. Similar bell curves occur whenever a result is composed of a large number of independent factors (of roughly equal weight) added together.


Histogram of 800 rolls of twenty dice. The dark blue bell curve shows the expected results.


Mathematics in action: Alea jacta est and Random graphs

Having posted about the mathematics of dice, here is a way to use dice to teach a seemingly unrelated concept, that of random graphs (also known as Erdős–Rényi networks).

Random graphs are networks where the links are introduced at random, among a pre-existing set of nodes. Here, the nodes will be the numbers from 1 to N = 20. The theory of random graphs, described in the classic textbook by Béla Bollobás, is quite beautiful.

The theory of random graphs is sometimes introduced as a game involving buttons and string. However, I cannot recommend that – it leads to the most horrible tangled mess. Instead, I suggest using a pair of icosahedral (d20) dice, like this one (such dice can be obtained from games shops, although I must confess to using random.org to do my dice rolls):

The first dice roll gives 2 and 4 (we re-roll any pairs which are doubles, or which have come up before). Each pair of numbers like this represents a random link in the network. We write the numbers 1 to 20 on a piece of paper, and draw a line between 2 and 4:

The second dice roll gives 1 and 12, so we add a link between those two numbers. A common measure of the density of links is the average degree, which is the average number of links per node. In this case, the average degree is the number of links divided by 10 (not by 20, because each link connects two nodes):

We keep repeating this process, and at an average degree of 1, something interesting starts to happen. A giant component begins to emerge – one big cluster containing many nodes (accompanied by smaller clusters and isolated nodes). The giant component is more impressive with a larger number of nodes, of course.

At an average degree of around log(N), taking (natural) logarithms to the base e = 2.7182818284…, enough random links have been introduced that the network becomes connected. We have log(20) = 3.00, but for this particular set of dice rolls, the network becomes connected at an average degree of 2.5. For larger networks, this connectivity threshold becomes quite sharp.

Additional random links reduce the average distance (mean path length) between pairs of nodes. This is the average number of “hops” needed to get from one node to another. Here the average degree is 6, and the average distance is 1.758:

For connected networks with an average degree of d, the average distance will be approximately log(N) / log(d). This function is shown by the red line below (with black dots showing measured values for our set of dice rolls). For large networks, this formula gives quite a small number, and the property of having small average distances is often called the “small world” property.

There is much more to the study of random graphs, of course, but we can see that a simple pair of icosahedral (d20) dice is enough to introduce the basics.

Mathematics in action: dice

We are all familiar with dice of various kinds. With fair dice, each number will come up with equal probability, regardless of how the die is rolled. This requires a degree of symmetry – we want a die to be a polyhedron where all the faces are equivalent. The obvious candidates are therefore the five Platonic solids, in which not only the faces, but also the edges and vertices are equivalent. The Platonic solids give us the common d4, d6, d8, d12, and d20 dice:


Five Platonic dice (d4, d6, d8, d12, d20) and two pentagonal trapezohedra (d10) – photo by “Copat”

However, the Platonic solids are more symmetrical than necessary for the job. A tetragonal disphenoid, for example, makes a very good d4:


A tetragonal disphenoid makes an alternative d4 – photo by “Traitor”

What is required is that a die be isohedral (also called “face-transitive”). Each face should be equivalent. Specifically, for any numbers A and B, given the die with A on top, there should be a series of rotations and reflections that make the die look like the starting position, but with B on top. This rules out shapes like the gyroelongated square bipyramid, where all the faces are equilateral triangles, but the triangles are not equivalent (the “end” triangles differ from the “middle” triangles):


A gyroelongated square bipyramid does not make a fair die – photo by Andrew Kepert

We also want a die to be convex, so that it can land on its faces. Stellated polyhedra are excluded:


Stellated polyhedra cannot be dice – mosaic in St Mark’s Basilica, Venice

Trapezohedra satisfy this “convex and isohedral” rule, and the pentagonal trapezohedron is commonly used as a d10 (see the picture above). Trapezohedra work best with 10, 14, 18, … sides, since then pairs of faces can be parallel, and there can be an unambiguous “top” number. The cube can be seen as a special case of a trapezohedron.

For 12, 16, 20, …. sides, bipyramids make good dice (the octahedron is a special case of a bipyramid):


A bipyramid makes a good d16 – photo by “Traitor”

These are not the only shapes satisfying the definition, however. The 13 Catalan solids also satisfy it, and some of them make good candidates for dice. For example, the deltoidal icositetrahedron and the tetrakis hexahedron are both good candidates for d24:


The deltoidal icositetrahedron and tetrakis hexahedron are alternatives for d24 – photos by Jacqueline de Swart (left) and “Traitor” (right)

Some Catalan solids, like the pentagonal icositetrahedron, are unsuitable as dice because there is no unambiguous “top” number. On the other hand, there are some additional variations that are isohedral, like the hexakis tetrahedron.

For more on this subject, see Alea Kybos’ impressive dice page.