According to chess rules, the (undirected) graph generated from the Knight move on a keypad is the following:$$\begin{array}{ccccc}3 & - & 4 & - & 9 \\| & & | & & | \\8 & & 0 & & 2 \\| & & | & & | \\1 & - & 6 & - & 7\end{array}$$The question is:Consider the uniform distribution on all $n+1$-sequences $(s_i)_{i=0}^n$ starting with $s_0=0$.  What is the expected value and the standard deviation of $\sum_{i=1}^n s_i \bmod n$, under this distribution on sequences?My naive approach is simply traverse every single sequence of fixed given length and do the calculation. But as the $n$ grows, the number of visits grows exponentially. For example, for $n=1024$, the number of sequences exceeds $6.04\times 10^{367}$. Hence a DFS or any kind of traverse is not a feasible approach.So my second thought is using some analytic method. To get a few ideas, I first did some simulations on $\sum s_i$ (without modular reduction) with $10^5$ trials. The program generates the following distribution which doesn't match any obvious candidate so I couldn't advance further. So I am thinking if this is the correct way to tackle this problem. Any hint or help is appreciated.
Deep DFS traverse on graph
graph theory;graphs;probability theory;simulation
You can compute the exact distribution of $\sum_{i=1}^n s_i$ using dynamic programming: for each vertex $v$, index $m \in \{0,\ldots,n\}$ and index $S \in \{0,\ldots,9m\}$, calculate the number of walks of length $m$ starting at $0$, ending at $v$, and summing to $S$. The running time is roughly $O(n^3)$ (the extra $n$ factor is due to the length of the numbers involved).If you want an estimate, you should first find the stationary distribution of the Markov chain corresponding to a random walk on your graph. Given that, $\sum_{i=1}^n s_i$ has roughly Gaussian distribution with parameters that you can calculate from the stationary distribution; more specifically, roughly $N(n\mu, n\sigma^2)$ (this requires a version of the central limit theorem for Markov chains). This Gaussian approximation shows that the sum lies inside the interval of width $n$ centered around $n\mu$ with high probability, so taking modulo $n$ doesn't have much effect beyond shifting this interval to $\{0,\ldots,n-1\}$.