# Intrinativeness: From Games to Random Walks +
## 2 Transitivity  
Let us start defining the concept of transitivity of a binary relation, defined on a set \(\mathcal{I}\). The relation \(\sim\), is transitive if  
\[A\sim B,B\sim C\Rightarrow A\sim C\qquad\forall A,B,C\in\mathcal{I},\]  
and a relation is intransitive if this condition is violated for at least a triplet \(A,B,C\). A relation is completely intransitive if  
\[A\sim B,B\sim C\Rightarrow A\
ot\sim C\qquad\forall A,B,C\in\mathcal{I},\]  
where \"\(\
ot\sim\)\" denotes the fact that \(A\) is not in relation with \(C\). Intransitive relations are not uncommon, an instance of \"being father of\" is completely intransitive, while \"being behind\" is simply intransitive. It is possible to reformulate a game as random walk on a directed network where the nodes represent the possible choices of the players and the links describe the competitive relations. In order to be concrete, let us recall the Penney Game [1; 3], which is an extension of the heads-tails game. In the Penney Game, the two players are asked to bet not on a single coin flip, but on a contiguous succession of heads and tails, whose length \(\ell\) is fixed. This gives to each player a choice among \(2^{\ell}\) different sequences of heads and tails. The game is won by the player whose sequence will appear first. The network and the relative adjacency matrix for the case \(\ell=3\) are shown in Figure 1.  
Figure 1: Analysis of the Penney Game with \(\ell=3\), fair coins and fully absorbing traps. (**a**) Transition graph, where every node is a possibly winning sequence, the links go from one sequence to the sequences which can be obtained with a coin toss. Each link weights \(1/2\). (**b**) Weighted adjacency matrix (Markov matrix) \(\mathbf{M}\) of the system, where the sequences (indexes) are read as base-two numbers. (**c**) Victory matrix and (**d**) victory graph, where arrows mark which sequence wins with the largest probability over the given one. By assigning a symbol to each possible sequence (for instance 1 for heads and 0 for tails, and then reading the \(\ell\) sequence as a base-two number) we can map the game to a random walk on a network. Given a sequence, the next one is obtained by discarding the first digit and extracting a new one, each symbol (sequence) is connected to two other symbols (which can be the same, like in the 000 or 111 sequences). The use of a loaded coin corresponds to biased walks. The chosen sequences are absorbing traps, since, once they appear, one of the players wins. In the Penney Game, some sequences are surely disadvantageous, but it is not evident which is the winning one. The analysis is quite simple for \(\ell=2\) and fair coins, see Figure 2. The weighted adjacency matrix (forbidding to bet on the sequence chosen by the first player) is  
\[M_{2}(p)= \begin{pmatrix}-&1-p&(1-p)^{2}&\frac{(1+p)(1-p)^{2}}{1-p+p^{2}}\\ p&-&1-p&1-p^{2}\\ p(2-p)&p&-&1-p\\ \frac{(2-p)p^{2}}{1-p+p^{2}}&p^{2}&p&-\end{pmatrix} .\]  
The first player chooses a column (betting on the sequence corresponding to the column index in base two), and the second one chooses the row entry, corresponding to his/her probability of winning. For fair coins, \(p=1/2\), the matrix is  
\[M_{2}\left(\frac{1}{2}\right)=\frac{1}{4} \begin{pmatrix}-&2&1&2\\ 2&-&2&3\\ 3&2&-&2\\ 2&1&2&-\end{pmatrix} ,\]  
and the first player avoids columns where there is a high probability of victory for the second player, so he/she will choose sequences 01 or 10 and the second player the opposite sequence. The game is fair. For extremely loaded coins, for instance \(p=0\), we have  
\[M_{2}(0)=\frac{1}{2} \begin{pmatrix}-&2&2&2\\ 0&-&2&2\\ 0&0&-&2\\ 0&0&0&-\end{pmatrix} ,\]  
so the first player has simply to choose the sequence 00 (which will always be the only sequence appearing) to win. This holds also for finite (small) values of \(p\). Figure 2: Complete analysis of the Penney Game for \(\ell=2\) and loaded coins. However, taking for example \(p=0.51\), the matrix becomes  
\[M_{2}(0.51)=