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