A rotation chosen at random

Pick up a solid object, close the eyes, and turn it to an orientation chosen at random. Compared with where it started, how far has it been turned? Every orientation of a body is reached from its starting one by a single turn about some axis through some angle, so the question has an answer, and the answer is not ninety degrees. A uniformly random rotation turns the body by 126.5 degrees on average, by more than 132 degrees half the time, and by less than ten degrees only about three times in ten thousand.

That is a fact about what at random has to mean for rotations, and the quaternions are the cleanest way to see it. A unit quaternion is a rotation, named twice — $q$ and $-q$ turn a body identically — and the unit quaternions fill the three-dimensional sphere in four-dimensional space. Choosing a point of that sphere evenly is the right way to choose a rotation, and two recipes that sound equally fair turn out to be wrong in opposite directions.

What “at random” has to mean for a turn #

For a number between nought and one, “at random” means uniformly, and uniformly means that every interval of the same length is equally likely. Rotations have no intervals, and the condition has to be restated in the form that survives: a random rotation is uniform when composing it with any fixed rotation leaves its distribution unchanged. If a body is turned at random and then turned again by some definite amount — ninety degrees about the vertical, say — the result should be just as random as before, with no orientation any more or less likely than it was. The same must hold when the fixed turn is applied first.

There is exactly one distribution with that property. Alfréd Haar proved in 1933 that every group of this kind — compact, and continuous in the right sense — carries one and only one probability distribution unchanged by multiplication on either side, now called its Haar measure. For rotations of three-dimensional space it is the only candidate for “uniform”, and the question is how to describe it concretely.

The quaternions describe it in one line. A unit quaternion $q = w + xi + yj + zk$ with $w^2 + x^2 + y^2 + z^2 = 1$ rotates three-dimensional space by $v \mapsto q v \bar q$, through the angle $\theta = 2\arccos|w|$ about the axis $(x, y, z)$. Composing two rotations is multiplying their quaternions, and multiplying every point of the three-sphere by a fixed unit quaternion moves the sphere rigidly onto itself — it is a rotation of four-dimensional space, and a rotation preserves area on a sphere just as it does on a globe. So the even distribution on the three-sphere is unchanged by composing with a fixed turn on either side, which is exactly Haar’s condition, and since $q$ and $-q$ give the same rotation, taking a point evenly and forgetting its sign gives the uniform rotation.

The semicircle hidden in the angle #

The figure at the top says that this uniform rotation turns a body a long way. The reason is visible one step earlier, in the first coordinate $w$ of a uniformly chosen point on the three-sphere.

On the ordinary sphere in three-dimensional space, Archimedes found that a band between two parallel planes has the same area as the band they cut from the enclosing cylinder. One coordinate of a uniform point on the ordinary sphere is therefore uniform on the interval from −1 to 1: every height is equally likely. On the three-sphere the same calculation gives a different answer, because the slice at height $w$ is a two-sphere of radius $\sqrt{1 - w^2}$, with area proportional to $1 - w^2$, and a step $dw$ in height is a step $dw/\sqrt{1 - w^2}$ along the slanting surface. The product is $\sqrt{1 - w^2}$, and normalised the density of $w$ is $(2/\pi)\sqrt{1 - w^2}$, a semicircle. On the ordinary sphere the same two factors are a circle’s length, proportional to $\sqrt{1 - w^2}$, and the same slant, and they cancel — which is the hat-box theorem.

The semicircle has most of its weight in the middle, near $w = 0$, and $w = 0$ is a half turn. A small turn needs $|w|$ close to one, at the semicircle’s thin ends. Pushing the semicircle through $\theta = 2\arccos|w|$ gives the angle’s density, $(1 - \cos\theta)/\pi$, which is nought at no turn and largest at a half turn. Its mean is $\pi/2 + 2/\pi$ radians, 126.48 degrees, and the chance of a turn under an angle $\alpha$ is $(\alpha - \sin\alpha)/\pi$, which for small angles is about $\alpha^3/(6\pi)$. Turns of less than ten degrees come up 0.028 per cent of the time; turns of less than one degree, about three times in ten million.

The cube in that $\alpha^3$ has a plain meaning. A turn close to the identity is described by three small numbers — how far about each of three axes — so the rotations within $\alpha$ of the identity form a small ball in a three-dimensional space, whose volume grows like the cube of its radius. Most of the volume of any ball lies near its edge, and most of the rotations lie far from the identity for the same reason.

The semicircle is not a coincidence of four dimensions, either. The same shape governs how the eigenvalues of a large random symmetric matrix spread out, where Eugene Wigner found it in 1955, and in that setting it is a theorem about matrices rather than about spheres. That two quite different objects share the curve is less mysterious than it looks — in both, a count of degrees of freedom is weighted by a square root — but the shared picture is a reminder that “uniform” on one object rarely looks uniform when it is read through a coordinate.

Two recipes that look fair #

The obvious recipe for a random rotation is to pick its two ingredients at random: an axis, uniformly over the sphere of directions, and an angle, uniformly between nought and a half turn. It produces a flat line in the figure at the top — and a flat line is exactly what the uniform rotation is not. It overweights small turns by a factor that grows without bound near the identity, because it gives the thin ends of the semicircle the same weight as its middle. The axis is right and the angle is wrong; drawing the angle from $(1 - \cos\theta)/\pi$ instead repairs it.

The other common recipe uses Euler angles: a turn by $\alpha$ about the vertical, then $\beta$ about a horizontal axis, then $\gamma$ about the vertical again. Every rotation can be written this way, so choosing the three angles uniformly — $\alpha$ and $\gamma$ round the full circle, $\beta$ over a half turn — looks like choosing every rotation equally. It produces the third curve at the top: too many turns near a half turn, and, less visibly, too many small ones as well.

The failure is easiest to see in where a single arrow ends up. The vertical turns $\alpha$ and $\gamma$ do not move an arrow pointing straight up at all before the middle turn, so after all three the arrow’s height above the equator is $\cos\beta$ — and with $\beta$ uniform, every latitude gets the same share. But latitudes near the poles are short circles and latitudes near the equator are long ones, so equal shares per latitude crowd the tip towards the poles. Within twenty degrees of either pole the uniform rotation puts 1 − cos 20°, about six per cent, of the arrows; uniform Euler angles put 40/180, over twenty-two per cent.

The repair here is just as small: draw $\cos\beta$ uniformly between −1 and 1 instead of $\beta$, which is Archimedes’ theorem used as a recipe. Both repairs exist, and both recipes are still wrong as written, which is the general lesson. A coordinate system that describes every rotation does not, as a rule, describe them evenly, and the Euler angles are a particularly bad one because they have a singular place, at $\beta = 0$, where the first and third turns are about the same axis and the description stops being unique. A sphere cannot be given a smooth field of directions without a zero, and rotations cannot be given three smooth angles without a place where the angles break; the crowding at the poles is that breakage seen statistically.

Three correct ways to draw one #

The quaternion picture turns the problem into drawing a point evenly from the three-sphere, and three methods do it with no rejection and no fiddly correction.

Normalise four Gaussians. Draw four independent numbers from the standard bell curve and divide by their length. The joint density of four independent standard normals depends only on the distance from the origin, so the direction of the four-vector is uniform, and its direction is the unit quaternion wanted. This is the method used for every figure on this page.

Marsaglia’s pairs. George Marsaglia gave a method in 1972 that needs no logarithms. Draw two points uniformly from the unit disc, by rejection from a square, with squared distances $s_1$ and $s_2$ from the centre. Keep the first point’s coordinates as they are and multiply the second point’s by $\sqrt{(1 - s_1)/s_2}$. The four numbers lie on the three-sphere and are spread evenly over it, and the rejection wastes only about a fifth of the draws.

Shoemake’s three numbers. Ken Shoemake, writing for computer graphics in 1992, gave the closest thing to an explicit formula. Three uniform numbers $u_1, u_2, u_3$ between nought and one give the quaternion

$$\begin{aligned} q = \big(&\sqrt{1 - u_1}\,\sin 2\pi u_2,\ \sqrt{1 - u_1}\,\cos 2\pi u_2,\\ &\sqrt{u_1}\,\sin 2\pi u_3,\ \sqrt{u_1}\,\cos 2\pi u_3\big).\end{aligned}$$

It splits the four coordinates into two pairs, each pair a point on a circle, with the squared radii $1 - u_1$ and $u_1$ shared between them. That the split radius should be uniform is the four-dimensional relative of Archimedes’ hat-box: on the three-sphere it is the sum of squares of one pair of coordinates, not one coordinate, that is spread evenly. The two circles are the fibres of the Hopf fibration, which fills the three-sphere with linked circles, and Shoemake’s formula is a uniform choice of fibre followed by a uniform choice of point on it.

None of the three needs the angle law to be known in advance. That is the advantage of a description in which uniform means the plain thing — evenly on a sphere — rather than a formula found afterwards.

Sixty rotations that leave no gaps #

Randomness is often used to spread a sample of rotations evenly, for searching orientations of a molecule against a density map, say, or for averaging a measurement over all directions. Random points are a poor way to spread a few of anything evenly — they clump and leave holes, which is why points chosen deliberately to be even can beat random ones at integration — and rotations have their own even point sets ready made. The symmetry groups of the regular solids are finite sets of rotations, and a symmetric set has no reason to leave one region bare.

As quaternions, these groups were already met as points: the twelve rotations of the tetrahedron are the twenty-four units among the integer quaternions, taken in pairs; the cube’s twenty-four rotations are forty-eight unit quaternions; and the icosahedron’s sixty are the hundred and twenty icosians, the ring that builds an eight-dimensional lattice. Each set is closed under multiplication, and the figure confirms it on every product before measuring anything.

The measurement is the angle from a random rotation to the nearest rotation of the set. The tetrahedron’s twelve leave some rotations ninety degrees from every one of them — a quarter turn about a coordinate axis is such a rotation — and the cube’s twenty-four leave nothing more than about sixty-two degrees away. The icosahedron’s sixty bring every rotation within about forty-four degrees, with a typical miss of under thirty. Sixty rotations drawn at random, the same number, leave a typical miss nearly six degrees worse and some rotations nearly eighty degrees from all of them.

The groups do well because they spread themselves evenly by construction: each member sees the others arranged exactly as every other member sees them, which is what a group is. Chance offers no such guarantee. The same contrast between a random set and a regular one runs through every subject where a few points have to cover a space, and on the three-sphere the regular solids supply the regular sets for free.

Turning by the shortest way #

A random rotation is a point; moving a body smoothly from one orientation to another is a path, and the quaternion picture has a natural one. Between two points of the three-sphere there is a shortest arc of a great circle, and travelling along it at constant speed — spherical linear interpolation, which Shoemake introduced to animation in 1985 under the name slerp — turns the body steadily about one fixed axis, through exactly the angle of the single rotation that carries the first orientation to the second.

The figure’s target orientation is chosen to show the alternative at its worst, and it is not an exotic one. Euler angles of (180°, 40°, 180°) describe a turn of only forty degrees — the two half turns about the vertical cancel, apart from what the middle turn did to their axis — but turning each angle evenly from nought sends the body spinning through three hundred and fifty-five degrees on the way. The arrow’s tip spirals round instead of moving straight along a meridian. A half turn about the vertical, then the middle turn, then another half turn about the vertical, is the middle turn reversed, so the two large angles undo each other in the end; interpolating the angles evenly performs both half turns in full along the way. Slerp knows nothing about the coordinates and takes the forty degrees directly.

This is why so many systems that turn things smoothly — spacecraft attitude control, character animation, the orientation filters in a phone — store orientations as quaternions even when they report them as angles. The uniform rotation and the shortest turn are the same geometry: distance on the three-sphere is the angle of the turn between two orientations, and the even distribution and the straight path are both defined by it.

Small turns add up to a random one #

A random rotation can also be built slowly. Give a body a turn of a fixed small angle about an axis chosen at random, then another, and another. After enough turns the orientation should be uniform, since nothing remembers where the body started, and how quickly it forgets is a question that the quaternions answer exactly.

The exact part is the average of the trace, $1 + 2\cos\theta$. A turn by $\varepsilon$ about an axis chosen uniformly has, as an average matrix, a multiple of the identity — by symmetry it can favour no direction — and the multiple is $(1 + 2\cos\varepsilon)/3$, a third of the turn’s own trace. Independent turns multiply, so after $k$ of them the average total rotation is $((1 + 2\cos\varepsilon)/3)^k$ times the identity and its mean trace is three times that. For thirty-degree turns the factor is 0.9107, and the simulated means agree with it at every step listed in the figure, to the accuracy four thousand bodies can give. The uniform rotation has mean trace nought, since its average turn is a half turn’s worth of cancelling.

The full angle law takes longer to settle than its mean. After sixteen turns it is still far from uniform, after thirty-two it is close, and after sixty-four it is within what the sample can resolve. The general theory behind this — the factor $(1 + 2\cos\varepsilon)/3$ is the first of a sequence of such factors, one for each way the rotation group can act on functions on the sphere — is how Jeffrey Rosenthal computed in 1994 how fast random rotations mix in every dimension, and it is the continuous relative of how long a finite chain takes to forget its start. In three dimensions the slowest factor is the one shown, and it sets the pace.

What the histograms cannot settle #

Every histogram on this page is a finite sample, and a sample cannot prove that a recipe is uniform. Sixty thousand draws distinguish the three recipes at the top easily, because their errors are gross; they could not distinguish the true uniform rotation from a recipe wrong by a tenth of a per cent. The claim that normalising four Gaussians gives the uniform rotation is not supported by the figure — it is proved by the symmetry of the Gaussian, and the figure is a check that nothing went wrong between the argument and the arithmetic.

The same is true of the numbers measured rather than derived. The icosahedral grid’s worst miss of about forty-four degrees is the largest of thirty thousand random trials, which approaches the true worst case from below; the true value is a definite number, the covering radius of the group, and a sample can only suggest it. The tetrahedron’s ninety degrees is exact, because a quarter turn about an axis realises it. And the trace formula is exact for the average, but says nothing about how the whole distribution approaches uniform beyond its first moment.

Finally, every picture of the three-sphere here is a shadow: a coordinate’s histogram, an arrow’s path, a distance. The three-sphere itself cannot be drawn faithfully in three dimensions, and the figures use only what survives projection — distances between rotations and directions of arrows — because those are the quantities a body actually experiences.

Still open: the best way to spread a few rotations #

The regular solids give good grids of twelve, twenty-four and sixty rotations, and nothing better is known at those sizes. For most other numbers the best grid is not known. How should $N$ rotations be placed so that every rotation is as close as possible to one of them? It is the covering problem for the three-sphere with opposite points identified, and like its relatives on the ordinary sphere — where Thomson’s charges and Tammes’s circles have been searched for a century — it has proved answers only for a handful of small $N$ and good constructions, not proofs, beyond them.

Practical applications have settled for constructions that are provably close to even rather than provably best: grids built from the six hundred-cell, the four-dimensional relative of the icosahedron whose vertices are the hundred and twenty icosians, or from the Hopf fibration’s circles, refined a level at a time. What a uniformly random rotation offers instead is not evenness but honesty — a sample whose averages converge to the right answer at a known rate, which is the one thing a clever grid cannot promise for every quantity at once.