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

I am wondering if this random walk remains finite with positive probability. Start with three lines $A,B,C$ that are extensions of an equilateral triangle. Let $p_0$ be one corner. Generate a line $L_1$ through $p_0$ at a random orientation. Now, from $p_0$ walk either right or left with equal probability along $L_1$ until you hit the first intersection point $p_1$ of $L_1$ with $\{A,B,C\}$, or reach $\infty$. Clearly there is a $\frac{1}{2}$ chance you stay finite. Through $p_1$ generate a randomly oriented line $L_2$, and walk right or left to the first intersection point $p_2$ of $L_2$ with $\{A,B,C,L_1\}$. And so on.

On the one hand, there are always routes to $\infty$. On the other hand, as the line arrangement thickens, the number of steps to escape grows. So if the process survives a few iterations, it becomes less likely it will escape. Intuition is likely useless here, but it feels to me like this should remain finite. Can anyone see an argument?

If it does remain finite, then other questions suggest themselves, but perhaps I should start with the basic infinite/finite question.

Here is a hand-executed example (corrected from the original by Pablo):
alt text
Update. Here is a first attempt at an implementation:
alt text
I just stopped the iteration after $p_8$. I'll report more substantively after I have collected some data.

Addendum. Great progress! Bill Thurston's convincing analysis coupled with independent simulations. I appreciate the interest! Of course many interesting questions remain: What is the probability of remaining finite? What is the distribution of the number of steps before shooting off to $\infty$? When a path remains finite forever, does its total length remain bounded?

share|improve this question
    
Are you conditioning the walk to remain finite after n steps? Otherwise the probability of going to infinity is at least 1/2 just after the first step. Or perhaps do you want to know whether the walk remains finite with positive probability? –  Alex R. Sep 22 '10 at 21:11
    
@Alex: Yes, exactly as you put it. I see I misphrased it. Will correct. Thanks! –  Joseph O'Rourke Sep 22 '10 at 21:24
1  
In the figure, $p_2$ should be on line $B$ right? –  Pablo Lessa Sep 22 '10 at 21:26
    
@Pablo: Oops! I hand generated it (with random #s). Will correct! Thanks! –  Joseph O'Rourke Sep 22 '10 at 22:25
    
Do you have any numerical evidence going one way or the other? –  j.c. Sep 22 '10 at 23:59
show 1 more comment

3 Answers

up vote 9 down vote accepted

There is a positive probability that the process never escapes to $\infty$.

I hope I have this basically correct. Please criticize.

To set the stage to analyze this, let's list some related processes, with related questions:

Process 2: Start with 3 great circles on $S^2$, and one of their intersection points $p$.

Iterate: given a set $X$ of great circles and an intersection point $q$, adjoin to $X$ a random great circle $C$ through $q$, and move $q$ to a random intersection point of $C$ with the other great circles adjacent to $q$.

Does the point $q$ converge on $S^2$ a.s.? Claim: yes, it converges.

Let's first back down to related processes in one dimension that are easier to analyze

One-dimensional version

Process 0: Start with two points on a circle, and a choice $p$ of one of them. Iterate: Given a collection $X$ of points on a circle and a choice $q$ from among them, add a random element of $S^1$ to $X$ and move $q$ one step randomly chosen to be clockwise or counterclockwise.

Claim: Process 0 converges almost surely.

Let's analyze how likely it is for $q$ to reach any particular point $q_0$ from among the others. Suppose the clockwise combinatorial distance is $a$ with metric distance $A$ and counterclockwise the measurements are $b$ and $B$. For convenience we'll take the length of the circle to be $1$. When a random point is added, either $a$ increases or $b$ increases, and when $q$ moves, one of the two is decreased by one and the other increased by one. Then $a(t)$ evolves as a random walk on integers with drift, pushing it higher by 1 with probability $A(t)$. The chance of ever hitting 0 is comparable to the chance that a random walk exceeds some linear function of $t$ at time $t$. Since the location of an unbiased random walk at time $t$ has variance proportional to $\sqrt t$, if it doesn't happen in a short time it becomes vanishingly unlikely it will ever happen.

It follows that there's a positive probability $q$ will never reach $q_0$. We can wait and repeat this with various $q_0$'s at different times, and conclude that $q$ a.s. converges on $S^1$.

ADDED: Here's a plot of a typical simulation of process 0, starting with 30 random points on the circle and going for 400 steps. Time proceeds left to right; the set $X_t$ at a particular time is a vertical slice. The red path shows the trajectory of $q_t$. It wraps around the circle near the beginning. Since the circle grows linearly in length, the distance $q$ is likely to go on the circle after time $t$ is bounded and proportional to $\sqrt t$, so its position converges a.s.

alt text

Analysis of Spherical version

Let's return to process 2.

For any particular great circle $C_0$ in $X$, let's think about the probability of $q$ ever reaching $C_0$. At time $t$, $C_0$ is divided into $t+2$ intervals by the other circles. Define the combinatorial distance from $q$ to $C_0$ as the number of great circle one must cross to get from $q$ to the a point. This is a step function that changes by one of $-1,0,1$ at each intersection point with another circle. (The 0 case is when $q$ is actually on the relevant circle).

For the process, when a new circle through $q$ is added, some antipodal pair of intervals are split in half, with all distances remaining constant. Let $\alpha$ be the distance along $C_0$ between its intersection points with the original great circles at $q$, measured in the direction that encloses the new great circle $C'$. Then when $q$ is moved along $C'$ to a neighboring point, the distance is increased by $2$ on a segment of $C_0$ of length $\alpha$ (the far side of the angle), it is decreased by 1 on a segment of length $\alpha$ (the near side of the angle), and in the remainder of the circle, half the length is increased kept the same and half is increased by 1.

The combinatorial distance of $q$ to any particular point on $C_0$ behaves as a random walk, with a somewhat complicated bias pushing it higher. When $q$ is reasonably close to the center, the bias at each step is greater than some constant. We can conclude that with positive probability, none of these distances ever reach 0. Therefore, $q$ converges a.s. on $S^2$.

Process 1: original question

Do this in the same way as process 2, but keep track of the combinatorial distance to segments of the line at infinity.

share|improve this answer
    
Impressive analysis! The comparison of $\sqrt{t}$ variance with needing to exceed linear in $t$ is intuitively convincing. Now I will certainly implement this. I appreciate you taking the time to reply in such detail. –  Joseph O'Rourke Sep 23 '10 at 1:23
    
I'd suggest implementing the $S^1$ process first. Programming at a low level, ordered lists can be implemented as trees, and a simulation would run quickly. For a higher-level language like Mathematica, you should try to make sure the higher-level constructs you use are reasonably efficient with ordered insertion and find, and not, for example copying the entire list each time you add an element. For the 2-dimensional cases, in principle I think there are good data structures, but I doubt if Mathematica has efficient routines for them. It might get slow, probably $\ge$ quadratic*log time. –  Bill Thurston Sep 23 '10 at 1:59
    
A simplified version of process $0$ (process $-1$?) is the following: At step $n$ jump $1/n$ clockwise or counter-clockwise with equal probability (this is the expected lenght of the jump of process $0$). Once lifted to $\mathbb{R}$, you're just considering a martingale which is to sum the harmonic series with random independent signs. Since the variance of each partial sum is uniformly bounded you can apply the martingale convergence theorem. The lift of process 0 to $\mathbb{R}$ also seems to be a martingale. Maybe there's a similar proof of it's convergence? –  Pablo Lessa Sep 23 '10 at 21:16
    
Sorry, process 0 isn't a martingale after all since the jumps to each side are unequal. –  Pablo Lessa Sep 23 '10 at 21:36
1  
More on process 0: Take $M_n$ the maximum size of any of the intervals on the circle at time $n$. The sequence $M_n$ is non-increasing and converges almost surely to 0. Let $X_n$ be plus or minus one according to if the jump at step $n$ is clockwise or not. If the random sum $S_n = X_1M_1+\cdots+X_nM_n$ converges then so does process 0. This process $S_n$ is a martingale. If one can show that $\sum\mathbb{E}(M_n^2)$ is finite then the conclusion follows. A similar approach might work for process 2 (depending on estimating the statistics of the diameter of the largest region at time $n$). –  Pablo Lessa Sep 24 '10 at 16:14
show 10 more comments

I don't know, how to find the probability analytically, but numerical simulation is actually simple. It suggests, that the process remains finite with probability $0.162\pm 0.003$. Here there is a simulation in Wolfram Mathematica 7.0.1. Typical examples of processes with 20+ steps are shown below. 20 steps are drawn. Initial triangle is always in the center, but on some pictures it is too small to see it.

alt text, alt text, alt text

share|improve this answer
    
You are ahead of me! I just ran 20K iterations and found the probability to be 0.165, which should be a slight overestimate (because I didn't run to $\infty$!). So entirely consistent with your results. Perhaps the probability is $16/\pi^4$? [Just kidding!] –  Joseph O'Rourke Sep 24 '10 at 0:03
add comment

For your specific example, starting at one of the points on the equilateral triangle $abc$ composed of the segments between pairs of the intersection points of the lines $A$, $B$, and $C$, with no lines draws other than the three initial lines,

the three lines divide the $\mathbb{R}^2$ space into 7 regions, the center of the triangle, the three regions outside the triangle touching the line segments $ab$ (defined on line $C$), $ac$ (defined on line $B$), $bc$ (defined on line $A$), and the regions extending out from points $a$,$b$,$c$ away from the triangle and not touching the line segments.

I am working under the impression that you have random direction defined as a uniform distribution over the possible angles to go in, say $0 \le \theta \lt 2\pi$. This allows you to define the direction you're going in with one random variable and still defines the line as the extension in the positive and negative directions. Picking a line and then picking "left" or "right" requires calculating two pseudo-random numbers, numerically using up twice as much computation time with each step of the simulation. It also leads to ambiguity in defining "left" or "right" clearly for all possible orientations of the line. I also assume that even though the probability of picking the exact same angle of the line which has been intersected is zero in mathematical terms, it is non-zero because of the level of numerical precision used in computations of the simulation. If the new line's angle is the same as the current line's angle, I assume that the next point is the same as the current point (rather than picking a random distance along the already exisiting line, the intersection occurs at all points along the line, and the starting point is technically the first point of intersection if you define it that way), and you pick another new angle.

If you start at a point on one of the line segments of the triangle (rather than on one of the points of the triangle), the initial random line has a slightly greater than a $1/6$ change of escaping to infinity, and a slightly lower than $5/6$ chance of intersecting one of the lines. For example, starting on the line segment $ab$ on the right side of the triangle (along line $C$ and on the triangle, but not at point $a$ or point $b$), the only way to escape to infinity is if $0 \le \theta \le \pi /3$, and the ways to intersect a line occur for $\theta \gt \pi /3$. Similar statements can be made for each open region on the outside of the polytope created by the intersections of the lines.

If you start at one of the end-points of the equilateral triangle, then each point allows three open outward facing regions in which a ray could escape to infinity, and a line below it effective blocking the $\pi$ radians of angular directions which can intersect a ray. For example, starting at $P_0$ as you've defined it (point $a$ as I've labeled it), the union of the three outward facing regions (each of $\pi/3$ in angular extent) is available as the escape region, while the region of $\pi/2 \lt \theta $ leads to an intersection on the line $A$. The three escape regions sum up to an angular region $0 \lt \theta \lt pi/2$ (excluding the angles $\theta=\pi / 3$ and $\theta=2\pi / 3$ of angular extent $\pi$.

Since equal angular extents are available for escape and for intersection, the first step has $p=1/2$ probability of escape and $p=1/2$ probability of intersection.

The first point of intersection $P_1$ (if it exists) is required to be on line $A$, with probability $1/3$ of being on line segment $bc$, and probability of $2/3$ of being on line $A$ outside of the line segment $bc$.

Each new point of intersection will either be

  • (1) contained within the polytope defined by the points of intersections of the lines drawn thus far, in which case no escape zones are available and the step will be an intersection with $p=1$.

  • (2) on a portion of a line which has available to it an escape zone allowing escape to infinity.

Each line that extends the boundaries of the polytope will decrease the angular extents available for escape zones and increase the likelihood of providing an intersection point. This is because each escape zone has a limited angular extent, $\theta_1 \le \theta \le \theta_2$, and the new line can only maintain that angular extent by being parallel to one of the two lines defining the angular extent of the escape zone. Any other angle will increase the area of the polytope and close off some of the angular extent available for that escape zone.

That's the extent of my approach thus far. I'll have to ruminate on this a bit further, and add to this. Thanks for a very interesting question, Joseph.

share|improve this answer
    
latex editing slowing down my editing, I'll comment this correction in now, and edit it later. "while the region of π/2<θ leads to an intersection on the line A" really should read "while the region of $\pi \lt \theta$ leads to an intersection on the line $A$ " –  sleepless in beantown Sep 23 '10 at 20:25
1  
For long replies, you can uncheck "Preview math" to turn off automatic preview and thenceforth click the "one-shot preview" button whenever you want to check that things are OK. –  j.c. Sep 23 '10 at 20:30
    
@sleepless: Thank you for the very interesting thoughts! In the current implementation, I generate a random ray, uniform in $(0,2\pi]$, with what I called left/right in my original formulation implemented as forward/backward along the directed line containing the ray. –  Joseph O'Rourke Sep 23 '10 at 21:09
    
@jc, thanks for the info. I'll try that out later today. @Joseph O'Rourke, if tge ray is uniform in $(0,2\pi]$ then choosing left/right or forward/backward is redundant and maps $(0,2\pi] \to (\pi, 3\pi]$ equivalent to the joined regions ($\pi, 2\pi] , (0,\pi]$. You can just pick a direction $(0,\pi]$ and then pick forward/backward for the direction, or pick a direction $(0,2\pi]$ and note that it already covers the full $2\pi$ radians angular extent possible. This way only needs and maps 1 random/pseudorandom long integer, rather than map 1st PRN to a real and 2nd PRN to +/- binary choice. –  sleepless in beantown Sep 23 '10 at 23:42
    
@sleepless: Good point re range! –  Joseph O'Rourke Sep 24 '10 at 14:07
add comment

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.