Lesson 9

For two combinations \(s \neq t \in \{0,1\}^{3}\), we draw an edge \(s \to t\) in the graph if the probability of encountering \(s\) before \(t\) is greater than \(1/2\). This results in the following graph.

By examining the graph, one can observe many interesting properties.

• The combinations \(000\) and \(111\) cannot win against anyone. For example, the combination \(000\) is bad because as soon as \(1\) appears, all progress of \(000\) resets. The combination \(100\) is better in this regard: if \(10\) appears and then another \(1\) appears, the combination has still not appeared, but the last \(1\) can become the start of the combination, meaning progress is not fully reset.


• Any combination loses to some other combination! This is easy to see in the graph: every vertex has at least one incoming edge. So, no matter which combination you choose, I can choose another one that appears first more often than yours.


• From the previous point, it follows that there are cycles in the graph: starting from any vertex, one can move backward along incoming edges, and eventually, a previously visited vertex will be reached (not necessarily the starting one), forming a cycle. Here is one such cycle: \[110 \to 100 \to 001 \to 011 \to 110.\]