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.

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 . 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 at a point whose (Euclidean) distance from the origin is . In this model, the hyperbolic distance between a point at the origin and a point at Euclidean distance away is . 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.

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.

A critical turtle trajectory osculates a horocycle

The critical relationship is precisely that , 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 from this geodesic in the first steps.

One interesting statistic for an immersed path in the plane is the winding number. If we trivialize the unit tangent bundle, the derivative 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 is tangent to a unique oriented geodesic which limits to a unique point 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 denotes the winding number after steps, then the random variable 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 of (orientation-preserving) homeomorphisms of the circle. The circle is covered by the line, and the group 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 , where the tilde denotes central extension. Poincaré’s rotation number is a function from  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 of lifts of . Now we consider some random walk where each is drawn independently and uniformly from , and we ask about the distribution of the random variable , which is defined to be the (real valued) rotation number of the composition .

Now, although there is typically no metric/measure on the circle left invariant by there is a natural measure — the so-called harmonic measure — which is invariant on average. If is a probability measure on the circle, we can define , and then let . The have a subsequence converging to a fixed point for the operator ; such a fixed point is a harmonic measure. Note that such a harmonic measure is quasi-invariant under every . The measure pulls back to a locally finite measure on the real line, and this pullback is harmonic for the action of . We can define a function as follows. For each choose some and define . Then is monotone nondecreasing, and for any and any integer . In particular, the winding number satisfies for any .

Now, by the definition of a harmonic measure, for any and for random , there is an equality (here the notation means the expectation of a random function). In particular, is constant independent of . We call this constant quantity the drift and denote it by . Define a sequence of random variables by . By the calculation above we see that for each , the expectation of conditioned on a particular value of is equal to the given value of . More informally, we could just write and say that at every step, the expected change in the value of 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 is equidistributed in the circle with respect to , and there is a central limit theorem: converges to a Gaussian.

Returning to our original setup, the left-right symmetry forces the drift to equal zero, and we can identify with the winding number up to a constant. How does the variance of 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.

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 and external angles A; this polygon can be decomposed into semi-ideal triangles with internal angles and finite side length . As we deform the angle we get a new triangle with angles where , and the angle is opposite a side of fixed length . The hyperbolic law of cosines says in this context that . Since is fixed, and is small, we can approximate ; in other words, the angle is of polynomial (actually, quadratic) order in the difference . Now, suppose for some very large . A turtle trajectory with the property that there is at least one left and at least one right turn in every steps will be quasigeodesic; the only full twists will occur when there is a sequence of at least left turns or right turns in a row. This is a very rare occurrence — it will typically only happen twice in a sequence of steps. Hence the variance of the winding number is of order . 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 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.