Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \inf \{k > \tau_n : \ S_k \in \Sigma\}$. Then $(X_n) = (S_{\tau_n})$ is a Markov chain on $\Sigma$. Let $P$ be its transition matrix.
The matrix $P$ can be computed using potential theory, in a way akin to the XKCD "nerd sniping" problem (see here).
I decided to do this for a simple example, $\Sigma = \{A, B, C\}$ with $A = (0,0)$, $B = (-1,0)$ and $C=(1,1)$. The computation is somewhat lenghty, but hopefully I made no mistake:
$$P = \frac{1}{-\pi^2+8\pi-4} \left( \begin{array}{ccc} -\frac{1}{2}\pi^2+4\pi-4 & -\frac{1}{2}\pi^2+3\pi & \pi \\ -\frac{1}{2}\pi^2+3\pi & -\pi^2+6\pi-4 & \frac{1}{2}\pi^2-\pi \\ \pi & \frac{1}{2}\pi^2-\pi & -\frac{3}{2}\pi^2+8\pi-4 \\ \end{array} \right)$$
So, a few remarks:
The result is a symmetric matrix, which comes from the fact that the transition kernel of the simple random walk is itself symmetric.
It can be written as $F(\pi)$ where $F$ is a rational function with rational coefficients. This is not surprising, because, using Fourier transform, it can be evaluated from trigonometric integrals such as
$$\frac{1}{\pi^2} \int_{[-\pi, \pi^2]} \frac{\sin^2 (\xi_1)}{\sin^2 (\xi_1)+\sin^2 (\xi_2)} \ \text{d} \xi_1 \text{d} \xi_2,$$
and using algebraic operations on matrices with coefficients in $\mathbb{Q} (\pi)$.
- The rational function $F$ above satisfies $F(0) = I$.
And the last fact I don't understand. It seems too perfect to be random chance, but I don't see where it comes from. So, why should we have $F(0)=I$ ?
