My eldest daughter Lisa recently brought home a note from her school from her computer class teacher. Apparently, the 5th grade kids have been learning to program in Logo, in the MicroWorlds programming environment. I have very pleasant memories of learning to program in Logo back when I was in middle school. If you’re not familiar with Logo, it’s a simple variant of Lisp designed by Seymour Papert, whereby the programmer directs a turtle cursor to move about the screen, moving forward some distance, turning left or right, etc. The turtle can also be directed to raise or lower a pen, and one can draw very pretty pictures in Logo as the track of the turtle’s motion.

Let’s restrict our turtle’s movements to alternating between taking a step of a fixed size S, and turning either left or right through some fixed angle A. Then a (compiled) “program” is just a finite string in the two letter alphabet L and R, indicating the direction of turning at each step. A “random turtle” is one for which the choice of L or R at each step is made randomly, say with equal probability, and choices made independently at each step. The motion of a Euclidean random turtle on a small scale is determined by its turning angle A, but on a large scale “looks like” Brownian motion. Here are two examples of Euclidean random turtles for A=45 degrees and A=60 degrees respectively.

turtle_Euclid

The purpose of this blog post is to describe the behavior of a random turtle in the hyperbolic plane, and the appearance of an interesting phase transition at \sin(A/2) = \tanh^{-1}(S). This example illustrates nicely some themes in probability and group dynamics, and lends itself easily to visualization.

Let’s work in the Poincaré unit disk model of hyperbolic geometry. In this model, the hyperbolic plane is thought of as the interior of the unit disk in the Euclidean plane, and the hyperbolic metric is related to the Euclidean metric by multiplying distances infinitesimally by 2/(1-r^2) at a point whose (Euclidean) distance from the origin is r. In this model, the hyperbolic distance between a point at the origin and a point at Euclidean distance r away is 2\tanh^{-1}(r). So, at the risk of being slightly confusing, let me say that a hyperbolic random turtle has “step size S” if the first step, starting at the origin, lands on the Euclidean circle of radius S.

I wrote a little program called turtle to illustrate the motion of a random turtle for various values of S and A; it can be downloaded from my github repository if you want to play with it. The figures below are all produced with it. Let’s look at a few examples.

turtle_picture_1turtle_picture_2turtle_picture_3turtle_picture_4turtle_picture_5

The phase transition alluded to earlier is very evident in these pictures: for large S and small A, the turtle zooms off in an almost straight line to the boundary, with very little wiggling along the way. For small S and large A, the turtle meanders around aimlessly, filling up lots of space, intersecting its path many times, until eventually wandering off to the boundary in a more or less random direction.

For a given length, what is the critical turning angle? The “worst case” scenario is a turtle which always turns left (or always turns right). For such a turtle there is a critical angle (for a given length) such that the trajectory of the turtle just fails to close up. Technically, the hyperbolic isometry describing the turtle’s motion at each step is parabolic, and fixes a unique point at infinity. The segments of the turtle’s trajectory will then osculate an invariant horocycle for the parabolic isometry, when the (discrete) atoms of positive turning curvature at the vertices exactly balance the negative curvature of the hyperbolic plane.

turtle_picture_osculating_horocycle

A critical turtle trajectory osculates a horocycle

The critical relationship is precisely that \sin(A/2) = S, with our convention about the relationship between S and the hyperbolic length of the segments. For angles smaller than this value, the trajectory is a quasigeodesic — i.e. it stays within a bounded (hyperbolic) distance of an honest geodesic, and does not wind around at all. For angles bigger than this value, there is a definite probability at every stage that the trajectory will undergo some number of complete full turns, and it might return to some region it has visited before. The trajectory still converges to a point at infinity with probability one (this is a very robust feature of random walk in negatively curved spaces) but it makes deviation of order \log(n) from this geodesic in the first n steps.

One interesting statistic for an immersed path \gamma in the plane is the winding number. If we trivialize the unit tangent bundle, the derivative \gamma' can be thought of as a map to the circle, and we can ask how many times it winds around. In the Euclidean plane there is a natural trivialization of the unit tangent bundle via parallel transport, because of the flatness; technically there is a flat orthogonal connection. In the hyperbolic plane any orthogonal connection must have curvature, but there is a flat connection with structure group equal to the group of (hyperbolic) isometries, by identifying the unit circle in each tangent bundle with the circle at infinity. Explicitly: every tangent vector v is tangent to a unique oriented geodesic \gamma which limits to a unique point \gamma^+ in the circle at infinity. This identification is global, and respected by the natural action of the isometry group.

For a random turtle in the Euclidean plane, the trajectory turns left or right through angle A at every step, and the winding number after some number of steps is distributed like simple random walk on the integers. That is, if W_n denotes the winding number after n steps, then the random variable n^{-1/2} W_n converges to a normal distribution with mean zero and standard deviation A. The point is that the increments at every stage are independent and identically distributed. On the other hand, for a random turtle in the hyperbolic plane, each step induces an isometry of the hyperbolic plane, and thereby a projective transformation of the boundary circle. There is no natural invariant metric on this boundary circle, and therefore it is more subtle to compute winding number from this action.

Let’s abstract the discussion somewhat. Suppose we are given a finite collection X of (orientation-preserving) homeomorphisms of the circle. The circle is covered by the line, and the group \text{Homeo}^+(S^1) of orientation-preserving homeomorphisms of the circle is covered by the group of orientation-preserving homeomorphisms of the line that commute with integer translation.  Call this covering group \text{Homeo}^+(S^1)^\sim, where the tilde denotes central extension. Poincaré’s rotation number is a function from \text{Homeo}^+(S^1)^\sim to the real numbers, whose reduction mod the integers is the usual rotation number for a circle homeomorphism. Thinking of our turtle as turning left or turning right continuously implicitly determines a lift of the motion to the universal covering group, so we can suppose that we are given a finite collection X^\sim of lifts of X. Now we consider some random walk x_0 x_1 x_2 \cdots where each x_i is drawn independently and uniformly from X^\sim, and we ask about the distribution of the random variable W_n, which is defined to be the (real valued) rotation number of the composition x_0 x_1 \cdots x_n.

Now, although there is typically no metric/measure on the circle left invariant by X there is a natural measure — the so-called harmonic measure — which is invariant on average. If \mu is a probability measure on the circle, we can define X_* \mu: = \frac {1}{|X|} \sum_{x\in X} x_*\mu, and then let \mu_n: = \frac 1 n \sum_{i=0}^{n-1} X_*^i \mu. The \mu_n have a subsequence converging to a fixed point for the operator X_*; such a fixed point \mu_\infty is a harmonic measure. Note that such a harmonic measure is quasi-invariant under every x \in X. The measure \mu_\infty pulls back to a locally finite measure \mu_\infty^\sim on the real line, and this pullback is harmonic for the action of X^\sim. We can define a function M:\mathbb{R} \to \mathbb{R} as follows. For each t choose some T\ll t and define M(t) = \mu_\infty([T,t]) - \mu_\infty([T,0]). Then M is monotone nondecreasing, and M(t+n) = M(t) + n for any t and any integer n. In particular, the winding number W_n satisfies |W_n - M(x_0x_1\cdots x_n(0))| < 1 for any n.

Now, by the definition of a harmonic measure, for any s,t and for random x\in X^\sim, there is an equality \mathbb{E}(M(x(t)) - M(x(s))) = M(t) - M(s) (here the notation \mathbb{E}(\cdot) means the expectation of a random function). In particular, \mathbb{E}(M(x(t))) - M(t) is constant independent of t. We call this constant quantity the drift and denote it by D. Define a sequence of random variables W'_n by W'_n:=M(x_0x_1\cdots x_n(0)) - nD. By the calculation above we see that for each n, the expectation of W'_n conditioned on a particular value of W'_{n-1} is equal to the given value of W'_{n-1}. More informally, we could just write \mathbb{E}(W'_n) = W'_{n-1} and say that at every step, the expected change in the value of W' is zero. This is a familiar object in probability theory, and is known as a martingale. One can think of the values of the martingale as the wealth of a gambler who makes a succession of fair bets. The wealth of such a gambler over time looks roughly like a simple random walk, after reparameterizing time proportional to the rate at which the gambler takes risks (as measured by the variance of the outcomes of each bet). For our random product of homeomorphisms, there are two possibilities: either the martingale converges, as successive “bets” become smaller and smaller, and the winding number converges to some final value (this happens in the case that the length of the turtle’s steps are big compared to the turning angle), or else the position of the point x_0x_1\cdots x_n(0) is equidistributed in the circle with respect to \mu_\infty, and there is a central limit theorem: n^{-1/2}W'_n converges to a Gaussian.

Returning to our original setup, the left-right symmetry forces the drift D to equal zero, and we can identify W'_n with the winding number W_n up to a constant. How does the variance of n^{-1/2}W_n depend on the variables S and A? The following figure shows a graph of the variance as a function of S and A. The red line marks the phase transition from zero variance (i.e. quasigeodesic turtle trajectories) to strictly positive variance.

phase_transition

As one sees from the figure, the phase transition is not something sharp that can be easily seen experimentally, and in fact, the graph looks completely smooth along the phase locus (although we know it can’t be real analytic there). This experimental observation can be theoretically confirmed, as follows.

Consider the behavior of a random turtle, with fixed stepsize, for some turning angle A’ just marginally bigger than the critical angle A. The critical turtle trajectory bounds an infinite polygon with edges of length 2\tanh^{-1}(S) and external angles A; this polygon can be decomposed into semi-ideal triangles with internal angles (\pi-A)/2, \pi/2, 0 and finite side length S':=\tanh^{-1}(S). As we deform the angle A we get a new triangle with angles \alpha, \pi/2,\epsilon where \alpha = (\pi-A')/2, and the angle \epsilon is opposite a side of fixed length S'. The hyperbolic law of cosines says in this context that \cos(\epsilon) = \sin(\alpha)\cosh(S'). Since S' is fixed, and \epsilon is small, we can approximate \cos(\epsilon) \sim 1-\epsilon^2/2; in other words, the angle \epsilon is of polynomial (actually, quadratic) order in the difference A'-A. Now, suppose \epsilon = 1/N for some very large N. A turtle trajectory with the property that there is at least one left and at least one right turn in every N steps will be quasigeodesic; the only full twists will occur when there is a sequence of at least N left turns or right turns in a row. This is a very rare occurrence — it will typically only happen twice in a sequence of 2^N steps. Hence the variance of the winding number W_n is of order 2^{-N}. In particular, the graph of the variance is tangent to zero to infinite order along the phase locus, as claimed.

(Update:) At Dylan’s request I’ve added a slice of the variance graph, at S=0.05 with angle varying from 0 to 0.2. The vertical axis has been stretched (relative to the 3d graph above) for legibility. The phase transition is at angle 0.1000417 and I must say the graph looks pretty flat there.

phase_slice