Expected value of the recursive algorithm

Question

Sara and Macey want to play the game of Truth or Dare. They use the following recursive algorithm to decide who goes first:

$\textbf{Algorithm} \hspace{2mm} GoesFirst(k):$
$// \hspace{2mm}k ≥ 1$, the die is fair, and all rolls are independent
Shelly rolls the die, let $s$ be the result;
Macey rolls the die, let $m$ be the result;
$ \textbf{if } s > m \\ \textbf{then} \text{ Sara goes first} \\ \quad \quad return \hspace{2mm} k \\ \textbf{end if } \\ \textbf{if } s < n \\ \textbf{then} \text{ Macey goes first} \\ \quad \quad return \hspace{2mm} k \\ \textbf{end if } \\ \textbf{if } s = m \\ \textbf{then} \text{ GoesFirst(k + 1)} \\ \textbf{end if } \\ $

The ladies run algorithm $GoesFirst(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) $3/2$
(b) $5/4$
(c) $5/6$
(d) $6/5 \hspace{2mm} \text{ This is the answer} $

Why is this the answer? I know the formula for the expected value is $\mathbb{E}(X) = \sum_{}^{} k \cdot Pr(X = k)$.

From class I learned that the Expected Value of a Geometric Distribution is $1/p$ where $p$ is the probability of success.

Is $5/6$ is the probability of success? (ie. $5/6$ times we will get an answer as to who will go first).

If so, then we repeat this algorithm until we reach a success, which I assume follows the Geometric Distribution:

$\frac{1}{5/6} = 6/5$ which is the answer.

I tried doing the sum but realized it was pointless.

$\mathbb{E}(X) = 1 \cdot 5/6 + 2 \cdot 1/6$ ...

I think my first solution is correct. If anyone can formalize my thinking that would be great.

Thanks.

Answer 1

The algorithm returns the number of the first roll of the die on which they get a different number. As you say, the probability of success (the probability that they roll different numbers) is $5/6.$ The expected number of trials until the first success is $1/p$ as you know. The answer is $6/5$.

It isn't "pointless" to compute the sum. That's how the expected value of $1/p$ is arrived at in the first place. However the second term should be $$2 \cdot 1/6\cdot 5/6$$ It's $2$ times the probability that they get the same number on the first roll, times the probability that they get different numbers on the second.

Answer 2

There are $36$ possible outcomes of $(s,m)$ drawings, of which $6$ make a tie, with probability $\dfrac16$.

Then we have the recurrence

$$p_{k+1}=\frac{p_k}6$$

because $k$ is incremented only in case of a tie, and we indeed have a geometric law with parameter $1-p=\dfrac56$. The expectation is known to be the inverse of the parameter.

---

By direction computation, the expectation is

$$E=\frac{1p+2p^2+3p^3+\cdots}{p+p^2+p^3+\cdots}=1+\frac{1p^2+2p^3+\cdots}{p+p^2+p^3+\cdots}=1+p\frac{1p+2p^2+\cdots}{p+p^2+p^3+\cdots}=1+pE$$ and we draw

$$E=\frac65.$$

Answer 3

Your output X follows a Negative binomial distribution. X is the number of trial before the first success.

Here the success S is when the 2 dices roll different number. Let's say we have rolled the first dice what is the probability that the second dice gives a different number? The probability of success is $p=P(B=1)=\frac 56$

Then we repeat this experiment until success and X=k means $B_1=0$ and $B_2=0$ and $\dots$ $B_k=1$.

The expectation of the negative binomial is $E(X)=\frac 1p$. A good explanation is available in Wikipedia. A formal proof is the following:

$E(X)=E(X|B_1=0)P(B_1=0) + E(X|B_1=1)P(B_1=1) = (E(X)+1)(1-p) + p$ $E(X)=\frac 1p $