Terminating Sequence expected length

Question

I was preparing for a quant interview and I came across a puzzle on QuantGuide(named Sequence Terminator):
A fair 6−sided die is rolled repetitively, forming a sequence of values, under the following rules: If any even value is rolled, add it to the current sequence. If a 3 or 5 is rolled, discard the entire sequence, and don't add the 3 or 5 to the start of the new sequence. If a 1 is rolled, add the 1 to the current sequence and end the game. Find the expected length of the sequence at the end of the game.
My approach:
Let us define 2 variables $\alpha_n$ and $\beta_n$ as the expected length till the $n^{th}$ iteration given that in the last roll, we continue with the game or the game terminates respectively. But I'm unable to proceed further.
It would be great if you could please help me out.

Answer 1

$$E=\sum_{x=1}^\infty x\times P_{n=x}$$

In order to calculate $P_{n=x}$ we note that the probability $r$ of a restart is the probability of rolling a $3$ or a $5$ before rolling a $1$. This is clearly $\frac{2}{3}$, so for $P_{n=1}$ we have

$$P_{n=1}=\frac{1}{6}+\frac{1}{2}\times\frac{2}{3}\times P_{n=1}+\frac{1}{3}\times P_{n=1}$$

The second addend having a restart after an even roll, and the third an immediate restart. This simplifies to

$$\begin{align}P_{n=1}&=\frac{1}{6}+\frac{2}{3}\times P_{n=1}\\ \frac{1}{3}\times P_{n=1}&=\frac{1}{6}\\ P_{n=1}&=\frac{1}{2}\end{align}$$

For $P_{n=2}$ we have $$\begin{align}P_{n=2}&=\frac{1}{2}\times\left(\frac{1}{6}+\frac{1}{2}\times\frac{2}{3}\times P_{n=2}+\frac{1}{3}\times P_{n=2}\right)+\frac{1}{3}\times P_{n=2}\\ P_{n=2}&=\frac{1}{2}\times\frac{1}{6}+\frac{2}{3}\times P_{n=2}\\ \frac{1}{3}\times P_{n=2}&=\frac{1}{2}\times\frac{1}{6}\\ P_{n=2}&=\left(\frac{1}{2}\right)^2\end{align}$$

Similarly, we find $P_{n=3}=\left(\frac{1}{2}\right)^3$ and this continues with $P_{n=x}=\left(\frac{1}{2}\right)^x$, though I have not found a clear induction argument for proof. Putting this into the sum gives us the final result:

$$E=\sum_{x=1}^\infty\frac{x}{2^x}=2$$

Given the source of the question, I expect that there is some clever way to reach the final result with proof.

Answer 2

Notation: We define a stopping number to be either a 3 or a 5.

Game 1: Force Never Rolling a Stopping Number

Game 1: The rules are the same. Except this time, if you never roll a 3 or a 5, you get 0 points and the game ends. What is the expected value of your length?

The probability of rolling our first 1 on the $n$th roll is $\left( \frac{1}{2} \right)^{n-1} \cdot \frac{1}{6}.$ Then, $$\mathbb{E}[\text{length}] = \frac{1}{6}\sum_{n = 1}^{\infty} \left( \frac{1}{2} \right)^{n-1} \cdot n = \boxed{\frac{2}{3}}.$$

Game 2: Force Rolling a Stopping Number

Game 2: The rules are the same except this time, if you never rolled a stopping number, you get 0 length.

Suppose that we made $n$ rolls and that our last stopping number was at the $k$th roll. The probability of this happening is $\left( \frac{5}{6} \right)^{k - 1} \cdot \frac{2}{6} \cdot \left(\frac{3}{6} \right)^{n - k - 1} \cdot \frac{1}{6}.$ Thus, \begin{align*} \mathbb{E}[\text{length}] &= \frac{1}{18}\sum_{n = 1}^{\infty} \sum_{k = 1}^{n-1} \left( \frac{5}{6} \right)^{k - 1} \cdot \frac{2}{6} \cdot \left(\frac{3}{6} \right)^{n - k - 1} \cdot \frac{1}{6} \cdot (n - k) \\ &= \boxed{\frac{4}{3}}. \end{align*}

Putting it all together

Our "score" is the sum of the scores in game 1 and game 2. By linearity of expectation, this is $\frac{4}{3} + \frac{2}{3} = \boxed{2}.$