Let a human $h(t)$ random walk on $\mathbb{Z}^2$ by taking a unit-length step at every
time step $t$. A dog $d(t)$ on a leash of length $\lambda$ follows $h(t)$, also
taking a unit-length step at every
time step, but always retaining
a Manhattan distance $|x|+|y| \le \lambda$, where $(x,y)=h(t)-d(t)$.
So $d(t)$ remains inside the diamond-shaped $L_1$-ball centered on $h(t)$.
Just as in real life, it is natural to expect the dog to be closer to the
periphery of the $L_1$-ball than to its master, constantly tugging on a taut leash.
Indeed when I simulate this process, this situation obtains.
Here is an example of a 100,000-step walk, with a leash of length $\lambda=50$,
showing a histogram of the $L_1$-distance of $h(t)-d(t)$:
The growth is roughly linear in distance, but is perhaps falling off below linear.
My question is:
Is there some logic to suggest this distribution should be linear,
or instead, sublinear, with respect to distance?
Here is the human path (blue) and the dog's wandering (red)
which the above histogram summarizes:
Best Answer
The position of the dog relative to the human is a Markov chain, which is symmetric by inspection (there are three cases to consider: interior squares, "edge squares," and "corner squares"). This Markov chain splits up into two irreducible ergodic components corresponding to even and odd squares. Finally, any symmetric, irreducible, ergodic Markov chain has uniform stationary distribution. Since the number of squares at distance $d$ is $4d$ (except for $d = 0$), it follows that the distribution of the distances will be linear (again except for $d = 0$).
Here's how to show symmetry. If you're in an interior square, you move in each cardinal direction with probability $\frac{1}{16}$ and each diagonal direction with probability $\frac{2}{16}$. If you're in an edge square, you move diagonally off the edge with probability $\frac{2}{16}$, cardinally off the edge in each of two directions with probability $\frac{1}{16}$, and along the edge in each direction with probability $\frac{3}{16}$. If you're in a corner square, you move diagonally to an edge in each of two directions with probability $\frac{3}{16}$, and into the interior in one cardinal direction with probability $\frac{1}{16}$. We then observe that the probabilities of moving to each square from each other square are equal to the probabilities of moving the other way. (e.g., if we're on an edge next to a corner, we move into the corner with probability $\frac{3}{16}$ and then move out to that same edge square with the same probability.)