Game notation

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.

1. Random variables described by games

In game notations a random variable is described by a small program (often called a game) that shows how the values of the random variables are chosen.

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.

A random variable's value $z$ is obtained by running an algorithm $\mathscr A$ on input $x\cdot y$, where $x$ is chosen uniformly from $1,\dots,10$ and $y$ is chosen uniformly from $1,\dots,x$. Write down the corresponding game.

Answer

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

A game specifies the corresponding random variable's distribution implicitly, i.e. indeed describes the random variable.

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$:

$x$ 1 2 3 4 5 6
$y$ 1 0 1 0 1 0

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

$x$ 1 2 3 4 5 6
$y$ 1 0 1 0 1 0
$\Pr[X=x]$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$

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$:

$y$ 0 1
$\Pr[Y=y]$ $\frac{1}{6}+\frac{1}{6}+\frac{1}{6}$ $\frac{1}{6}+\frac{1}{6}+\frac{1}{6}$

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.

The probability that uniformly chosen variable has a value $x$ does not depend on the time the value is fixed.

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$:

$x$ 1 2 3 4 5 6 1 2 3 4 5 6
$y$ 1 1 1 1 1 1 2 2 2 2 2 2
$z$ 1 2 3 1 2 3 1 2 3 4 5 6

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$

$z$ 1 2 3 4 5 6
$\text{Pr}[z]$$3\cdot\frac{1}{12}$$3\cdot\frac{1}{12}$$3\cdot\frac{1}{12}$$1\cdot\frac{1}{12}$$1\cdot\frac{1}{12}$ $1\cdot\frac{1}{12}$

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))               

Conclusion. In games where the only source of randomness is the uniform choice form finite sets, such as $\{0,1\}$ or $\{1,2,3\}$, we can always move uniform choices of random variables to the beginning of the game using the time invariance postulate. As a result, we get a game where the output is directly computable after we have fixed the all uniform choices. Hence, we can compute the output probabilities by cycling over all possible values of uniform choices, then execution the rest of the game (fixed calculation) and finally tabulating the output frequencies.

Let us have two games $S$ and $R$:

$$\begin{array}{l} S\\ \left[\begin{array}{l} \beta\underset{u}\leftarrow \mathbb{Z}_q\\ \gamma\underset{u}\leftarrow \mathbb{Z}_q\\ \alpha\leftarrow \frac{g^\gamma}{y^\beta} \pmod{17}\\ \textbf{return}\ (\alpha,\ \beta,\ \gamma) \end{array}\right.\end{array}$$

$$\begin{array}{l} R\\ \left[\begin{array}{l} r\underset{u}\leftarrow \mathbb{Z}_q\\ \alpha\leftarrow g^r \pmod{17}\\ \beta\underset{u}\leftarrow \mathbb{Z}_q\\ \gamma\leftarrow x\beta + r\\ \textbf{return}\ (\alpha,\ \beta,\ \gamma) \end{array}\right.\end{array}$$

where $q=8,\ g=2,\ y=2^3,\ x=3$. Write a Python program for finding the corresponding distributions. Do $R$ and $S$ describe different random variables?

Answer

A random variable's value $z$ is obtained by running an algorithm $\mathscr A$ on input $x\cdot y$, where $x$ is chosen uniformly from $1,2,3$ and $y$ is chosen uniformly from $1,\dots,x$. Write a Python program for finding the corresponding distributions if

  • the algorithm $\mathscr A$ is given by the following table
$p$ 123456789
$\mathscr A (p)$353000471
  • the algoritm $\mathscr A$ means tossing a coin ($\omega\gets\{0,1\}$) and using the following table
$p$ 112233445566778899
$\omega$ 010101010101010101
$\mathscr A (p)$025325010007250110

2. How games are used in cryptography?

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.

Write in game notation the probability that two independent dice rolls are equal?

Answer

What is $\text{Pr}[x=z:x\underset{u}\leftarrow\{1,\dots,6\}, y\underset{u}\leftarrow\{1,\dots,3\}, z\leftarrow xy]$?

probability/07_game_notation.txt ยท Last modified: 2014/01/29 17:30 by marje