# Exact distribution of random walk after 10 or 100 steps

(Variant of Stats Exercise to Protect the Innocent).

Starting for $x = 0$ I can do one of two operations $\pm 1$ or $\pm 4$. Let $T$ be one iteration of this step.

• What is the mean and standard deviation after 10 steps mod 10 ? i.e. the distribution of $T^{10}(0) \mod 10$

• What is the mean and standard deviation after 100 steps mod 100 ? i.e. t he distribution of $T^{100}(0) \mod 100$

• What is the mean and standard deviation after 1000 steps mod 1000 ? i.e. t he distribution of $T^{1000}(0) \mod 1000$

The exam had asked for 10 decimal places accuracy. Also the problem has been completely altered but original in spirit. Notice these do not look for limits.

Can this be classified under a general theme?

• That seems like a question better suited for stats.stackexchange.com? I don't see a numerical analysis component -- the ten digits are probably just for the sake of having a uniform answer format. – Christian Clason Jul 22 '16 at 11:26
• If I had to guess, the general theme is think before you calculate -- presumably, there is a stochastical argument to obtain these values directly rather than performing a tedious Monte Carlo approximation of the required accuracy. – Christian Clason Jul 22 '16 at 12:02
• @ChristianClason Monte Carlo would be quite tedious, so there must be a numerical way to get a faster answer – john mangual Jul 22 '16 at 16:12
• Is the choice between $\pm\{1,4\}$ made uniformly at random, or is it something else? – Kirill Jul 22 '16 at 19:03
• @Kirill yes this is known as a Cayley graph and may have other terms in the statistics literature. the vertices are $V=\mathbb{Z}/10\mathbb{Z}$ and the edges are $E = \{ (x, x \pm 1 ),(x, x \pm 4)\}$. and I'm asking for the exact distribution after 10 steps. – john mangual Jul 22 '16 at 19:37

## 1 Answer

One way to do this is to note that since step sizes are independent of step directions, conditional on knowing the sequence of step sizes, the distribution of $T^n(0)$ is a sum of two random walks of $k$ and $n-k$ steps with step sizes 1 and 4, respectively (both of which are independent binomial random variables), where $k$ is the number of steps of size 1, which itself has a binomial distribution, independent of the random walks. Since the limits on the problem are pretty small, the probability of observing a given value of $T^n(0)$ can be calculated directly in time $O(n^3)$ from the binomial pmf's, and then expectation and standard deviation modulo $n$ calculated from that.

I think this can be classified as a question about iterated expectation.

For reference, for $n=10$ this gives me mean $4.3798828125$ and s.d. $2.871979661$.