TAOCP 3.6 Exercise 3

We simulate a game of craps as described, using the standard linear congruential generator from Section 3.

taocpmathematicsalgorithmsvolume-2simple

Section 3.6: Summary

Exercise 3. [14] Write a program that simulates a roll of two dice, each of which takes on the values 1, 2, $\ldots$, 6 with equal probability. If the total is 7 or 11 on the first roll, the game is won; a total of 2, 3, or 12 on the first roll, call that losing immediately; otherwise, roll until the total is either the point (the first total rolled) or 7.

Verified: yes
Solve time: 1m31s

Solution

We simulate a game of craps as described, using the standard linear congruential generator from Section 3.6 to produce uniformly distributed random numbers between 1 and 6 for each die. Let $X$ denote the current state of the generator, initialized to some seed $X_0$, and updated by

$$ X \leftarrow (aX + c) \bmod m. $$

Define a function

$$ \text{RollDie}() = 1 + \lfloor 6 X / m \rfloor $$

to produce integers $1,2,\dots,6$ with approximately equal probability, using the most significant digits of $X$ (principle vi, Section 3.6). Then the sum of two dice is obtained by

$$ S \leftarrow \text{RollDie}() + \text{RollDie}(). $$

The program proceeds according to the rules:

  1. Compute the initial sum $S$. If $S = 7$ or $S = 11$, declare a win. If $S = 2$, $3$, or $12$, declare a loss. Otherwise, set the point $P \leftarrow S$ and continue.
  2. Repeat the following until the game is decided: generate $S \leftarrow \text{RollDie}() + \text{RollDie}()$. If $S = P$, declare a win. If $S = 7$, declare a loss. Otherwise, continue.

We may express this as an algorithm using Knuth's step notation.

Algorithm CRAPS:

E1. Initialize $X \leftarrow X_0$ (seed value).

E2. Compute the first roll: $S \leftarrow \text{RollDie}() + \text{RollDie}()$.

E3. If $S = 7$ or $S = 11$, set $\text{Outcome} \leftarrow \text{Win}$ and halt.

E4. If $S = 2$, $3$, or $12$, set $\text{Outcome} \leftarrow \text{Lose}$ and halt.

E5. Otherwise, set $P \leftarrow S$.

E6. Repeat:

  • E6a. Compute $S \leftarrow \text{RollDie}() + \text{RollDie}()$.
  • E6b. If $S = P$, set $\text{Outcome} \leftarrow \text{Win}$ and halt.
  • E6c. If $S = 7$, set $\text{Outcome} \leftarrow \text{Lose}$ and halt.
  • E6d. Otherwise, return to E6a.

This procedure guarantees that each die roll is uniform in ${1,2,3,4,5,6}$ and independent of previous rolls, since the linear congruential generator produces pseudo-random numbers with full period $m$ when $a$ and $c$ are chosen according to Section 3.6. By multiplying $X/m$ by 6 and truncating, we ensure that the outcome of $\text{RollDie}()$ depends on the most significant digits of $X$, preserving randomness.

The algorithm halts in finite time almost surely, because the Markov chain corresponding to the point-and-seven process has probability 1 of eventually reaching either $P$ or $7$.

The complete simulation can therefore be implemented in any language using a subroutine for $\text{RollDie}()$ based on the linear congruential generator, and a loop structure as in steps E1–E6.

This completes the solution.

∎