Randomly walking a leashed dog

Question

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:
     

Answer 1

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.)

Answer 2

Consider the random variable $r(t)=d(t)-h(t)$. Now $r(t)$ is a random walk inside the "sphere" of "radius" $\lambda$. The possible steps of $r(t)$ are no longer just the four neighboring cells, but this isn't a crucial difference. Essentially $r(t)$ is just doing a random walk inside the square (constrained not to step outside of it). It should be elementary to show that after running for many iterations, $r(t)$ becomes evenly distributed in the square (well, except for some silly parity issues: $r(t)$ only visits squares whose coordinate sum is even, and at time $t$ the coordinate sum is $\equiv 2t\mod 4$). Now the linear growth of the distance distribution is easy to explain, since the number of points of distance $x$ from zero is a linear function of $x$.