Browse Category

Death by Cubes (Algorithmic Modelling: Pandemic) “So the probability we lose is 2/3, multiplied by 5/23, or 10/69. It’s pretty much a 6 in 7 shot.”

I met a friend for dinner and board games a while back, and one of the games we played was Pandemic. Designed by Matt Leacock, the game is themed around managing and discovering cures for diseases before they spread across the world.

Diseases are modelled using cubes, and they spread across a network of cities (which are nodes in a graph). On players’ turns, they perform actions to contain the spread of diseases, research cures for these diseases or share knowledge with other players. After they are done with their actions, players draw cards from an infection deck, where each city (node) is represented once. For each card, players need to add a disease cube of the city’s colour to the city. For example, considering a simplified network: • If D is drawn, one yellow cube will be added to D. Similarly, if E is drawn, one red cube will be added to E; if F is drawn, one blue cube will be added to F.
• A city is allowed to have a maximum of three disease cubes of each type; if a fourth cube of the same type needs to be placed, an outbreak happens. Instead of placing the fourth cube, all connected cities receive one cube of the relevant colour. For example, if C is drawn, a blue outbreak occurs in C, and one blue cube is added to both B and F.
• The rules on having at most three cubes of each type still apply when placing additional cubes, meaning that outbreaks can cause chain reactions. For example, if A is drawn, a red outbreak occurs in A. This causes one red cube to be added to B, D and E. However, B already has three cubes, meaning that a chain outbreak occurs in B; this causes one red cube to be added to A, C, E and F.
• This looks like it would loop infinitely, but there is some mercy; in a given chain reaction, each city may only outbreak once. Thus, instead of adding a red cube and triggering an outbreak again in A, no red cube is added.

The game ramps up steadily in pace, by increasing the infection rate (number of cards drawn) over time. Players lose the game when the eighth outbreak occurs, when they need to place disease cubes but can’t (these are component-limited), or when the deck of player cards runs out.

Separately, the goal of the game is to research a cure for each of the four diseases in the game, which requires collecting data on the spread of the diseases. There is a deck of player cards which contains twelve city cards associated with each disease; players need to collect five of them (in one player’s hand) and bring them to a research station. This can be tricky, as players draw cards independently, and giving cards is restricted (I can only give you a card if we’re both in the one city that is associated with that card, and if it’s my turn). At the end of each player’s turn, players draw two cards from this deck (if they can’t, the game is lost).

The deck of player cards also contains a few special event cards which help players, and more interestingly several Epidemic cards which are disruptive. The number of Epidemic cards to include is variable (4 are used in an easy game, 6 for a difficult one). When an Epidemic card is drawn, players resolve a three-step process:

1. “Increase”: The infection rate marker moves along its track, possibly increasing the infection rate (number of infection cards to draw at the end of each player’s turn). This begins at 2, but eventually becomes 4.
2. “Infect”: There is a sudden wave of disease in a new city. Players draw the bottom card of the infection deck, and the city in question receives 3 disease cubes of its colour. The usual Outbreak rules apply, though thankfully only one Outbreak occurs even if the city already has two or three cubes.
3. “Intensify”: The infection discard pile is shuffled (including the just-revealed card from the bottom of the infection deck). These cities are likely to suffer from more disease soon, especially since this happens as part of players drawing cards (before the infect phase of the current player’s turn).

Going back to the initial calculation, we were on the second last turn of a game with six Epidemic cards, five of which had already been drawn. There were three cards left in the player deck. We already had seven outbreaks occur, meaning that one more would lose the game. However, we had also cured three diseases, and the Medic which I was playing was sitting in a research station with all of the cards to cure the last disease on the next turn. Furthermore, my friend who was playing the Operations Expert held the One Quiet Night Event card, which allows skipping of the Infection phase.

Thus, the only risk of losing was drawing the last Epidemic card, and then in the Infect step revealing a city on the board which already had disease cubes of its colour (from outbreaks in adjacent cities). These events draw cards from separate decks, so their probability should be independent.

The first term is easy – there were three player cards remaining, one of which was the last Epidemic card, so there would be a 2/3 chance we would draw it. For the second term, we looked through the infection discard pile, which at that time had 24 cards (along with Sydney, which we removed from the deck using a special event card). There were thus 23 unseen infection cards; six of them corresponded to locations on the board which had disease cubes. On my friend’s last turn, we were able to defuse one of these locations, leaving a final loss probability of (2/3) * (5/23).

It turned out that we got lucky as we didn’t draw the Epidemic card, and even then the card at the bottom of the deck would have been safe. I wasn’t initially keen on doing too much of the calculation, figuring that clearing one risky place was easy but two was hard, but my friend (who is a statistician) decided to go ahead with the calculation.

On Set Collecting When I hear the word ‘set’, the first thing I think of is the computing data structure, and then the mathematical construct that that data structure is trying to model. Essentially, a set is an unordered collection of distinct objects. I’d probably then think of the Egyptian deity before thinking of the card game, or failing at a contract in bridge. That said, we recently had some interesting discussions about the card game over lunch at work.

The game consists of a deck of 81 distinct cards which each show a number of shapes. Each card has four attributes, and each of these attributes can take on three values – number of shapes (one, two or three), colour (red, purple or green), shading (shaded, striped or unshaded) and shape (diamond, rounded rectangle, ‘S’).

Initially, twelve cards are dealt to the table; players compete in real-time to identify a set of three cards where, for each attribute, the cards are either all the same or all different. The player collects these cards, and the dealer replenishes the cards on the table.

It is possible that no set is possible with twelve cards. In physical games, the dealer will, after a while, deal three more cards to the table if no one can identify a Set. We were playing on an app, though; this app waits for players to claim that there is no set available, and penalises players if they make an erroneous claim. More often than not, even though all of us were looking carefully at the board, we were too quick to declare no-set with 12 cards. However, we had one round where even with 15 cards (after one declaration of no-set), no one found anything. After a long while, someone pressed the no-set button, and indeed there wasn’t a set!

After the game, discussion turned towards finding the maximum number of cards where no set was possible. We quickly settled on 16 as a lower bound; this is possible if you only use two of the values for each of the four attributes (e.g. by throwing out all cards that have three symbols, are red, are shaded or are diamonds). Now it becomes impossible to perform matches along any attributes being different, since you need one occurrence of each of the three values; also, because cards are unique there is no set of three cards where all four attributes are the same (that would be three copies of the same card). This arrangement has $2^4 = 16$ cards.

Going beyond this is tricky, mainly because the number of possible groups of cards you have to pick from is large. There are $81$ ways of selecting the first card, and $80$ ways of selecting the second. The third would have $78$ ways, since there is one specific card that won’t go with the first and second. However, later on you can’t just deduct one card for each already selected card; for a simple counterexample, suppose I have already selected:

• (1) one red shaded diamond
• (2) one green shaded rectangle
• (3) one green shaded S

Now suppose I try and add the card (4) with one red shaded rectangle. This means that the card with one purple shaded rectangle would now become ineligible for selection, because it would form a set with (2) and (4). However, we have already eliminated this card from consideration, because it would form a set anyway with (1) and (3).

I turned to writing a quick program here. This is a standard algorithm based on depth-first search.

• Each card is represented as a vector with four components.
• There is an initial set of 81 vectors created.
• To guide our search, whenever we consider adding a card to a working set, we iterate over the elements of the existing working set and determine which cards would, together with the new card, create a set. This relies on an observation that for any pair of (distinct) cards, there is one and only one card that would form a set with the first two. We then prune these set-creating cards from the search tree.

This found sets of size 17 quite quickly, but knowing that the bound was 20, I knew that wasn’t good enough. There were several implementation tricks that I used to help speed up the search.

• This search is easily parallelisable; each branch of the search tree may be explored in parallel. A simple implementation (and what I used) could rely on Java’s parallel streams when doing the recursion, for instance. The orchestration around keeping track of the best answer needs a few small changes to be thread-safe, of course.
• If the goal is merely to find some set of size 20, then we can exploit the symmetry of the problem and fix the first card to be any card (I used 0,0,0,0), since any cap set could be re-expressed as one that contains 0,0,0,0 by permuting the assignment of attributes to variable values. There may be more clever symmetry to exploit here than what I did.
• Computing the last element of a set involves a bunch of jumps, branches and math; the result of this computation is deterministic, and can be cached so that it can be reused along different branches of the search tree. There’s probably something more clever I can do regarding overlapping sub-problems (this improves the runtime only by a constant factor).

This was sufficient to get the tool to spit out many sets of size 20, though I unfortunately didn’t churn through every possible selection, so this doesn’t show that 20 is an optimum.

Algorithmic Modelling – Codenames Codenames is a board game designed by Vlaada Chvatil which tests communication. The game is played with two teams; each team splits itself into clue-givers and guessers.

There is a board of 25 cards, each with one (or more) words on them. Of these cards, 9 are owned by the first team, 8 owned by the second team, 7 are neutral and one is the ‘assassin’.

The clue-givers attempt to communicate to the guessers which cards are owned by their team. This is done by giving a one-word clue followed by the number of cards N corresponding to the clue. The rules establish some bounds on allowed associations (for example, ‘sounds like’ clues are not allowed).

I don’t know how much time went into selecting the words to appear on individual cards, but there are certainly many words in the deck that can be interpreted in many ways, which makes the game fun. For example, I can think of quite a number of ways to clue BOND (COVALENT for unambiguity; DURATION, ASSET or DEBT for the debt; JAMES, AGENT or SEVEN or even at a stretch something like CASINO for the character; FRIEND or FRIENDSHIP; STREET or TUBE; CONTRACT, PROMISE or WORD for the idea of a promise; ADHERE or CONNECT, among others). Which one I might pick would depend on the other words on the board.

Guessers then identify up to N+1 cards they think their team owns. This can be based on the entire history of clues given, not just the previous clue. These cards are guessed one at a time; a team is only allowed to make further guesses if they guess ‘correctly’ one of their team’s cards. Teams may refrain from making all guesses.

The game ends either when all cards owned by a team are revealed (that team wins), or if a team reveals the assassin (that team loses).

In practice, clue-givers will need to consider all cards, not just the ones their team owns. The penalty for ‘failure’ varies; the assassin is an instant loss, and revealing a card owned by the other team is also bad. For example, with the cards APPLE, BANANA and GRAPE it would be very tempting to declare (FRUIT, 3) as a clue; yet, if KIWI is owned by the other team (or worse, is the assassin) it might be dangerous.

However, if the other team has already revealed that KIWI is theirs (e.g. with another clue, maybe SOUTH or BIRD) then the FRUIT clue becomes safe. Thus, pre-computing a strategy at the beginning of the game (e.g. by partitioning the eight or nine clues owned into several logical groups while avoiding other words) may not be optimal.

I tend to consider making an effort to win to be a key part of games, and thus what moves may be considered good also often depends on the state of the game. For example, if the opposing team has just one card left, I will give a broader clue that may have more tenuous links in a ‘do or die’ effort to finish on this turn. A less extreme example would be attempting weaker links if behind, or perhaps playing slightly more conservatively if ahead.

Mathematically modelling Codenames can be tough. We can try modelling the game state as a tuple $(O, E, N, x, h, f_O, f_E)$ where $O, E, N$ are sets of the remaining clue words our own team has, words the enemy team has, and the neutral words, $x$ is the assassin, $h = (t,w,n)^+$ is the history of the game, and $f_O$ and $f_E$ are preference functions of the form $h, w, n, O, E, N, x \rightarrow P$, returning an ordered list $O \cup E \cup N \cup \lbrace x \rbrace$. $(t, w, n)$ is a clue meaning that a given team gave a clue word and hinted that some number of cards was relevant. This already abstracts two difficult parts away – ordering the clues, and determining how many of the top preferences to pick.

I think the preference functions need to take into account previous clues from both teams; if a previous clue could clearly have corresponded to two words and I picked the wrong one, it might be fairly high on the list even if unrelated. Similarly if this scenario happens to the opposing team, I would probably avoid the word that would blatantly be theirs.

The notion of degree of confidence also isn’t captured as well in our ordering; going back to the fruit example, having a clear ordering would imply that clues for less than 4 items could reliably result in correct guesses (if we knew that APPLE was by a small margin the best pick, we could safely and confidently give (FRUIT, 1) to clue it, which seems wrong). One could imagine modelling these with selection probabilities, though things would be even more complex.

The above representation still seems computationally difficult to work with. The evolution of the preference function as one moves from one state to another is unclear (so in that representation it is fully general), making lookahead difficult. It doesn’t seem like a greedy choice is always best; for example, given eight clues that are reasonably divisible into four pairs, a clue for 4 words taking one element from each pair might be a bad idea if the other words can’t easily be linked.

We can proceed by simplifying the preference functions; a simple approach could be that for each $w, n$ each team has a persistent preference function that returns an ordered list of $O_0 \cup E_0 \cup N_0 \cup \lbrace x \rbrace$. The preference functions during the game then return the subsequence of that list that contains strictly the words still left in the game. This of course doesn’t take into account past information or clues from the other team.

With this, we can attempt to solve the game using standard techniques; assuming that the vocabulary of clues is bounded (let’s say it must be from the Linux dictionary), a game state is winning for the current team if there exists some word for which the preference function returns everything in $O$ as a prefix. A state is losing if all moves in that state produce a state which is winning for the opposing team.

We can generalise this to a simple probabilistic model as well; the preference ‘functions’ instead return a discrete random variable that indicates either guessing some word or passing. A simplified model could then, at the start of the game, assign weights to each candidate indicating the relative probability that candidate would be selected. These can be normalized to account for a pass probability. As words are removed from the board, the probability of the remaining words being selected scales (we can imagine a simple rejection-sampling where we discard words that aren’t actually on the board any more).

The algorithm for the probability that we get a win from a given state is then slightly more complex (though I think still reasonably covered by standard techniques).

Likelihood Estimation One of my team-mates introduced another interesting question over lunch. Working through it reminded me of some of the statistics problems I struggled with at Imperial, specifically during Intelligent Data and Probabilistic Inference. It reinforced that in spite of scoring 90 for that course I’m still not confident I knew what I was doing then (or now).

Suppose you have a symmetric triangular distribution of unknown width and mean. Given that the distribution has yielded three independent samples of 2, 4 and 5, what is the expectation of the mean?

The triangular distribution can be used as an estimate for something which is known to be bounded both above and below, that also takes into account a value known to be the most probable. Some argue that it is the simplest distribution satisfying these (though one could argue that a cosine or some kind of truncated normal might be more applicable).

The instinctive answer I have is simply the mean of the samples, or $\frac{11}{3}$, though I was suspicious as probability and statistics often yield non-intuitive results.

The distribution is named as such because it has a triangular probability density function; because of the laws of probability (area under the function must be 1), specifying the minimum, maximum and mean is enough to uniquely identify it. Supposing we have a minimum $a$, a maximum $b$ and a mean $c$, this yields a pdf of: $f(x) =\begin{cases} \dfrac{2(x-a)}{(b-a)(c-a)} & a \leq x \leq c \\ \dfrac{2(b-x)}{(b-a)(b-c)} & c \leq x \leq b \\ 0 & \text{otherwise} \end{cases}$

We are only dealing with a symmetric case, so we can set $c = \frac{a+b}{2}$ which cleans things up a little: $f(x) =\begin{cases} \dfrac{4(x-a)}{(b-a)^2} & a \leq x \leq c \\ \dfrac{4(b-x)}{(b-a)^2} & c \leq x \leq b \\ 0 & \text{otherwise} \end{cases}$

Based on our observations that we have three samples of 2, 4 and 5, we can construct the likelihood that a given triangular distribution gave rise to a certain result. While the probability sampling a given distribution resolves to a precise value is infinitesimally small, we can still compare them in relative terms using the density functions. We can write this as $P(2,4,5;a,b) = f(2)f(4)f(5)$

Expanding this term will depend on where exactly 2, 4 and 5 fall in our triangle. Let’s work out the most promising case (where 2 falls on the left of $c$ while 4 and 5 fall on its right); the rest are left as an exercise to the reader. In this case, we have $P(2,4,5;a,b) = \dfrac{4(2-a)}{(b-a)^2} \times \dfrac{4(b-4)}{(b-a)^2} \times \dfrac{4(b-5)}{(b-a)^2} = \dfrac{64(2-a)(b-4)(b-5)}{(b-a)^6}$

At this point, we notice the original question needs a bit more specification. We aren’t given what the distribution of possible values of $a$ and $b$ is. One way of getting around this is just to pick a uniform distribution; however, that isn’t quite defined over the real line. We can for now simply find the maximum likelihood estimate for $a$ and $b$.

Alternatively, if we give prior probability distributions for $a$ and $b$, we could also use the samples as information to get a posterior distribution. Usually we would pick a conjugate prior distribution that wouldn’t fundamentally change even when accounting for the sample; I didn’t find one for the triangular distribution, though.

If we want to find the most likely distribution, we seek to find an extreme point; this can be done by taking partial derivatives (and this expression actually lines up quite well with the quotient rule). There is a fairly standard ‘trick’ for handling these, though; since the logarithm is a strictly increasing function, we compute the log-likelihood instead. The maximum of the logarithm will also be the maximum of the original function. Using the laws of logarithms, we get something a lot more tractable: $\log P(2,4,5;a,b) = \log 64 - 6 \log(b-a) + \log(2-a) + \log(b-4) + \log(b-5)$

Computing the partial derivatives is then straightforward. We then set them to zero, and solve the resulting equations simultaneously; this yields $a, b = \left( \dfrac{1}{3} \left( 4 + \sqrt{\frac{2}{5}} \right), \dfrac{1}{3} \left( 16 - \sqrt{10} \right) \right), \left( \dfrac{1}{3} \left( 4 - \sqrt{\frac{2}{5}} \right), \dfrac{1}{3} \left( 16 + \sqrt{10} \right) \right)$

We’ll want the second pair of solutions; the first actually has $b \approx 4.279$ which is no good (we need $b > 5$). Interestingly, the mean of that triangular distribution is then $\dfrac{2}{15} \left(25 + \sqrt{10} \right) \approx 3.75497$ which is not quite $11/3$.

Indeed, though, the log-likelihood we get with these values of $a$ and $b$ is about $-4.74053$. Indeed, if we look at the family of distributions with $a = \frac{11}{3} - \alpha$ and $b = \frac{11}{3} + \alpha$, the best we get is about $-4.7473$.

On Challenges that Build On my return flight from Singapore to London, I listened to quite a few hours of music. Two of the songs I listened to and enjoyed at least partially for similar reasons were It’s Gonna Be Me (by NSync), and I Can’t Be Mad (by Nathan Sykes). It’s a bit of a strange pairing as the former seems to be an upbeat, relaxed pop song while the latter is a fairly moody piano ballad. However, the common element I latched on to here was that both songs feature sections that are repeated multiple times, with the vocals developing additional complexity on each iteration (thinking about it this is fairly common in songs that are critically reviewed well, and also in songs I like). For example, in It’s Gonna Be Me there is a line in the chorus which is sung four times over the course of the song, and its complexity develops: The challenges in I Can’t Be Mad have a couple of changed notes, but also (if trying to reproduce the original) demand different productions of the notes (falsetto vs not, belts, etc). There’s always a risk of adding too many embellishments, though I find expanding upon base melodies can be quite interesting. Singing these, and considering what would be reasonable for my voice (adding a closing run to the last syllable above, for instance) and what would not be (adding a +1 semitone key change after the second chorus in I Can’t Be Mad – original is already awfully hard), can be enjoyable too.

Generalising this, I quite like the idea of “increasingly complex variations on the same theme” when learning concepts and when teaching them. This already seems to happen for many concepts in mathematics. Over the course of an A-level student’s mathematics education, he/she might understand how to write a quadratic expression as a product of linear factors (e.g. converting $6x^2 - 19x - 7$ into $(2x-7)(3x+1)$). This could first begin with expressions where inspection works feasibly. However, students should also be presented with some examples where inspection is extremely difficult or even impossible (though probably only after gaining some confidence with the cases where inspection is plausible). For general expressions, one could try to use both the quadratic formula and factor theorem to factorise something like $6x^2 - 19x - 8$ into $-\frac{1}{24}(-12x + \sqrt{553} + 19)(12x + \sqrt{553} - 19)$. However, there will be some expressions like $6x^2 - 19x + 16$ where the solutions to the quadratic are not real; later, with some understanding of complex numbers, these would make sense. Students will also learn about problems which may not obviously be quadratics but can be written as such (like $x^4 + 2x^2 + 1$); the ability to synthesise the various techniques can then be tested with something like $7x^8 - 10x^4$.

To some extent my Masters project also had this theme – linear time logic, adding knowledge, adding dynamic modalities, generalising that to full branching time logic, and then switching out the infinite traces for finite traces. I haven’t written a course or a book on a computer science topic yet, but I can imagine that there might at least be sections that follow this kind of sequence.

This pattern also occurs a fair bit in many technical interviews I’ve seen as well, where problems start easy, but additional and progressively more challenging constraints are repeatedly introduced. The purposes here could include testing for a breaking point, seeing how candidates react to problems without an obvious solution, or whether they are able to synthesise additional information to come to a solution.

I find that I often learn best by practicing on smaller examples at first, and then (attempting to) generalise their conclusions to larger models, considering when these conclusions may fail or not. Having multiple variations of progressive difficulty can be useful as they can give a sense of achievement as partial progress towards an overall goal is made. Furthermore, I find understanding how changes in the problem scenario leads to the base solution method being applicable or inapplicable to be a key part of understanding as well; there is a clear need to reason about this when considering incremental variations. Going back to It’s Gonna Be Me, for example, aiming downwards at the word ‘love’ and not conserving sufficient air or energy for it might work for the first three passes, but it’s unlikely to on the last round.

There is a risk that the method can be frustrating in that it seems like it is consistently ‘moving the goalposts’, especially if one forgets that the partial goals are partial goals (and starts to think of them as complete ends in and of themselves). The standard I’m using for understanding (ability to critically evaluate applicability in novel contexts) may be seen as a little high. I also haven’t covered how to bootstrap the method (that is, how to develop an understanding of how to attack the base problem before any variations are introduced). Nonetheless I think there are some contexts where this works well. I’ve found it to be useful in singing, mathematics and interviewing at least!

Making Heads of Tail Risks I remember that I was fairly anxious at the beginning of my fourth year at Imperial. I was concerned about securing work after university. Looking back, this seemed patently ridiculous; I had topped my class for the third time and already had a return offer in hand from Palantir. However, owing to sweeping government rhetoric about controlling post-study work visas at the time, I saw “not being able to get a work visa” as the primary risk then, even if it was remote. That statement in and of itself was probably correct, though the time I spent to monitor and mitigate that risk (reading up on government committee reports, and considering alternatives like a H1B1, EU blue card or doing a Tier-2 ICT after a year) was excessive.

Of course, this never materialised; and even if it did, the only likely impact would be that I’d have to fly home to Singapore in between finishing uni and starting work (I did not; though on hindsight that might have been a good thing to do).

I’m not sure when I first became aware of the concept of probability distribution functions (or, for that matter, continuous random variables). These functions are continuous, take on nonnegative values and integrate (across all variables) to 1. In the case of single variable functions, one can plot them on a two-dimensional graph; one may get results looking somewhat like the picture above, in some cases.

Areas of regions underneath the graph are proportional to the probability that a value falls in that region. For example, a uniform distribution would have a probability function that’s just a horizontal line. The graphs for the return of investments 1 and 2 in the example above follow what’s called a normal distribution; investment 3 follows a Student’s t distribution which has fatter tails.

Since areas are proportional, a simple technique for generating random values from an arbitrary distribution is called rejection sampling; if one draws a box around the distribution and throws darts randomly at it, one can take the x-coordinate of the first dart that lands underneath the function as a representative random sample.

That’s a basic mathematical introduction. If we had to rank the quality of the return profiles above (remember: right means higher returns), a lot would depend on what we were trying to do. I would personally rank investment 2 (the green curve) on top; it has a considerably higher mean return than investment 1 (blue) and adds only a small amount of variability. We can calculate what’s known as the standard deviation of a given distribution; this is a measure of how much variability there is with respect to the mean. In fact, the blue curve has a standard deviation of 0.6; this is 0.7 for the green curve.

Ranking investments 1 and 3 is more difficult; the mean of 3 is higher, but you add a lot of uncertainty. I’d probably rank them 2, 1, 3. However, there is also an argument in favour of investment 3 – if one is only interested if the returns exceed a certain level. It’s a similar line of argument where if you’d ask me to double a large sum of money (nominally) in 20 years, I’d pick a bond; 10 years, a general stock index fund, and 10 minutes, probably blackjack or aggressive forex speculation.

Whichever investment we pick, it’s possible that we may get unexpectedly awful (or excellent!) results. The standard deviation could give us some measure of what to expect, but there is still a non-zero probability that we get an extreme result. For the normal distributions (the blue and green curves), there is a 99.7% probability that a single observation will be within three standard deviations of the mean; this does also mean that there’s a 0.3% probability it does not, and about a 0.15% probability it’s lower than three standard deviations below the mean.

Tail risk refers to the risk of events that may have severe impact but are low-probability; considering them is important. Going back to the work visa situation, I think I correctly identified visa policy changes as a tail risk, though in hindsight controlling the amount of time spent mitigating them was done poorly – akin to spending $10 to insure against a 1% probability of$100 loss (provided the $100 loss wasn’t crippling – which it wouldn’t have been). I also spent a lot of time focusing on mitigating this specific tail risk, when perhaps a better solution could be developing resilience to general tail risks that may affect my employment. The obvious routes at the time would have been continuing to do well academically and develop my skills, though others exist too – such as having a greater willingness to relocate, living below one’s means and building up an emergency fund. There are still further tail risks that the above wouldn’t address (e.g. a scenario where computers and automation are universally condemned, all countries practice strict closed-border policies and the global fiat money system collapses) but the costs in mitigating those risks seem untenably high. I haven’t read Antifragile yet (what I describe here is weaker, as it doesn’t demonstrate benefiting from low-probability events), though that’s planned to be on my reading list at some point in the future. Quantitative Challenges I spent about two to three hours studying and then working through mathematical problems on quantitative finance today. Specifically, these were questions from Blyth’s An Introduction to Quantitative Finance and dealt with interest rate swaps. These are contracts where one party typically pays fixed payments (e.g. 5%) and receives floating payments, which are dependent on market rates (e.g. LIBOR + 1.5%), though float-float swaps exist too (e.g. across currencies). Swaps can be used to mitigate interest rate risk (or gain exposure!); they can also be mutually beneficial depending on companies’ borrowing characteristics. If I had to classify the mathematics involved in the problems I did, beyond “applied” I’m not sure how else I could label it. For many of these problems, the first steps involved figuring out how to mathematically model the financial products involved. There then followed some elementary algebra, along with proofs that required some intuition to pick the right approach (for lack of a better word). The exercises I did this time around relied less on probability than normal; much of this probably stemmed from a result that forward interest rates (i.e. the interest rate you’d get from future time T1 to later future time T2) could be valued independent of the distribution of possible values. I’ve struggled quite a fair bit with the book, both in terms of the reading material as well as the exercises. Today’s chapter was relatively easier, though that might have been because I was reading through the chapter for the second time. It was my first time doing many of the exercises, though it seems like they went relatively smoothly today. Some of this might be because I work through the chapters at a very relaxed clip of about one per month. Like many other mathematical domains, there tend to be many dependencies on previous topics. The earlier result I mentioned on forward interest rates, for example, was from the previous chapter; yet, it was instrumental in computing the valuation of a swap. There are certain fundamental ideas that I learned way back in 422 (Computational Finance at Imperial). I also think my mathematical knowledge and logical intuition have (hopefully) mostly stayed with me. Furthermore, I like to think that I remember the concepts at a high level. However, many proofs require recognizing that expressions are in certain forms and can thus be rewritten; I’m still yet to develop that level of familiarity – or shall I say intimacy – with the content. This might also be partially self-created, especially where the reading material is concerned. When I see theorems, I tend to try my hand at proving them on my own first. These often prove to be rather tricky endeavors; the aforementioned lack of keen familiarity with the material certainly doesn’t help. Typically, I can understand the proofs fairly easily when reading them. However, I usually expect myself to figure out the intuition behind the proof (including reproducing it, at least at a high level), which isn’t always so forthcoming. That actually reminds me of what I used to do at Imperial for certain modules, especially the (in my opinion) two hardest of the course: 438 Complexity and 493 Intelligent Data and Probabilistic Inference. I would make the effort to understand why many of the proofs in those courses worked. I’d also try to figure out how the author might have come up with the proof, or at least what the core intuitions might have been. This included relatively nasty ones (e.g. SAT being NP-complete via direct argument, or ELBO results in variational inference), and I think it paid off in terms of understanding. It could be argued that finding the material difficult is expected, because the subject matter is itself complex. I tried to obtain a popular estimate of the complexity of the material covered by the book, but didn’t find much data; there were only a handful of reviews on Amazon, which offered a wide spectrum of views (from “[o]ne of the best introductory treatise (sic)” to “I would hardly call it an “Introduction” to quantitative finance”). I’m not sure how to start more simply, though; there is a fair bit of assumed mathematical knowledge, but this is at least partly spelled out in the introduction. While the book has proved challenging at times, I’ve not found it too hard to follow. Discussing the problems with a friend has also helped a fair bit, especially since the book doesn’t have solutions! What Does “Likely” Mean? (Estimative Probability) I typically take some time out on Saturday mornings to do some reading. This often begins with developments in personal finance or computer science, though there’s a tendency to branch out from that; I generally don’t restrict myself from going off on tangents. For some reason, this week I came across a Masters thesis discussing communication of probabilities, specifically in the intelligence domain. It seems that I found it via A Wealth of Common Sense, a blog concerning personal finance that I read occasionally; there was a link there to a Library of Economics blogpost discussing issues with mapping qualitative descriptions to quantitative probabilities. For example, if I say that something is highly likely to happen, I would be implying that I believe it would happen with probability at least N; however, the numerical value of N is uncertain, and differs among different people. For me at least, N would be around 80 percent (and, incidentally, the author of that post agrees); that said, I can certainly envisage people assigning values of N as low as 0.6 or as high as 0.95. Note that the problem can also be two-tailed (e.g. about evenmightpossiblenot inconceivable). The LoE author’s son proposes a reasonable scheme, which is to have authors outline their own mapping in a glossary. This is probably (well, I mean P >=0.7) a good first step, though there are implementation challenges in terms of length as well as completeness. It turns out that the concept of words of estimative probability is treated very seriously in the intelligence domain. It is understandably important, as briefs are typically prepared in natural language, and often need to be communicated to audiences that may not be entirely comfortable with mathematical notation. To quote a CIA officer: Most consumers of intelligence aren’t particularly sophisticated when it comes to probabilistic analysis. They like words and pictures, too. My experience is that [they] prefer briefings that don’t center on numerical calculation. That’s not to say we can’t do it, but there’s really not that much demand for it. Furthermore, deriving highly precise (though possibly not highly accurate) estimates for probabilities is almost certainly (*cough* I mean P <= 0.03) pointless, and is likely (P >= 0.7) damaging in that it tends to (P >= 0.6) give a false sense of security and accuracy when that does not actually exist. The original proposal divides probabilities onto a seven-point scale (arguably five, as the ends are meant to reflect absolute certainties): certain, almost certain, probable, chances about even, probably not, almost certainly not, impossible. I think most people would agree that the above ordering is in decreasing order of probabilities. Of course, strictly adhering to the above labels would impart a degree of awkwardness to writing, and a group of variants for each level (such as highly doubtful for almost certainly not) soon developed. Interestingly, the author also gives possible a fairly specific meaning; he defines it to mean “greater than zero and less than one” (which makes sense; of course, something always happening is certainly possible – but it seems pointless to not use the more precise word), but also adds the restriction that “no numerical odds (can) be assigned”. This seems like a useful construct, especially in the early stages of knowing things when uncertainty tends to be high; the other descriptive terms were conceived with uncertainty ranges of about 10% on each side. The author of the Masters thesis also considers how words of estimative probability are used in other fields. I found the comparison to weather forecasting particularly interesting, as the author rightly points out that that is one field in which the general public is given numeric estimates (of the probability of precipitation). Weather forecasters typically add their own prose when reporting as well, which allowed some comparison. That said, a major difference is that in forecasting, these estimates can be derived with fair precision (and, as it turns out, accuracy) as they can (and, in the UK, do) originate from predictive models of atmospheric conditions. There seem to be standardised terms as far as the US National Weather Service is concerned, though I wasn’t able to find comparable guidance from the UK Met Office. The clarity required from words of estimative probability depends on the consequences of miscommunication, as well. This is of course important in intelligence, with some claiming that there was miscommunication regarding warnings related to the September 11 terrorist attacks. Incorrectly reporting a weather forecast is almost certainly (ugh, P >= 0.95) less consequential, though people may make bad decisions concerning taking umbrellas when going out or hanging clothes out to dry. I can imagine contexts where this would also be very important (such as experimental trials in medicine or financial planning), though it seems for the most part some degree of ambiguity or even unknown disagreement is probably okay. Elevation (Hotseat: STEP I 2015) Background STEP (short for Sixth Term Examination Paper) is a somewhat difficult Maths exam that is used by several UK universities (including Cambridge, Warwick and Imperial) as part of a conditional offer for courses in Mathematics and Computer Science. A part of my conditional offer for Imperial included a 2 in any STEP paper of my choice, though it was paired with a relatively awkward 35 points for IB – perhaps because the rest of my portfolio was pretty strong. There are three papers – I, II and III; III includes A Level Further Mathematics content, while I and II remain within the A Level Mathematics syllabus. I is also somewhat easier than II; that said, I think both papers exist because Cambridge does sometimes want students who didn’t take Further Mathematics to get a pair of grades in these exams. Nonetheless, STEP I itself is certainly no pushover. Students are graded on a scale of S, 1, 2, 3, U; the 2015 STEP I paper had 73.1 percent of students scoring at least ‘3’ (the lowest pass grade), and just 42.6 percent scoring at least ‘2’ (the lowest grade many universities would consider). This may be compared with A Level mathematics in 2015, where the analogous metrics of A*-E and A*-C respectively are 98.7 and 80.8 percent; and this is even before we factor in selection bias. Each paper consists of 13 questions, but candidates are only required to pick six of them; their highest-scoring six questions will be used to determine their final score. Questions have equal weight (and each is marked with integers out of 20, which seems suspiciously similar to how I’ve seen this done at many universities!). Eight of the 13 questions are classified as “pure mathematics” and include tasks testing concepts like calculus, trigonometry, algebraic manipulation, series and even number theory. Three are classified as “mechanics”, typically requiring calculations on Newtonian mechanics, and two as “probability and statistics”. I almost always do 4/0/2 or 3/1/2. Note that it is possible to attempt seven or even more questions as a form of “insurance”, though given the strict time constraints this is likely to be difficult. Performance I had a fairly decent run, picking up 114 out of 120 points; mainly losing these to minor slips/cases where an important statement was not explicitly asserted, and a good chunk in question 7 with not clearly handling a case which was expected to be shown to bear no fruit (I thought it was rather obvious that it was not needed, and dismissed it in one line). The last row indicates the order in which I attempted the problems; it seems this was generally consistent with how long I actually took on them (problems 2 and 13 were fast; 1 and 8 were somewhat in-between, and I struggled for a bit with 12 and messed up 7 while using up a fair bit of the time). Note that the “break-even” time if one wants to answer all questions would be 30 minutes per question. Selected Problems in Depth Problem 8: Series Division First, prove that $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$ and $(N-m)^k + m^k$ is divisible by $N$. Then, consider $S = 1^k + 2^k + 3^k + \ldots + n^k$ Show that if n is a positive odd integer, then S is divisible by n, and if n is even then S is divisible by n/2. Show further, that S is divisible by $1 + 2 + 3 + \ldots + n$. The two lead ins were simple. Induction does work but in both cases there were much better methods that could be used (write the series twice and pair terms up, and then pair terms in the binomial expansion). Later parts involved pairing S with a zero term, but the general theme of “pairing terms” persisted throughout the question. I think the toughest part of this one was, knowing that one had to show divisibility by $\frac{n(n+1)}{2}$ at the very end, figuring out that it was safe to split this into two terms and show them separately. This works because the highest common factor of $n$ and $n + 1$ is 1. My number theory was a bit rusty so I wasn’t sure if that was correct, and proved it during the paper. Problem 12: On Fish Distributions The number X of casualties arriving at a hospital each day follows a Poisson distribution with mean 8. Casualties require surgery with probability 1/4. The number of casualties arriving on each day are independent of the number arriving on any other day, as are the casualties’ requirements for surgery. (After some initial work) Prove that the number requiring surgery each day also follows a Poisson distribution and state its mean. Given that in a particular random chosen week 12 casualties require surgery on Monday and Tuesday, find the probability that 8 casualties require surgery on Monday (as a fraction, in its lowest terms). This one really wasn’t too bad, though it involved a lot of algebraic manipulation and it seems I took quite a long time on it when doing the paper. Essentially, the independence condition should hint that if we have X casualties, the probability of S needing surgery is clearly binomially distributed. X itself is a random variable, but that’s fine; the law of conditional expectation gives us $P(S = s) = \displaystyle \sum_{t = s}^{\infty} P(S = s | X = t) P (X = t)$ and a suitable substitution yields this: $P(S = s) = \displaystyle \sum_{t = s}^{\infty} \left( \frac{t!}{s! (t - s)!} \times \left( \frac{1}{4} \right)^s \times \left( \frac{3}{4} \right)^{t-s} \times \frac{e^{-8} 8^t}{t!}\right)$ After some fairly involved algebraic manipulation, one can indeed recover a Poisson form for the pdf of S. Using this, the last part is relatively simple actually; we want $P(S_1 = 8 | S_1 + S_2 = 12)$ and relying on the fact that a sum of independent Poissons is Poisson itself (so the means of $S_1$ and $S_2$ are 2 each gives us that the mean of $S_1 + S_2$ is Poisson, and with mean 4). Problem 13: Probability and State Machines Already covered in a previous post. I dispatched this one very quickly, though I was already familiar with the Markov process model that I used here. Meta-Analysis The main datasource we have available here is an Examiner’s Report that discusses to some extent what happened (though we don’t have full details). The grade boundary for an S is 96, so a 114 is comfortably in that range; 3.5 percent of candidates scored that. Question-level data isn’t published beyond the comments in the Examiner’s Report. Focusing on the questions that were attempted, my opener Q1 which was a test of curve-sketching was also the highest-scoring question on the paper, with students scoring an average mark of over 13.5 (with caveats that some students were worried about curve sketching and thus avoided it). This was the second “easiest” question as far as I was concerned. The other pure maths questions I attempted (2, 7 and 8) were also popular, and attempted with varying degrees of success (questions 2 and 7 were the second and third highest scoring questions). Probability and Statistics for some reason seems to always cause issues for students attempting these papers, with mean scores in the 2-3 range, though having done Olympiads in the past (and specialising in combinatorics and probability) I understandably found these easier. Generally, STEP I for me tends to be fairly tough but certainly comfortable, II is solidly difficult, and doing III often makes me feel like a dog behind a chemistry set (“I have no idea what I’m doing”), especially since I didn’t take Further Maths in high school. Probability and State Machines Suppose you have a fair six-sided die, and repeatedly toss it. What is the probability that you throw exactly one 4 before your first 6, or you throw exactly one 5 before your first 6 (inclusive or)? (STEP I Q13, 2015) There are several ways to approach this problem. There’s a “conventional” method that involves careful use of binomial series (and that was the approach taken in the mark scheme). However, the approach I used for this was somewhat different; some of it may be attributable to my computer science (or perhaps even logic/verification) background. We can model this event using a finite state machine, where each state has a transition distribution that indicates the probability of transitioning to each other state in the state machine. For example, we can consider a simpler problem: what is the probability that you throw exactly one 4 before your first 6? Well, we can be in multiple “states”: • We could not have rolled anything of significance yet. In this case, we have a 4 in 6 probability of staying in this state (1, 2, 3 or 5); a 1 in 6 probability of immediate failure (rolling a 6), and a 1 in 6 probability of registering a 4. • We could have already registered a 4. In this case, we again have a 4 in 6 probability of staying in this state (1, 2, 3 or 5), a 1 in 6 probability of success (rolling a 6), and a 1 in 6 probability of failure (rolling a 4). • We could already have succeeded or failed. Additional rolls won’t change anything in these cases. This can be modelled as the following state machine: We can then compute a success probability for each state – that is, “given I’m in this state, what’s the probability I succeed”? • The success probability PS of the state Pass is 1, and that of Fail is 0; we write this as PS(Pass) = 1 and PS(Fail) = 0. • PS(4) is a bit more interesting; it is $\frac{4}{6}PS(4) + \frac{1}{6}PS(Pass) + \frac{1}{6}PS(Fail)$ and solving this yields half. This is intuitively expected; at this point, we’re counting on rolling a 6 before rolling a 4, and on a fair die the probability of that is half. • We can now determine PS(Start); this is $\frac{4}{6}PS(Start) + \frac{1}{6}PS(4) + \frac{1}{6}PS(Fail)$. Solving the equation yields the answer of $\frac{1}{4}$. Note that we could only use this approach because, with the way we’ve defined the states, the process is memoryless; that is, the transition probabilities depend only on the current state. We could try to directly construct a state machine for the original question (either exactly one 4 or exactly one 5 before the first 6, or both), though it seems that the requirement of memorylessness makes things somewhat complex; we would need states tracking whether we experienced zero, one, or two-plus of each number. We can use a well-known probability axiom here, though; $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ – defining rolling exactly one 4 before one 6 as event A and respectively with a 5 for event B. Furthermore, our initial exploration already yielded values for $P(A)$ as a quarter, and $P(B)$ would also be a quarter by symmetry. We thus, instead, construct a state machine for the intersection, where both need to be satisfied. • Throughout, a 1, 2 or 3 does nothing and simply puts us back in the state we were in. • As we start, we can also roll a 4 or 5, which mean we’ve got the one 4 or 5 we want; or we can roll a 6, which is an immediate failure. • Once we have a 4 registered, we want to roll a 5 which gets us into the (4, 5) state. 6 remains an immediate failure, but 4 also now becomes one (remember that we want to have exactly one 4 and exactly one 5 before our 6). • The above logic also holds for 5s, except with 4 and 5 swapped. • Finally, in the (4, 5) state, rolling a 6 yields success, but either a 4 or a 5 would become immediate failures. Here’s the result: We could use the same method of success probabilities used earlier; I’ll take a little shortcut. • PS(4,5) must be $\frac{1}{3}$ as we’re counting on a 6 being rolled before either a 4 or a 5, and with a fair die each of these has equal probability of being the first of the set to be rolled. • PS(5) is $\frac{1}{6}PS(4,5) + \frac{2}{6}PS(Fail) + \frac{3}{6}PS(5)$, which gives us $PS(5) = \frac{1}{9}$. By symmetry, we can be sure that $PS(4) = \frac{1}{9}$ too. • PS(Start) is $\frac{3}{6}PS(Start) + \frac{1}{6}PS(4) + \frac{1}{6}PS(5) + \frac{1}{6}PS(Fail)$. Solving that yields $PS(Start) = \frac{2}{27}$. We’re not done yet, though, as this isn’t what we wanted. We wanted $P(A \cup B)$; but now we can apply the identity and get $P(A \cup B) = P(A) + P(B) - P(A \cap B) = \dfrac{1}{4} + \dfrac{1}{4} - \dfrac{2}{27} = \dfrac{23}{54}$ which is the same answer obtained by the STEP problem-setters, though they used binomial series instead. The above approach can of course be generalised to handle expected values (on the basis that there can be multiple distinct terminal states, where each state is assigned a value). For example, if a player won a consolation prize of$21 if he ‘bust out’ (rolled a 6 before rolling either a 4 or a 5), and a full \$60 if he won, and we wanted to determine the value of the game, we could draw the graph with three terminals instead, perhaps something like this: We would then perform our computations on the expected value (EV) of each state, with terminals being exactly their value.

Also, though for our examples we didn’t have cycles in our graphs, it’s possible that in general there could be cycles. Of course, these can be handled by solving the multiple PS or EV-equations simultaneously.

• 1
• 2