A group of people starts to play the board game "Snakes an ladders". A question arises: how many dice rolls end the game. Clearly the number of rolls can be viewed as random variable. So how to describe this random variable? It depends on number of players, results of dice rolls, location of ladders and snakes. To calculated the distributions of this random variable seams really complicated.

Game notation provides a way of describing such algorithmic randomised procedures without precise calculations.

For example, let a random variable $Y$ values be calculated $\ x \pmod{2}\ $ where $x$ is obtained by a dice roll. A game notation for this random variable is

$$\begin{array}{l} G_1\\ \left[\begin{array}{l} x\underset{u}\leftarrow \{1,2,3,4,5,6\}\\ y\leftarrow x \pmod{2}\\ \textbf{return}\ y \end{array}\right.\end{array}$$

where $G_1$ is the name of the game, $x\underset{u}\leftarrow \{1,2,3,4,5,6\}$ means that $x$ is chosen uniformly from the set $\{1,2,3,4,5,6\}$ (i.e. each value in the set is equally probable) and models the dice roll, $y$ is evaluated by calculating $x$ modulo $2$.

Note that we can define games where some components are left undefined and hence with one game we can also view a group of random variables.

As the game describes what must be done in order to get the outcomes, it also specifies the probabilities for each outcome.

For example, in the game $G_1$ the value of $x$ determines uniquely the outcome y, i.e. having the value $x$ we can calculated the corresponding $y$:

Since $x$ is chosen uniformly, all values of $x$ are equiprobable. Let us assign the probabilities to each column.

As we are interested in the output-values $y$, we can merge columns $x=1,\ x=3,\ x=5$ providing one and the same $y$ and also columns $x=2,\ x=4,\ x=6$. Corresponding probabilities must be summed as all the merged events are mutually exclusive. Thus, we have obtained the distribution of the random variable $Y$:

Let us view one more example:

$$\begin{array}{l} G_2\\ \left[\begin{array}{l} x\underset{u}\leftarrow \{1,2,3,4,5,6\}\\ \textbf{if}\ x>3\ \textbf{then}\\ \left[\begin{array}{l} y\underset{u}\leftarrow \{1,2\}\\ \textbf{if}\ y=1\ \textbf{then}\ z\gets (x-3)\ \textbf{else}\ z\gets x\\ \end{array}\right.\\ \textbf{else}\ z\gets x\\ \textbf{return}\ z \end{array}\right.\end{array}$$

Clearly, the outcome of this game depends on the values of $x$ and $y$, but there is something curious happening in the game. The value of $y$ is chosen after the comparison $x>3$ is done. However, $y$ is chosen uniformly form the set $\{1,2\}$ and thus $\Pr[y=1]=\frac{1}{2}$. This probability does not change if the value of $y$ is chosen before the if statement. This concept is also known as the time-invariance postulate.

Thus, the game has alternative equivalent description.

$$\begin{array}{l} G_2\\ \left[\begin{array}{l} x\underset{u}\leftarrow \{1,2,3,4,5,6\}\\ y\underset{u}\leftarrow \{1,2\}\\ \textbf{if}\ x>3\ \textbf{then}\\ \left[\begin{array}{l} \textbf{if}\ y=1\ \textbf{then}\ z\gets (x-3)\ \textbf{else}\ z\gets x\\ \end{array}\right.\\ \textbf{else}\ z\gets x\\ \textbf{return}\ z \end{array}\right.\end{array}$$

From this description, it is evident that the outcome $z$ of the game is determined by the values of $x$ and $y$. Knowing $x$ and $y$, we can calculated the corresponding $z$:

Since evaluation of $x$ and $y$ are independent,
$\text{Pr}[x=3\ \land\ y=1]=\frac{1}{6}\cdot\frac{1}{2}=\frac{1}{12}$.
Also
$\text{Pr}[x=4\ \land\ y=2]=\frac{1}{6}\cdot\frac{1}{2}=\frac{1}{12}$ and so on.
Again all column are equiprobable and mutually exclusive. Thus, we can compute the destribution table for $z$

Note that the creation of this table can be easily automated with the following Python script, which iterates over all possible configurations of random variables $x$, $y$ and counts how many time each configuration leads to a specific output. Finally, the script normalises the counts into probabilities.

c=[0,0,0,0,0,0]
for x in range(1,7):
    for y in range(1,3):
        if(x>3):
            if(y==1):
                z=x-3
                c[z-1]=c[z-1]+1
            else:
                z=x
                c[z-1]=c[z-1]+1
        else:
            z=x
            c[z-1]=c[z-1]+1
p=[float(i) for i in c]
print (p/sum(c))               

Games are useful tools for quantifying success of attacks.

For example, let us consider attack algorithm $A$ which tries to guess message $m$ from a ciphertext $c$. We can formally define the success of deciphering the message with the following game:

$$\begin{array}{l} G\\ \left[\begin{array}{l} k\underset{u}\leftarrow K\\ m\underset{u}\leftarrow M\\ c\leftarrow E(k,m)\\ m'\leftarrow A(c) \\ \textbf{return}\ m=m' \end{array}\right.\end{array}$$

The game models a situation where a key $k$ is chosen at random from a key space $K$, a message $m$ at random from $M$, then the ciphertext $c$ is computed by encrypting $m$ with $k$, and finally the adversary $A$ is given $c$ and outputs $m'$.The distribution described by the game $G$ shows how likely $A$ guesses correctly $m$.

In cryptography it is common to write this probability as follows

$$\text{Pr}[m=m': k\underset{u}\leftarrow K, m\underset{u}\leftarrow M, c\leftarrow E(k,m), m'\leftarrow A(c)]$$

or alternatively

$$\text{Pr}[k\underset{u}\leftarrow K, m\underset{u}\leftarrow M, c\leftarrow E(k,m), m'\leftarrow A(c) : m=m']$$

depending on the author.