Luigi Amedeo Bianchi | Luigi Amedeo Bianchi

Combinatorial Game Theory

We are in the framework of games with perfect information. [add]

As a guiding example we consider the game of Nim, or to be more precise 3-Nim. We have three heaps of objects (say coins) and two players. On each turn, a player has to remove a positive number of coins from one heap. If a player is not able to move (that is, there is no coin left), that player loses and the other one wins.

There are two things to notice here. On one hand, the formulation given here is not equivalent to saying that the last one to pick is the winner, since we want to be able to consider the case $(0,0,0)$ . On the other hand, there are several variants of Nim, including one where the one left with the last coin is the one who loses.

As already hinted in the previous paragraph, there is a nice representation of each turn of the game, as a vector in $\mathbb{N}^3$ . Also, notice that each move decreases the sum of the components, so we know that the game ends, and we also know that one of the two has to lose (and one has to win, no ties are possible).

Question: is it possible, given the initial state $(n_1,n_2,n_3)$ , to determine if a player has a winning strategy and, in case, which is this strategy?

We can start with some examples: $(0,0,0)$ is clearly a losing state for the player about to take its turn. Similarly, $(1,0,0)$ (as well as rearrangements: states are always equivalent under permutations) and in general $(n,0,0)$ for $n>0$ is a winning state for the player about to move. Notice moreover that with $(1,0,0)$ the player cannot lose, even if they wanted, whereas with $(n,0,0)$ with $n>1$ the player has to play well not to lose. But we assume that both players are rational and play their best strategy. Moving on, $(1,1,0)$ is clearly losing for the player about to move, as is any $(n,n,0)$ state with $n>0$ , while $(n,1,0)$ il winning for the player about to move, as is $(1,1,1)$ .

Proceeding by examples, we cannot really find a general strategy, so let’s try a different approach. In particular, since each move can be on a single heap/coordinate, we can consider the 3-heap game as a combination of three different games, each with a single pile. This opens up an interesting perspective but requires us to formally state what we mean by “combination” of multiple games. Given two games $G_1$ and $G_2$ , their sum $G_1\oplus G_2$ is a game in which at each turn the player can decide whether to move in the game $G_1$ or in the game $G_2$ . In particular, we can see the 3-Nim as a sum of three 1-Nims, each corresponding to a column.

In order to harness what we have defined (that is, an operation), we want to associate to every (Nim) game a number, called nimber. We proceed in the following way. The Nim game $(0)$ has nimber 0. Given a game, we list all the possible moves (each of these provides a different game, with less coins) and we list all the corresponding nimber; the nimber of the game we started with is the smallest nimber not in the list.

If we consider only games of 1-Nim, nimbers are quite boring: they are just the number of coins in the heap. However, things start to be interesting when we move to $k$ -Nims with $k>1$ . Take for example the 2-Nim game $(1,1)$ . There is only one move possible (up to the choice of the heap): remove one coin and be left with the game $(1,0)$ . This game is the same as the game $(1)$ , so it has nimber equal to 1. Hence the nimber of $(1,1)$ , that is the smallest nimber not on the list, is 0.

How is this related to the sum of Nim games? Well, we can see that the nimber of the Nim sum of two games as the Nim sum of the nimbers of the two games. For example: $\mathop{nim}(1,0)=\mathop{nim}(1)\circleplus\mathop{nim}(0)=1$ . Also, as seen earlier, $\mathop{nim}(1,1)=\mathop{nim}(1)\circleplus\mathop{nim}(1)=0$ . We can construct the table of the Nim sum of nimbers:

$\oplus$	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0

The Nim sum table for the first 8 nimbers

How do we fill this table? Since $n\oplus m$ is the nimber of the 2-Nim $(n,m)$ , we can use the definition, and look at all possible moves in that game. What are these moves? We can reduce the number of coins in one of the two heaps (but not both), so we are moving either up along the column or left along the row. The nimber we have to write at the intersection of the row labelled $m$ and column labelled $n$ is the smallest that does not show up neither in the leftmost $n$ cells of the $(m+1)$ -th row nor in the first $m$ cells from above in the $(n+1)$ -th column.

This operation might look familiar: it can be written in a different way as the logical XOR of the nimbers written in binary. For example $5\oplus 3=101 \mathop{XOR} 011=110=6$ .

Notice that we have defined the operation for two games, but since the sum of two games has a nimber and can be considered equivalent to the 1-Nim with that nimber, we can go on and sum an additional game, and so on. We can also check that the operation is commutative and associative.

Now we can finally go back to the problem we had: which player has a winning strategy? We can now state the answer as a theorem.

Theorem: A Nim game is losing for the first player if and only if its nimber is 0.

To prove this result, we can go through two lemmas.

Lemma: If the nimber of a Nim game is 0 before a move, any legal move will result in a Nim game with nimber greater than 0.

Remember that any move takes us either left or up from where we are. We can be in a 0 only if there are no zeros left or up, because of the way we defined the nim sum.

Lemma: If the nimber of a Nim game is greater than 0 before a move, there exists always a move that will result in a Nim game with nimber 0.

This is specular to the previous one: if we were not able to put a 0 in the intersection of row and column, it means that there is at least a zero, either up or left.

The two lemmas give us not only the theorem, but they also tell us the winning strategy (if possible): always end your move on a 0, so that the other player has no winning move.

As a nice aside, we can also define a product between nimbers, the Nim product $\odot$ . The Nim product $n\odot m$ of two nimbers is the smallest nimber that is not in the list

$\tilde{n}\odot m\oplus n\odot \tilde{m}\oplus \tilde{n}\odot \tilde{m}, \quad \tilde{n}<n, \tilde{m}<m.$

The construction of the table of $\odot$ for the nimbers smaller than 8 is a nice exercise.

Orbital mechanics – Part 2

For part one, follow this link: there we answer the question “how to stay in orbit”. In this post, we want to figure out how to change the orbit we are in and, in particular, how to get into orbit.

How to change our orbit

Let us assume we are in an elliptical orbit, and that we change our velocity with an impulse (instantaneous change of velocity) along the same velocity vector we had previously when we are at perigee (this is just for simplicity, to fix a special point). What happens?

Orbital mechanics – Part 1

How to stay in orbit

This introduction only focuses on some aspects of celestial or orbital mechanics. In particular, we will stick to planar orbits, which we can assume equatorial for simplicity. Moreover, we will always consider two-body approximations. There will be some other simplifications, but we will mention them later when they become relevant.

The questions we want to answer are: how to go in orbit, how to stay in orbit and how to change orbit. We start, in this post, with the second one.

Independence and conditional independence

When considering independence and conditional independence, there are several well-known examples to show that neither implies the other. However, even though one can intuitively grasp that conditional independence does not imply independence tout-court, there is one special case that challenges intuition a little bit.

We want to show here that if two events $A$ and $B$ are independent conditional to a third event $C$ and also to its complement $C^C$ , then the two events are not necessarily independent, as it is shown in the following example.

Bayes’ Theorem – Part 2

In the previous post, we have seen Bayes’ theorem and a way to use it in the framework of updating mathematical models. We concluded by foreshadowing multiple updates of a model (or a belief) following multiple experiments. So this is where we take off now.

Assume that we have two experiments $E_1$ and $E_2$ . In the example we have seen in the first part, this could be “The first student I ask is in the program focused on Models” and “The second student I ask is in the program”. What we want to compute is our belief a posteriori, after both replies:

$\begin{align*}P(H|E_1, E_2) &= \frac{P(E_2|H, E_1)\cdot P(H|E_1)}{P(E_2|H, E_1)\cdot P(H|E_1)+P(E_2|H^c, E_1)\cdot P(H^c|E_1)} \\& = \frac{P(E_2|H, E_1)}{P(E_2|H, E_1)\cdot P(H|E_1)+P(E_2|H^c, E_1)\cdot P(H^c|E_1)}\\&\phantom{=}\cdot \frac{P(E_1|H)\cdot P(H)}{P(E_1|H)\cdot P(H) + P(E_1|H^c)P(H^c)}.\end{align*}$

Bayes’ Theorem – Part 1

In the first post, we discussed the importance of model updating, now we want to focus on the mathematics that comes into play. To do so, we will make use of Bayes’ theorem. In particular, we will need an alternative formulation of the (hopefully) well-known result.

First of all, we will briefly revise conditional probabilities.

Definition. Given two events $A$ and $B$ in a probability space, with $P(B)\neq 0$ , the conditional probability of $A$ given $B$ is the quantity
$P(A|B)=\frac{P(A\cap B)}{P(B)}.$

The idea is the following: we know that some event ( $B$ in the definition above) has happened, and we want to renormalise our notion of probability to the new reality we are living in, the one where $B$ is certain, as it already happened. One can notice that the conditional probability with respect to $B$ is itself a probability measure, and, in particular, satisfies all the properties of a probability. At the same time, it is worth noticing, with an example, that $P(A|B)$ , in general, is not equal to $P(B|A)$ . Among inmates in Italy, roughly 90% are male, so we can write $P(\text{male}\,|\,\text{inmate})=90\%$ . However, it is definitely false that the probability that an Italian male is an inmate, that is $P(\text{inmate}\,|\,\text{male})$ , is 90%. At the same time, the two probabilities are connected with one another, as the following result shows.

Theorem (Bayes, probability form). Given two events with nonzero probability $A$ and $B$ , the following identity holds:
$P(B|A)=\frac{P(A|B)\cdot P(B)}{P(A)}.$

Fermi estimates

Let us start with the following problem.

Problem: Giovanni is an Italian man, soft-spoken and very calm. He enjoys sharing what he knows and learning new things. He wears glasses and is particularly fond of logic puzzles. Is it more likely that Giovanni is a high school teacher or a metal worker?

Let us start with a gut answer: given the description of Giovanni, we can easily see him as a teacher, he really fits our stereotypical description. At the same time, we want to go a little beyond the gut answer: is there a way to give a more “mathematical” or “scientific” assessment? We can split the problem at hand into smaller ones: we want to figure out how could we come to an answer, what data we have and how can we get from the data to the answer.

Mathematical models

The new term has begun, and so has my new course, Mathematical Models for the Physical, Natural and Social Sciences. This is a course offered to master students in Mathematics, in particular those enrolled in the Teaching and Science Communication curriculum.

In the first class, we discussed what a mathematical model is, and what it is not. To begin with, we had some examples of mathematical models suggested by the students: the SIR model, ever-present in these days, the optimisation of industrial processes, the optimisation (or hedging) of an investment portfolio. We continued with some questions:

What are the questions that we want to answer with our model? Or, in other words, why are we considering a mathematical model in the first place?
What are our variables and our data? Which kind of data can we have?
Where does data come from? Why is it relevant?
Who develops a mathematical model?

$\oplus$	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0

$\oplus$	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0

$\oplus$	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0