CLRS Solutions | Exercise 5.2-3 | Probabilistic Analysis and Randomized Algorithms

Use indicator random variables to compute the expected value of the sum of \(n\) dice.

This problem asks us to find the expected sum when rolling \(n\) standard six-sided dice. We’ll solve it using indicator random variables to demonstrate the technique, even though this problem can be solved more directly.

Setting Up Indicator Random Variables

For each die \(i\) (where \(1 \leq i \leq n\)) and each face value \(j\) (where \(1 \leq j \leq 6\)), we define an indicator random variable:

\[X_{ij} = \begin{cases} 1 & \text{if die } i \text{ shows value } j \\ 0 & \text{otherwise} \end{cases}\]

The actual value shown on die \(i\) can be expressed as:

\[D_i = \sum_{j=1}^{6} j \cdot X_{ij}\]

This works because exactly one of the indicators \(X_{i1}, X_{i2}, \ldots, X_{i6}\) equals 1 (corresponding to the face that came up), and that indicator gets multiplied by its face value \(j\).

Expected Value of One Die

The expected value of die \(i\) is:

\[\begin{align*} E[D_i] &= E\left[\sum_{j=1}^{6} j \cdot X_{ij}\right] \\ &= \sum_{j=1}^{6} j \cdot E[X_{ij}] && \text{(Linearity of expectation)} \\ &= \sum_{j=1}^{6} j \cdot \Pr\{X_{ij} = 1\} && \text{(Lemma 5.1)} \\ &= \sum_{j=1}^{6} j \cdot \frac{1}{6} && \text{(Assuming fair die)} \\ &= \frac{1}{6}(1 + 2 + 3 + 4 + 5 + 6) \\ &= \frac{21}{6} \\ &= 3.5 \end{align*}\]

Expected Sum of \(n\) Dice

The total sum of all \(n\) dice is:

\[S = \sum_{i=1}^{n} D_i\]

By linearity of expectation:

\[\begin{align*} E[S] &= E\left[\sum_{i=1}^{n} D_i\right] \\ &= \sum_{i=1}^{n} E[D_i] \\ &= \sum_{i=1}^{n} 3.5 \\ &= 3.5n \end{align*}\]

So, the expected value of the sum of \(n\) dice is \(\boxed{3.5n}\) or equivalently \(\boxed{\frac{7n}{2}}\).

Interactive Simulation

Try the simulation below to see how the empirical average converges to the theoretical expected value of \(3.5n\):

import random def roll_dice(n): """Roll n six-sided dice and return the sum.""" return sum(random.randint(1, 6) for _ in range(n)) def simulate_dice_expected_value(n, num_trials=1000): """ Simulate rolling n dice many times and compute the average sum. Args: n: Number of dice to roll num_trials: Number of simulations to run Returns: The empirical average sum """ total = sum(roll_dice(n) for _ in range(num_trials)) return total / num_trials # Test with two example sizes print("Expected value of sum of n dice:") print("=" * 50) for num_dice in [2, 10]: empirical_average = simulate_dice_expected_value(num_dice) theoretical_expected = 3.5 * num_dice print(f"n = {num_dice:2d} dice") print(f" Theoretical: {theoretical_expected:.2f}") print(f" Empirical: {empirical_average:.2f}") print(f" Difference: {abs(empirical_average - theoretical_expected):.2f}") print() # Individual roll examples print("=" * 50) print("Five individual rolls of 10 dice:") for i in range(5): roll_result = roll_dice(10) print(f" Roll {i+1}: {roll_result}") print(f"\nTheoretical expected value: {3.5 * 10:.1f}")