On a white square grid there are two black cells. Each step consists of each of the cells 'moving' in one of the four directions with equal probability $p_0=1/4$ (a cell can't stay in the same place).
Let's say we start with a dimer (two cells sharing the same edge). What is the probability that after $n$ steps we again get a dimer?
The general condition for the dimer is:
$$d=|x_1-x_2|+|y_1-y_2|=1$$
With $(x_k,y_k)$ as the integer coordinates of the cells on the grid.
After each step the coordinates become:
$$(x_k,y_k) \to (x_k \pm 1 ,y_k \pm 1)$$
$\pm 1$ means either $+1$ or $-1$ with equal probability, independent for $x$ and $y$. Which also means that the distance always stays odd:
$$\Delta d=\{0,2\}$$
- After $1$ step there are $4^2=16$ possible states. They make $3$ distinct shapes, up to rotation (see the picture):
Thus, the probability of the dimer staying together after $1$ step is:
$$P_1=\frac{9}{16}$$
- After $2$ steps there are $4^4=256$ possible states. However, it's still possible to track all the states that lead back to a dimer:
$$P_2=\frac{9^2}{16^2}+\frac{1^2}{16^2}+\frac{6}{16} \cdot \frac{3}{16}=\frac{25}{64}$$
It's significantly harder to track all the possibilities for $n=3$, but I'll try (I track all the transformation that ultimately lead to a dimer):
$$P_3=\frac{25}{64} \cdot \frac{9}{16}+\frac{9}{16} \left( \frac{1^2}{16^2}+\frac{6}{16} \cdot \frac{3}{16}\right)+\frac{6}{16} \left( \frac{7}{16} \cdot \frac{3}{16}+\frac{2}{16} \cdot \frac{1}{16}\right)+\frac{1}{16} \left( \frac{4}{16} \cdot \frac{3}{16}+\frac{4}{16} \cdot \frac{1}{16}\right)=\frac{1225}{4096}^*$$
$^*$ I edited the value, since I put an incorrect calculation of the LHS before. Now it's correct.
Is there a general method to obtain the probability of a dimer after $n$ steps? Or even an explicit expression? Or at least, some approximations for large $n$?
Dan Uznanski has already sketched the solution in a comment; I'll work it out in more detail.
Regard one cell as stationary and let the other cell make two steps at a time. Turn the grid by $\frac\pi4$. Then the walk can be decomposed into two independent simple symmetric one-dimensional random walks. We want the probability that these walks end up at $(0,0)$, $(0,2)$, $(2,0)$ or $(2,2)$ after $2n$ steps, starting from $(0,0)$.
The probability that a simple symmetric one-dimensional random walk goes from $0$ to $2k$ in $2n$ steps is $2^{-2n}\binom{2n}{n-k}$. Thus the probability you want is
$$ \left(2^{-2n}\left(\binom{2n}n+\binom{2n}{n-1}\right)\right)^2=2^{-4n}\binom{2n+1}n^2\;. $$
The first three values are $\frac9{16}$, $\frac{25}{64}$, $\frac{1225}{4096}$. Your calculation for $n=3$ is correctly set up; you just got the wrong end result; the sum you wrote down is in fact $\frac{1225}{4096}$.