A random walk on random lines

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.

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.

, ,