A random walk on random lines

Question

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

---

     
Update. Here is a first attempt at an implementation:

---

     

---

I just stopped the iteration after $p_8$.

Addendum. Bill Thurston's convincing analysis coupled with independent simulations suggest it remains finite, perhaps with probability about $0.16$. Interesting questions remain: 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?

Answer 1

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.

^{(source: Wayback Machine)}

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.

Answer 2

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.

, ,

Answer 3

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.