Roll a fair 6 faces die. Stop if the sum of the previous rolls is a multiple of 3. What is the expected time to stop.

Question

Given there is a regular fair die, roll the die and stop if the sum of all previous rolls is a multiple of 3. What is the expected number of rolls?

Let $X$ denote the number of rolls until the event {the sum of all previous rolls is a multiple of 3} happens.

For $X = 1$, the rolls must be 3 or 6.

For $X = 2$, the rolls must be one of $\{(1,2), (2,1), (1,5), (5,1), (2,4), (4,2), (4,5), (5,4) \}$

For $X = 3$, the rolls must be one of $\{(1,1,1), (1,3,2),(1,3,5),(1,4,1), \ldots\}$

From the above enumeration, the pattern was not clear to me. I suppose there must be some "patterns" to simplify the computation.

Answer 1

If $n$ denotes an arbitrary integer and $D$ is the result of throwing a fair die then:$$\Pr(3\text{ divides }n+D)=\frac13$$

This because for every integer $n$ the set $\{n+1,n+2,n+3,n+4,n+5,n+6\}$ contains exactly $2$ numbers that are divisible by $3$.

Applying that for $\mu:=\mathbb EX$ we find:$$\mu=\frac13\cdot1+\frac23(1+\mu)=1+\frac23\mu$$ From this we conclude that:$$\mu=3$$

Answer 2

My idea is Markov Chain. Three states, representing $0,1,2$. Start at $0$, every turn uniformly go to one of the three states.We want to calculate $E_0(\sigma_0)$.

Denote $E_0(\sigma_i)$ as $t_i$, $i=0,1,2$.

We have $$t_0 = 1+(t_1+t_2)/3$$ $$t_1 = 1+(t_1+t_2)/3$$ $$t_2 = 1+(t_1+t_2)/3$$ We have $t_0=3$.

Update-----

I was a fool. Think that if you haven't finish rolling, every time there's $1/3$ chance to be terminated. So it's a geometry distribution with $p=1/3$

Answer 3

The probability that the game is a success in the $k^{th}$ roll is given by the coefficient of $x^k$ in

$$\frac12\sum_{k=1}^\infty \left(\frac{2x}3\right)^k \tag{1}$$

The expected number of throws is

$$\frac12\sum_{k=1}^\infty k\left(\frac{2x}3\right)^k \tag{2}$$

evalulated at $x=1$.

The differential of $(1)$ is

$$\frac12\frac23\sum_{k=1}^\infty k\left(\frac{2x}3\right)^{k-1}$$

which equals $(2)$ when evaluated at $x=1$.

$(1)$ can also be written as

$$\frac12\left(-1+\left(1-\frac{2x}{3}\right)^{-1}\right)$$

This differentiates to

$$\frac13\left(1-\frac{2x}{3}\right)^{-2}$$

which evaluates to $3$ at $x=1$.

Therefore $E(X)=3$.

Answer 4

Let $f(x)$ denote the expected number of runs till we get remainder $0$ with $x$ denoting the current remainder mod $3$.

Note that each remainder has $\frac{1}{3}$ chance of occurring.

$$f(1) = \frac{1}{3}(1 + f(2)) + \frac{1}{3}(f(1) + 1) + \frac{1}{3}(1)$$ $$f(2) = \frac{1}{3}(1 + f(1)) + \frac{1}{3}(f(2) + 1) + \frac{1}{3}(1)$$

Note that in case of $f(1)$, if we get remainder $2$ on the roll (numbers $2$ and $5$), we end the process, so we count only $1$ roll. Similarly, for $f(2)$.

We get $f(1) = f(2)$. Solving, we get $f(1) = f(2) = 3$.

Let us now iterate on the value of the first die roll. (Initial remainder is $0$)

$$ans = \frac{1}{3}(f(2) + 1) + \frac{1}{3}(f(1) + 1) + \frac{1}{3}(1)$$

$$ans = 3$$