# 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.

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.

• No matter what the sum of all previous numbers is, there is a fixed chance to roll a number which brings that sum up to a multiple of 3. Commented Mar 12, 2022 at 8:11

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$$

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$$

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$$.

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$$