Deep DFS traverse on graph

Question

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.

Answer 1

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