Mean number of tosses of a fair dice to get a sum of outcomes being a multiple of $5$

Question

Let $S_n$ denote the sum of the outcomes of the $n$ tosses of a fair dice. Let $T=\inf\{n>0: S_n$ is a multiple of $5\}$. Compute $E(T)$ (by means of markov chains).

Attempt. Instead of working with $S_n$,we shal work with $S_n$ mod $5$. So $T$ becomes $T=\inf\{n\geq 1: S_n =0\}$. The chain $\{S_n\}_{n \geq 1}$ is markov, with state space $\mathbb{X}=\{0,1,2,3,4\}$ and transition probabilities $p(k,m)=1/6$ for $m \in \mathbb{X}\setminus \{k+1\}$ and $p(k,k+1)=2/6$. I wonder which of the following is the right path to the solution.

Option one. According to one step analysis, the function $g(x)=E(T~|~S_1=x),~x\in \mathbb{X}$ satisfies: $$g(x)=\sum_{y\in \mathbb{X}}p(x,y)g(y)$$ and we solve somehow for $g(0),\ldots,g(4).$ So $$E(T)=E(E(T|S_1))=\sum_{x\in \mathbb{X}}P(S_1=x)E(T|S_1=x)=\frac{1}{6}g(0)+\frac{2}{6}g(1)+\ldots+\frac{1}{6}g(4).$$

Option two. $T$ is indeed a time of first return to a state $x_0\in \mathbb{X}$ (that I don't know..). In that case we work with limit distributions $\pi=\pi P$ (it exists since the chain is aperiodic, irreducible and has finite state space), so $E(T)=1/\pi(x_0).$

Thanks a lot in advance for the help!

Answer 1

(Update: Your Option One is the way to go; but you forgot to add $1$ for each step. Apart from this my $e_k$ are essentially your $E(T|S_1=k)$, as well as the $\tau_k$ of Nikolaos Skout's answer; but my handling of $e_0$ gives the correct value $5$.)

Denote by $e_k$ $(0\leq k\leq4)$ the expected number of additional throws if your current remainder is $k$, but the game is not yet over. Then you obtain five equations, a sample being $$e_3=1+{1\over6}(e_1+e_2+e_3+2e_4)\ .$$ Solving this system I obtained $e_0=5$ (which is the answer to your problem), $e_1={1554\over311}$, and so on.

Answer 2

Working in $\mathbb Z/5\mathbb Z$ is a good start. The transition probabilities are then $$ P(i,j) = \begin{cases} \frac13,& j\equiv i+1\pmod 5\\ \frac16,& j\not\equiv i+1\pmod 5. \end{cases} $$ Let $\tau_i=\mathbb E[T\mid S_1=i]$ for $i\in \mathbb Z/5\mathbb Z$. Conditioning on $S_1$ yields the system of equations \begin{align} \tau_0 &= 1\\ \tau_1 &= 1 + \frac13\tau_2 + \frac16(\tau_1+\tau_3+\tau_4)\\ \tau_2 &= 1+ \frac13\tau_3 + \frac16(\tau_1+\tau_2+\tau_4)\\ \tau_3 &= 1+ \frac13\tau_4 + \frac16(\tau_1+\tau_2+\tau_3)\\ \tau_4 &= 1 + \frac16(\tau_1+\tau_2+\tau_3+\tau_4). \end{align} We may rewrite these in matrix form $A\vec \tau=\vec b$ where $$A= \left[ \begin{array}{cccc} \frac{5}{6} & -\frac{1}{3} & -\frac{1}{6} & -\frac{1}{6} \\ -\frac{1}{6} & \frac{5}{6} & -\frac{1}{3} & -\frac{1}{6} \\ -\frac{1}{6} & -\frac{1}{6} & \frac{5}{6} & -\frac{1}{3} \\ -\frac{1}{6} & -\frac{1}{6} & -\frac{1}{6} & \frac{5}{6} \\ \end{array} \right],\quad \vec\tau= \left[ \begin{array}{c} \tau _1 \\ \tau _2 \\ \tau _3 \\ \tau _4 \\ \end{array} \right],\quad \vec b=\left[ \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ \end{array} \right].$$ Solving $A\vec\tau=\vec b$ yields $$\vec\tau = \frac1{311}\begin{bmatrix}1554\\1548\\1512\\1296\end{bmatrix}. $$