Solution: 2017 Fall Final - 22

Author: Michiel Smid

Question

Alexa and May 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{May rolls the die, let m be the result}$
$\quad \quad \mathbf{if}\ a > m\ \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 < m\ \mathbf{then}$
$\quad \quad \quad \text{print May goes first}$
$\quad \quad \quad \mathbf{return}\ k$
$\quad \quad \mathbf{endif}$
$\quad \quad \mathbf{if}\ a = m\ \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)

5/4

(b)

6/5

(c)

3/2

(d)

5/6

Solution

Let’s just think about this logically

$k$ increments when the dice rolls are the same(no die is greater than the other)

No die is greater than the other when the dice rolls are the same

The probability of returning k or having 2 different rolls is $ \frac{30}{36} $

On Allah, I swear there’s a rule that states that we expect to need 1/p attempts until the thing actually happens? Geometric Distribution?

$ p = \frac{30}{36} $

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

$ \mathbb{E}(X) = \frac{1}{ \frac{30}{36}} $

$ \mathbb{E}(X) = \frac{36}{30} $

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