Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$:
      Histogram
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:
      WalkDogPath100k

share|improve this question
    
Note that the freedom to increase or maintain distance is curtailed only by when the rope is taut. The freedom to decrease or maintain distance is determined by relative position. A distribution of relative positions inside the ball around the human is likely to be more informative. –  The Masked Avenger Mar 1 at 3:10
    
In particular, I think you are taking too short a walk. I intuit (perhaps wrongly) that for a leash of length l, walks of length larger than l^2 log l will have the ball distribution start to bunch up at the longer lengths. Try simulations with both really long walks as well as really short leashes. –  The Masked Avenger Mar 1 at 3:21
1  
This problem seems very much related to the previous question on the inchworm. Thus I think the process described here also should fit in the formalism of a "random walk with internal degrees of freedom"; see mathoverflow.net/a/132218 –  j.c. Mar 1 at 7:58
1  
Incidentally, it might also be interesting to see what happens if the dog can move faster than the human (a realistic assumption, in my experience). –  Nate Eldredge Mar 1 at 16:09
1  
@NateEldredge: The human moves $\pm 1$ in any direction. Then the dog moves $\pm 1$ in any direction that satisfies the leash length constraint. –  Joseph O'Rourke Mar 1 at 16:14

2 Answers 2

up vote 14 down vote accepted

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

share|improve this answer
    
Beautifully clear analysis---Thanks! –  Joseph O'Rourke Mar 1 at 13:15

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

share|improve this answer
    
However, the random walk is not entirely uniform. Not only are there times when steps of length 0 allowed, aren't the steps near the boundary weighted differently? –  The Masked Avenger Mar 1 at 4:05
    
A constrained random walk won't necessarily be uniformly distributed. Consider a (1D) random walk constrained to {-1, 0, 1}: certainly this will spend half its time in the middle! You need ergodicity (which is trivial in our case, since the dog can always stay put relative to the human) and symmetry, which really needs to be checked manually as in my answer. –  Evan Jenkins Mar 1 at 5:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.