Path length of ball on tilted, perforated plane - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T17:09:37Z http://mathoverflow.net/feeds/question/105616 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105616/path-length-of-ball-on-tilted-perforated-plane Path length of ball on tilted, perforated plane Joseph O'Rourke 2012-08-27T11:00:07Z 2012-08-28T10:58:37Z <p>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$.</p> <blockquote> <p>What is the expected length $L(\epsilon)$ of its roll before it falls through a hole?</p> </blockquote> <p>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$: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/TiltDisks.jpg" alt="Tilted Plane Disks"> <br /> I am particularly interested in the growth rate of $L(\epsilon)$.</p> <p>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.</p> <p>Perhaps there is an approach that employs techniques from rational approximations? All ideas welcomed&mdash;Thanks!</p> <p><b>Addendum</b>. 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. <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/Histograms200300.jpg" alt="Histograms"><br /> 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$!</p> http://mathoverflow.net/questions/105616/path-length-of-ball-on-tilted-perforated-plane/105617#105617 Answer by Karl Fabian for Path length of ball on tilted, perforated plane Karl Fabian 2012-08-27T11:19:09Z 2012-08-27T11:28:22Z <p>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.</p> http://mathoverflow.net/questions/105616/path-length-of-ball-on-tilted-perforated-plane/105623#105623 Answer by Douglas Zare for Path length of ball on tilted, perforated plane Douglas Zare 2012-08-27T13:01:29Z 2012-08-27T13:19:10Z <p>The expected length is infinite when $\epsilon \lt 1/2$. </p> <p>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$. </p> <p>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. </p> <p>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.</p> <p>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.$</p> http://mathoverflow.net/questions/105616/path-length-of-ball-on-tilted-perforated-plane/105646#105646 Answer by Barry Cipra for Path length of ball on tilted, perforated plane Barry Cipra 2012-08-27T17:47:31Z 2012-08-27T17:47:31Z <p>This is just a small streamlining of Douglas Zare's proof that the expected length $L(\epsilon)$ is infinite when $\epsilon &lt; 1/2$.</p> <p>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</p> <p>$$L(\epsilon) > {1\over \pi/2}\int_\epsilon^{1-\epsilon}\int_0^{\pi/2}L(\epsilon,y,\theta)d\theta dy,$$</p> <p>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</p> <p>$$\sin\theta = {1-\epsilon-y \over L(\epsilon,y,\theta)}$$</p> <p>so $L(\epsilon,y,\theta) = (1-\epsilon-y)/\sin\theta$, at which point we can pretty much declare victory because the integral</p> <p>$$\int_0^{\pi/2} {d\theta \over \sin\theta}$$</p> <p>diverges.</p> http://mathoverflow.net/questions/105616/path-length-of-ball-on-tilted-perforated-plane/105647#105647 Answer by Igor Rivin for Path length of ball on tilted, perforated plane Igor Rivin 2012-08-27T18:10:45Z 2012-08-27T18:10:45Z <p>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:</p> <p><a href="http://hal-polytechnique.archives-ouvertes.fr/docs/00/54/31/38/PS/KinExtPhSp.ps" rel="nofollow">F. Golse, Homogenization and kinetic models in extended phase-space</a></p> http://mathoverflow.net/questions/105616/path-length-of-ball-on-tilted-perforated-plane/105677#105677 Answer by LazyCat for Path length of ball on tilted, perforated plane LazyCat 2012-08-28T02:55:08Z 2012-08-28T02:55:08Z <p>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 </p> <p>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 </p> <p>J. Marklof and A. Strömbergsson, The Boltzmann-Grad limit of the periodic Lorentz gas, Annals of Mathematics 174 (2011) 225-298</p>