Solution: 2018 Winter Final - 22

Author: Michiel Smid

Question

Alexa and Shelly want to play the game of Monopoly. They use the following recursive algorithm to decide who goes first:

$\WhoGoesFirst(k):$
$\quad \mathbf{if}\ k \geq 1\ \mathbf{then}$
$\quad \quad \text{Alexa rolls the die, let a be the result}$
$\quad \quad \text{Shelly rolls the die, let s be the result}$
$\quad \quad \mathbf{if}\ a > s\ \mathbf{then}$
$\quad \quad \quad \text{print Alexa goes first}$
$\quad \quad \quad \mathbf{return}\ k$
$\quad \quad \mathbf{endif}$
$\quad \quad \mathbf{if}\ a < s\ \mathbf{then}$
$\quad \quad \quad \text{print Shelly goes first}$
$\quad \quad \quad \mathbf{return}\ k$
$\quad \quad \mathbf{endif}$
$\quad \quad \mathbf{if}\ a = s\ \mathbf{then}$
$\quad \quad \quad \WhoGoesFirst(k + 1)$
$\quad \quad \mathbf{endif}$

The ladies run algorithm $\WhoGoesFirst(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

(a)

6/5

(b)

3/2

(c)

5/4

(d)

5/6

Solution

In the algorithm, the value of $k$ keeps increasing if the two dice rolls are different. Theoreticaly, this algorithm can go on forever, until the two dice rolls are the same.

This is an example of the Geometric Distribution.

Let $p$ represent the probability of not ending the recursive algorithm. Using the formula for the expected value for Geometric Distribution we get:

$E(X) = \frac{1}{p} = \frac{1}{ \frac{5}{6}} = \frac{6}{5}$