# Expected distance squared of random walk on an infinite hexagonal grid

I had a probability test and that was one of the questions:

We have an infinite grid of hexagons like this:

Each edge has a length of 1 and all the degrees are 120°.

There's a particle in one of the vertices and each second it randomly moves to one of it's neighbours.

After n seconds what is the expected distance squared of the particle from it's starting position?

I spent a lot of time on that but I really have no idea how to even approached this question.

• Note: Those are hexagons, not octagons. – Mees de Vries Feb 7 '19 at 12:34
• @Mees de Vries sorry I meant hexagons – Tomer Wolberg Feb 7 '19 at 12:36

Let $$(Z_n)$$ be i.i.d. $$\mathbb{C}$$-valued random variables having the law $$\mathbb{P}(Z_n = -\omega^k) = \frac{1}{3}$$ for any $$k \in \{ 0, 1, 2 \}$$, where $$\omega = e^{2\pi i/3}$$. Using the $$90^{\circ}$$-rotation of the lattice in OP's figure, the $$n$$-th step $$X_n$$ of the random walk started at $$0$$ can be realized as
$$X_n = \sum_{k=1}^{n} Z_1 \cdots Z_k.$$
\begin{align*} \mathbb{E}[|X_n|^2] &= \mathbb{E}[X_n \overline{X_n}] \\ &= \sum_{j,k=1}^{n} \mathbb{E}[(Z_1\cdots Z_j)\overline{(Z_1 \cdots Z_k)}] \\ &= n + \sum_{1 \leq k < j \leq n} \underbrace{\mathbb{E}[Z_{k+1}\cdots Z_j]}_{=0} + \sum_{1 \leq j < k \leq n} \underbrace{\mathbb{E}[\overline{Z_{j+1}\cdots Z_k}]}_{=0} \\ & = n. \end{align*}
The following is a simulation using 2500 samples of $$X_{100}$$, numerically verifying the above computation.