2
$\begingroup$

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.

Trial

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, so the distribution can be roughly done the same lines as counting the number of paths using dynamic programming. For the simulation, I think the pattern can be modeled by truncated normal distribution, but the actual graph above is rather "non-measurable" alike, as seen by multiple "layers". What could be the cause of that? $\endgroup$
    – Kaa1el
    Jul 22, 2016 at 21:31
  • $\begingroup$ Perhaps $1024$ is too small a number. Also, perhaps there are local phenomena that explain the apparent "noise" or "jitter". They might be discussed in a Markov chain local limit theorem, if one exists. $\endgroup$
    – Yuval Filmus
    Jul 22, 2016 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.