Take the 2-minute tour ×

Imagine that an $\epsilon$-radius hole is punched in the plane centered on every integer-coordinate point. Now a point "ball" is dropped on the plane at a random spot $p$. If $p$ has not already dropped through a hole, the plane is tilted in a random direction, and the ball rolls along the gradient vector $u$.

What is the expected length $L(\epsilon)$ of its roll before it falls through a hole?

If $p$ is in a hole upon generation, then $L=0$. Otherwise $L$ is determined by the first encounter with a hole, i.e., the ray from $p$ along direction $u$ passes within distance $\epsilon$ of some hole center $c$. For example, here $\epsilon=\frac{1}{4}$ and $c=(2,1)$, with $L \approx 1.6$:
        Tilted Plane Disks
I am particularly interested in the growth rate of $L(\epsilon)$.

Intuition from another viewpoint suggests $\sim \frac{1}{\epsilon}$. Shrink the holes to points, and grow the ball to an $\epsilon$-radius disk. This sweeps out a rectangle of area $2 \epsilon L$ for a roll of length $L$. Very crudely, when this area reaches $1$ (or $1-\pi \epsilon^2$), I would expect it to include a lattice point. So perhaps $L \approx \frac{1}{2\epsilon}$. But this reasoning is surely not sound.

Perhaps there is an approach that employs techniques from rational approximations? All ideas welcomed—Thanks!

Addendum. Here are two histograms for $L(\epsilon)$ with $\epsilon=\frac{1}{4}$. The first is of 200 random points, the second of 300 random points.
They begin to illustrate Doug Zare's point that very long paths occur not infrequently. In the 300-point example, one path has $L \approx 63$, while more than half the paths have $L \le 1$. The probability that $L \le 10$ is $>98$%, even though the expected length is $\infty$!

share|improve this question

5 Answers 5

up vote 5 down vote accepted

The expected length is infinite when $\epsilon \lt 1/2$.

The reason is that when the slope $\alpha$ is near a rational $p/q$ such that there are infinite trajectories of slope $p/q$ which don't get closer than $\epsilon$ to any lattice point, the length of the trajectory is often long. Specifically, suppose $\alpha$ is very close to $0$. Then the expected length of the trajectory is not roughly $1/\epsilon$, it is proportional to $(1-2\epsilon)/\alpha$.

By rotating the lattice, we can assume that the direction of the ray is between $-\pi/4$ and $\pi/4$, and a uniform distribution on these directions has a bounded distortion $c_1$ from the uniform distribution on slopes between $-1$ and $1$. The expected value of a nonnegative quantity over slopes is a factor of at most $c_1$ off of the expected value over directions.

Suppose the slope is between $1/n$ and $2/n.$ For simplicity, assume the initial point has $x$-coordinate $0$. This adds less than $2$ to the length. For simplicity, in the following I'll assume $\epsilon \lt 1/2\sqrt2$ but that isn't necessary. In order to get within $\epsilon$ of a lattice point, the height of the ray has to be within $c \epsilon$ (with $c_2 \lt \sqrt 2, c_2 \lt 1+2/n$) of an integer when the $x$-coordinate is an integer. For an initial $y$-coordinate $y_0$ between $c \epsilon$ and $1-c \epsilon$, a lower bound for when this can occur is $(1-c_2\epsilon)/(2/n)$. So, as we average over the initial $y$-coordinates, the average length is at least $\frac{(1-2c_2 \epsilon)(1/2 - c_2 \epsilon)}{(2/n)} -2 \gt c_3 n$ - 2.

Since the intervals $(1/2^m, 2/2^m)$ are disjoint, the expected length is at least $c_1 \sum_{n=2^m} (1/n) (c_3 n - 2) = -2 + c_1 \sum_m c_3 = \infty.$

share|improve this answer
Wow, this is a remarkable conclusion! Quite counterintuitive, and therefore all the more interesting. –  Joseph O'Rourke Aug 27 '12 at 13:32
It's a nice argument, though I am guessing that one can compute the distribution of the lengths... –  Igor Rivin Aug 27 '12 at 17:56
@Joseph O'Rourke: This was my intuition. In your argument about how the expected length should be larger than $1/\epsilon$ for small $\epsilon$, you use the union bound, which is sharp when the possibilities are disjoint. However, if a line segment intersects two holes, it often intersects many holes. The flip side was that a line segment which misses might keep missing for a long time. I considered a slope of $1/100$ and $\epsilon \gg 1/100$, and noted that each extension by $1$ beyond $1$ only caused an intersection with $1/100$ of the line segments, not roughly $\epsilon$. –  Douglas Zare Aug 27 '12 at 19:59

This is just a small streamlining of Douglas Zare's proof that the expected length $L(\epsilon)$ is infinite when $\epsilon < 1/2$.

The expected length will only decrease if you enlarge the holes to become, say horizontal "gutters" that swallow everything whose $y$ coordinate is within $\epsilon$ of an integer. Thus

$$L(\epsilon) > {1\over \pi/2}\int_\epsilon^{1-\epsilon}\int_0^{\pi/2}L(\epsilon,y,\theta)d\theta dy,$$

where $L(\epsilon,y,\theta)$ is the length of the path the point ball takes if it starts with $y$-coordinate $y$ and heads off at an angle $\theta$ with respect to the $x$ axis. (I'm using obvious symmetries to restrict $\theta$ to lie between $0$ and $\pi/2$.) If you draw a picture, it's instantly clear that

$$\sin\theta = {1-\epsilon-y \over L(\epsilon,y,\theta)}$$

so $L(\epsilon,y,\theta) = (1-\epsilon-y)/\sin\theta$, at which point we can pretty much declare victory because the integral

$$\int_0^{\pi/2} {d\theta \over \sin\theta}$$


share|improve this answer
Nice argument. That's much cleaner than mine. –  Douglas Zare Aug 27 '12 at 20:00

There is a considerable literature on this question and the various generalizations (mankind HAS, in fact, studied the distribution of the path lengths, and not just the expectation, though apparently this is still open in higher dimensions). A good reference is:

F. Golse, Homogenization and kinetic models in extended phase-space

share|improve this answer

J. Marklof and A. Strömbergsson have pretty much complete results for the distribution you're interested in - both on the plane and in higher dimensions. Check

J. Marklof and A. Strömbergsson, The distribution of free path lengths in the periodic Lorentz gas and related lattice point problems, Annals of Mathematics 172 (2010) 1949–2033

J. Marklof and A. Strömbergsson, The Boltzmann-Grad limit of the periodic Lorentz gas, Annals of Mathematics 174 (2011) 225-298

share|improve this answer

You use the fact that the set of points and directions where $L(\epsilon)=\infty$ has measure zero. One can translate this problem to considering closed billiard paths through $p$ in a square, which avoid the corners by $\epsilon$. In the vicinity of a closed path this may be used to bound the number of reflections necessary to reach a corner.

share|improve this answer

Your Answer


