Solution to distance between random points from a sphere

So I asked on Sunday the following question: pick two points on a unit sphere uniformly at random. What is the expected distance between them?

Without loss of generality we can fix one of the points to be (1, 0, 0). The other will be chosen uniformly at random and will be (X, Y, Z). The distance between the two points is therefore

√((1-X)² + Y² + Z²)

which does not look all that pleasant. But the point is on the sphere! So X² + Y² + Z² = 1, and this can be rewritten as

√((1-X)² + 1 - X²)

or after some simplification

√(2-2X).

But by a theorem of Archimedes (Wolfram Alpha calls it Archimedes' Hat-Box Theorem but I don't know if this name is standard), X is uniformly distributed on (-1, 1). Let U = 2-2X; U is uniformly distributed on (0, 4). The expectation of √(U) is therefore

∫₀⁴ (1/4) u^1/2 du

and integrating gives 4^3/2/6 = 8/6 = 4/3.

(The commenter "inverno" got this.)

Of course it's not hard to simulate this in, say, R, if you know that the distribution of three independent standard normals is spherically symmetric, and so one way to simulate a random point on a sphere is to take a vector of three standard normals and normalize it to have unit length. This code does that:

xx1=rnorm(10^6,0,1); yy1=rnorm(10^6,0,1); zz1=rnorm(10^6,0,1)
d1=radic(xx1^2+yy1^2+zz1^2)
x1=xx1/d1;y1=yy1/d1;z1=zz1/d1;
xx2=rnorm(10^6,0,1); yy2=rnorm(10^6,0,1); zz2=rnorm(10^6,0,1)
d2=radic(xx2^2+yy2^2+zz2^2)
x2=xx2/d2;y2=yy2/d2;z2=zz2/d2;
d=radic((x1-x2)^2+(y1-y2)^2+(z1-z2)^2);

and then the output of mean(d), which contains the distances, is 1.333659; the histogram of the distances d is a right triangle. (The code doesn't make the assumption that one point is (1, 0, 0); that's a massive simplification if you want to do the problem analytically, but not nearly as important in simulation.)

A geometric probability problem

Here's a cute problem (from Robert M. Young, Excursions in Calculus, p. 244): "What is the average straight line distance between two points on a sphere of radius 1?"

(Answer to follow.)

If any of my students are reading this: no, this should not be interpreted as a hint to what will be on the final exam.

How to draw Voronoi diagrams

How to draw Voronoi diagrams by hand. Just to remind you, a Voronoi diagram is associated with a set of points x₁, ..., x_n in the plane; for each point, the cell containing it is the set of points in the plane that are closer to x_i than to any other x_j. I've spent a fair amount of time doodling Voronoi diagrams in boring places, so this is interesting. Apparently they also run into the problem that sometimes it's hard to tell which cells will border which other cells.

Yes, I know, it's been six months since I posted. As you can see, I'm still alive, and I made it through my first semester here at Berkeley. I live in North Oakland, closer to downtown Berkeley than to downtown Oakland, and I find myself describing where I live as "the part of Oakland that's really more Berkeley-ish". More formally, I'm in downtown Berkeley's Voronoi cell, not downtown Oakland's.

(VIa Proof Math is Beautiful.)

Brownies and space-filling curves

The Baker's Edge brownie pans, which are pans constructed in such a way that everybody gets an edge piece and nobody gets a piece from the middle, remind me of space-filling curves.

The isoperimetric inequality suggests that the only way to do the reverse -- to have pans where nearly everybody gets the middle and nearly nobody gets the edge -- is to have really big pans.

Which two states are closest together?

Fix two sets X and Y in the plane, each the interior of a curve, such that their closures don't intersect. How would one go about finding points x in X and y in Y such that the distance between X and Y is minimal?

Furthermore, say we have a bunch of sets X₁, ..., X_n, each the interior of a curve, with nonintersecting closures. Let d(i,j) be the minimal distance between X_i and X_j. How can we find the minimal nonzero d(i,j), that is, the minimal distance between any two sets with nonintersecting closures? (In particular, there should be a faster algorithm than computing all the d(i,j). I suspect O(n log n) of the d(i,j) need to be computed although I have no idea why I'm saying this.)

The problem that inspired this is the following geographic one. What two states in the US that don't border each other are closest together? I think I know the answer; I'll post about that later.

Probabilistic fun with the n-sphere

On reddit: a link to the old chestnut that high-dimensional spheres are weird. If you consider the volume of the unit ball in Rⁿ as a function of n, it increases up to n=5 and then decreases. The volume is π^n/2/((n/2)!). (By the way, I generally use the factorial notation, not the Γ notation, even when the argument isn't an integer.)

But I hear you complaining that it doesn't make sense to compare volumes in different dimensions! Fair enough. Compare the volume of the unit ball in Rⁿ to the cube circumscribing it, which has volume 2ⁿ. Then the portion of the cube which is inside the ball is f(n) = π^n/2/((n/2)! 2ⁿ). This is rapidly decreasing with n. For n = 2, it's π/4 -- the volume of the unit disc is π, and it can be inscribed in a square of area 4. In n = 3, the unit ball has volume 4π/3 and it's inscribed in a cube of size 8, so we get f(3) = π/6. But f(n) decreases superexponentially. f(10) is about 0.0025, f(20) is about 25 in a billion.

I was surprised that it decayed that quickly -- I'd never bothered to work it out. But if you think about it probabilistically, it kind of makes sense. Namely, a random point in the unit n-cube can be identified with its coordinates (x₁, x₂, ..., x_n). It's in the unit n-sphere if and only if the sum of the squares of those coordinates is less than 1. Let y_i = x_i² -- then y_i has mean 1/3 and variance 4/45. (That's calculus.) So the sum of the squares of the coordinates is a sum of n such independent random variables, and is thus itself a random variable with mean n/3 and variance 4n/45 -- it's no surprise most of its mass is at n > 1. One could probably use large deviation inequalities to quantify this, but come on, it's 11 at night and I have real work to do.

Tetrahedra with arbitrary numbers of faces

While reading a paper (citation omitted to protect the "guilty"), I came across a reference to an "n-dimensional tetrahedron", meaning the subset of Rⁿ given by

x₁, ..., x_n ≥ 0 and x₁ w₁ + ... x_n w_n ≤ τ

for positive constants w₁,..., w_n and τ.

Of course this is an n-simplex. But calling it a "tetrahedron" is etymologically incorrect -- that means "four faces", while an n-simplex has n+1 faces. This probably occurs because most of us tend to visualize in three dimensions, not in arbitrary high-dimensional spaces.

I'm not saying that "tetrahedron" shouldn't be used here -- I'm just pointing out an interesting linguistic phenomenon.

McMullen on the geometry of 3-manifolds

The Geometry of 3-Manifolds, a lecture by Curt McMullen. This is one of the Science Center Research Lectures; in which Harvard professors talk about their research to the interested public; the series doesn't appear to have a web page, but here's a list of videos available online in that series; these include Benedict Gross and William Stein on solving cubic equations. There are non-mathematical things too, but this is at least nominally a math blog, so I won't go there.

McCullen apparently also gave this lecture at the 2008 AAAS meeting in Boston, and has a couple other video lectures available online.

And now I want a do(ugh)hnut-shaped globe with just North and South America on it. This is a fanciful example of what an "armchair Magellan" might suspect the world looked like if humans had reached the North and South poles starting from somewhere in the Americas but had never crossed the Atlantic or Pacific; they might suspect that the cold area to the north and the cold area to the south are actually the same. McMullen uses to illustrate that tori and spheres are not the same, since loops on the sphere are contractible but loops on the torus are not. The lecture, which leads up to telling the story of the Poincaré conjecture, begins by using this as an example of how topology can distinguish between surfaces.

Finally, here's an interesting story, which may be well-known to some people but wasn't to me: Wolfgang Haken, one of the provers of the Four-Color Theorem, may have intended that (famous, computer-assisted) proof to be a "trial balloon" for a brute-force proof of the Poincare conjecture.

The geometry of a game

From 360: Shinju, a geometrical game. You're given an arrangement of shells in some of the squares of a square grid. One of the shells hides a pearl. Your goal is to find it, opening at most four shells. When you open a shell, it either contains the pearl, or a number. That number is the distance to the pearl, in the (T)chebyshev distance.

There's a nice little result hiding here:
Problem 1: Given any arrangement of shells, prove that it is possible to find the shell in four clicks.
Since you always get four clicks (at least as long as I played), the game becomes trivial if you can find a constructive proof of that fact. (If you're the sort of person that likes to rack up points in video games, though, I think you get more points if you don't use all your clicks -- so how do you set things up so that you're likely to solve the puzzle in less than four clicks?)

Problem 2: Generalize (to higher dimensions, different metrics, etc.)

The eyeballing game

Check out the eyeballing game. You're asked to "eyeball" various geometric constructions -- the perpendicular to a given segment, the center of a given circle, the bisector of a given angle, and so on.

I'm kind of curious which sort of mathematicians do best on this. I have very little reason to draw geometrically accurate pictures in my work. Although to be honest, even people who do geometry don't have to draw really accurate pictures; I suspect it's the engineers who would be best at this.

(via reddit.)

Who knew high school geometry was good for something?

Groundskeepers Display Artistry on the Diamond, September 30 (?) New York Times. David Mellor, the current head groundskeeper at Fenway Park, is the one who started the trend of mowing the grass in such a way as to create interesting-looking patterns; apparently he first did it in order to camouflage some damaged grass in Milwaukee in the early 90s. Roughly speaking, the mowing action bends the grass in one direction or another, creating contrasts of light and dark; you can see a similar effect when you vacuum your carpet. (I really mean "you" here. I can't; I have wood floors.)

And we're told that "High-school geometry classes visit [Mellor] at Fenway Park to study ways that an odd-shaped field can be divided and subdivided by straight lines and sharp angles."

The probability of making a putt

I don't know much about golf. Basically I know the following things:

• you try to get the ball in the hole;
• scoring works by counting the number of times you hit the ball with the club; lower scores are better;
• "par" is really good, not average.

Anyway, Tiger Woods won the U. S. Open, and Ian Ayres, guest-blogging at Freakonomics asks why golf commentators don't give the probability that a putt from distance x will go in. Commentators in just about every other sport do; Ayres' example is free-throw percentage in basketball, mine would have been batting average in baseball.

Ayres then gives a plot showing the success rate of golf putts as a function of difference from the hole, taken from this paper. Not all that surprisingly, the probability of making a putt from distance x scales like 1/x; essentially you can assume that the angular error in putting doesn't change as the distance of the putt increases. But the apparent size of the target is smaller at longer distances. Basically, from twice as far away the hole looks half as big.

It turns out that's what Andrew Gelman and Deborah Nolan thought, too. (Andrew Gelman and Deborah Nolan, "A Probability Model For Golf Putting", Teaching Statistics, Volume 24, Number 3, Autumn 2002. (This is the source for Ayres' figure.)) Their actual model is a bit more complicated, because they actually do the trigonometry correctly, and they assume that errors in putting are normally distributed while I'm assuming they're uniform. Read it, it's two and a half pages.) This fixes the problem that my crude model would have. At five feet, pros make 59 percent of their putts; thus it would predict that at two and a half feet, they make 118 percent!

The result of Gelman and Nolan is that the probability of the success of a putt from distance x is

where R, r are the radii of the ball and the hole; 2R = 4.25 inches and 2r = 1.68 inches. σ is the standard deviation of the angular error of a shot (in radians), which can be found from empirical data to be 0.026 (about 1.5 degrees). Φ is the standard normal distribution.

If you assume that x is large enough that (R-r)/x is small enough that we can make the small angle approximation arcsin x ≈ x, then this becomes 2Φ((R-r)/(σ x)) - 1. But Φ(z) is linear near z = 0, with Φ(0) = 1/2 and Φ'(0) = 1/(2π)^1/2. So the probability of succeeding from distance x, for large x, is approximately

R-r is 1.285 inches, or .10708 feet.

So we get that the probability of making a putt from distance x, in the limit of large x, is about (3.29 feet)/x, although this is really only a good approximation above x = 6 feet or so. This has the advantage of being easy to remember -- well, somewhat easy, because you still have to remember the constant. But if you measure in meters, there are 3.28 feet in a meter, so the constant is basically 1; clearly golf should be done in metric.

Incidentally, I think it's a good idea to put citations that at least include the author and title in blog posts, even though strictly speaking they're not necessary as pointers if a link is provided. Why? Because that makes it more likely that people who Google the paper's title or authors find the people talking about it. (Occasionally I've recieved comments from self-Googling authors.)

The napkin ring problem

Keith Devlin writes about The Napkin Ring Problem in his column this month. The problem is the following: consider a sphere with a cylindrical hole drilled out from the center. What is the volume of the resulting solid? At first one thinks that this should depend on the radius of the sphere and the radius of the hole, but it turns out to depend only on the height of the resulting solid; Devlin gives the computation. As it turns out, the volume is 4πh³/3, where h is the half-height of the resulting solid; this is the volume of a sphere of radius h. In fact, the corresponding cross-sectional areas of a "napkin ring" of half-height h and a sphere of radius h are the same, as one can see without calculus; by Cavalieri's principle the volumes are equal.

This is a problem that is usually assigned in our calculus courses when we get to solids of revolution. The way that it's phrased in Stewart's calculus text (which I don't have at hand right now) is in two parts. The first part refers to two such napkin rings -- call them A and B -- and says that napkin ring A comes from a larger-radius sphere than B but also has a larger-radius hole; the student is asked to guess whether A or B has greater volume.

At this point the students invariably ask "what if my guess is wrong?" I laugh and tell them that it doesn't matter; the point is that they should try to think about it for a moment before they plunge into the calculations.

The second part, if I remember correctly (my officemate has the book, so I'll check this tomorrow) asks the students to express the volume as a function of the two radii and the height; often, even if they manage to get the correct answer (which is a bit tricky) they do not seem surprised by this fact, which I was when I first saw it. Then again, it is often difficult to judge whether students are surprised by some statement made in class or on the homework; it's not the sort of thing your average college student is going to let show! (Penn students taking the calculus courses are mostly pre-professional, either in the engineering or business schools; I wonder if the future mathematicians or even the future "pure" scientists would react differently.)

(Incidentally, it is always amusing to look at reviews of textbooks at amazon.com; I often wonder how many of them are written by students who are disgruntled about their class and want somewhere to take it out.)

Approximating the length of an ellipse

Here's a question that occurred to me this morning -- what's the circumference (is this word appropriate here?) of an ellipse with semimajor axis 1+ε and semiminor axis 1? (ε is, of course, small. It could be negative, however.)

Of course, this is an elliptic integral. But I don't know much about elliptic integrals, and besides what good is that information? It doesn't give me a number. (I didn't actually need to know this for anything, but somehow the knowledge that the answer is, say, 2π+ε (it's not) is more satisfying than the fact that it can be written in terms of some special function that I don't know that well.

It turns out the answer is (2+ε)π.

Here's a sketch of a proof. This ellipse can be parametrized by x = (1+ε) cos t, y = sin t, with t varying from 0 to 2π. So the length is

Expand, and let ε² = 0, to get

which simplifies to (recalling cos² t + sin² t = 1)

Now, since ε is "small", 2ε cos² t is also "small". In general, for small h, (1+h)^1/2 ~ 1 + (h/2); thus this is approximately

and now we recall that cos² t has average value 1/2. So this is (2+ε)π, which is the answer.

More formally, if f(a) is the length of an ellipse with axis lengths 1 and a, this shows (modulo a couple leaps of faith) that f'(1) = π -- this can easily be checked with a computer algebra system, or if you actually know more about elliptic integrals than I do. This has the nice interpretation that if the lengths of the two axes of an ellipse are close to each other, the length of the ellipse is just π times the mean of the axis lengths -- which is true for a circle, where it just says that the circumference of a circle is π times its diameter. The Taylor series for the elliptic integral which gives the length is, according to Maple,

and from numerical data, for, say, ε = 0.1, this method predicts an ellipse length of 2.1π = 6.5973; the actual length is 6.6011. Even for ε = 0.5 the error's only about one percent (7.85 versus 7.93).

The real question that I started out with, though, still isn't answered -- is there some nice geometric way to see this?

A mathematician goes to the post office

There's a pretty standard theorem that one proves at the beginning of, say, a differential geometry course -- that any (n-1)-dimensional manifold embedded in n-dimensional Euclidean space is locally the graph of some function. (To any geometers are reading this, I apologize if I haven't stated this correctly.)

This morning I had to go to the post office to pick up a piece of certified mail. I live on one side of a large set of railroad tracks; the post office is about a mile away on the other side of the tracks. I generally don't go past the tracks, because very little that interests me is there, and I hadn't looked at a map before setting out. It's important to know where the tracks are when walking around in that neighborhood, because there are a lot of streets that exist on both sides of the tracks but are interrupted by them. The street on which the post office is, Florence Avenue (links goes to Google satellite imagery) may be such a street; it exists on both sides of the tracks, and doesn't cross over the tracks. It might cross under; Google Maps won't tell me, and I'm not curious enough to head out there again and look. So the scheme of "follow the street with the same name" doesn't always work.

I knew the tracks run basically from northwest to southeast. (For those who know where I live, or who are looking at the map I linked to: all directions are "nominal", i. e. by "west" I mean "the direction in which the street numbers get higher".) At one point on the way back I crossed a bridge and I was wondering "could that have been the tracks I just walked over?" Then I thought "hmm... I'm further north than I was when I crossed the tracks heading to the post office, so the tracks must be further west here."

Why must they? Because the tracks are basically a one-dimensional manifold embedded in two-dimensional Euclidean space. So locally there's a function mapping east-west streets to north-south streets that gives the position of the tracks. Everyone knows this intuitively. If you asked someone who knows that neighborhood well "Where does [insert street here] cross the tracks?" you'd get an answer, even if they're totally ignorant of geometry.

Mathematica est omnis divisa in partes tres

That is, "all mathematics is divided into three parts". I don't actually know Latin. I fear I may have said that Mathematica, the software, is divided into three parts.

This occurred to me this morning, when I saw the following three-fold characterization of the conic sections, which may amuse. (I'm basically copying this from Leila Schneps' lecture notes.)

Conic sections can be defined geometrically, analytically, or algebraically.

• Geometrically: a conic section is the curve obtained when a plane intersects with a cone. The conic section is an ellipse, parabola, or hyperbola according to whether the plane is less steeply slanted, exactly as steeply slanted, or more steeply slanted than the cone's generating line.


• Analytically: given a point F the focus and a line D the directrix, a conic section is the locus of points P such that d(P,F)/d(P,D) is a constant e, the eccentricity. The conic section is an ellipse, parabola, or hyperbola according to whether the eccentricity is less than, equal to, or greater than 1.


• Algebraically: a conic section is the solution set of Ax² + Bxy + Cy² + Dx + Ey + F = 0. The conic section is an ellipse, parabola, or hyperbola according to whether B² - 4AC, the discriminant, is negative, zero, or positive.

The three definitions are equivalent.

It's fitting that the quote is in Latin, because I don't know Latin, and I also don't believe that mathematics is divided into only these three parts. In particular, you all know that I like probability and combinatorics, which don't naturally fit into this tripartite scheme. But it's a nice division of what one might call "classical" mathematics (it's roughly the content of the semi-standard first-year graduate mathematics curriculum, for example).

Calling the second definition "analytic" is a bit of a stretch, though.

Nineteen proofs of Euler's formula

Nineteen proofs of Euler's Formula, from The Geometry Junkyard. (This is the one that says that if V, E, and F are the number of vertices, edges, and faces of a polyhedron, then V-E+F=2.)

This is something of an embarrassment of riches; I want one for my class tomorrow, because we're talking about regular polyhedra, and to talk about that without mentioning Euler's formula would be remiss.

I'll probably give "Proof #8: Sum of angles" from the page, which sums up the various angles involved in a drawing of the graph corresponding to a polyhedron, or the proof that Wikipedia attributes to Cauchy, which triangulates that graph (not changing V-E+F) and then removes edges one or two at a time (still not changing V-E+F). These seem the most accessible. (They're also the ones I managed to struggle in the general direction of while walking to the coffee house a couple hours ago.)

If I wanted to scare the hell out of my students (this class has no prerequisites), I'd give the "binary homology" proof.

A sighting of mathematics on Jeopardy!

Today's Final Jeopardy question (alas, I didn't write down the category, but it was something like "brands"):
"Each unit in this brand, introduced in 1968, is a hyperbolic paraboloid, & they fir together for perfect storage."

The answer: What are Pringles? Two of the three contestants got it right; the third answered "What is Orville popcorn?"

I wonder if the inclusion of the "hyperbolic paraboloid" makes it harder or easier. I think it made it harder for me, because I got confused and was picturing a hyperboloid of one sheet instead. Fortunately I realized that those wouldn't fit together in any reasonable way, at least if they were all the same size. I don't know the background of the contestants tonight; I suspect most people, even most people who know enough random things to appear on Jeopardy!, would probably just filter out those words, or at best replace them with "funny shape" (because they've heard of hyperbolas and parabolas). "Funny shape" is probably the right way to think of it here; the fact that Pringles are oddly shaped is a much more salient fact about them than the precise shape, unless of course you work in a Pringle factory.

(Before you ask: No, I've never tried out for Jeopardy. Yes, I probably should.)

How much land is in the tropics?

In Tropics widen, fringe areas drier, experts say, from the Associated Press, I found the following quote:

Geographically, the tropical region is a wide swath around Earth's middle stretching from the Tropic of Cancer, just south of Miami, to the Tropic of Capricorn, which cuts Australia almost in half. It's about one-quarter of the globe and generally thought of as hot, steamy and damp, but it also has areas of brutal desert.

In fact, the tropics make up about two-fifths of the globe. To be more precise, I mean that about two-fifths of the total area of the surface of the earth is between the two tropics. The tropics are at latitudes +23.5 and -23.5 degrees (I'll use + and - for north and south here.) So it's easy to see where the "one-quarter" figure might come from -- the tropics span a total of 47 degrees of latitude, out of the full range of 180, and 47/180 is essentially 1/4.

But there's an interesting fact about the surface area of a sphere. Take a sphere of radius r. Cut it with two parallel planes of distance h apart. Then the area of your slice will be h/(2r) times the surface area of the sphere, or 2πrh, regardless of the way the sphere is cut; notice that this is also the surface area of a cylinder of height h and radius r. I saw this demonstrated once, when I first saw this fact in a calculus class, by cutting a spherical loaf of bread into slices of equal thickness; the slices get varying amounts of the interior of the bread but all get the same amount of crust.

The thickness of the slice in question, for the tropics, is (2 sin(23.5^o))r, where r is the radius of the earth. Thus this slice makes up sin(23.5^o) = 0.398 of the earth, which is just under two-fifths. I knew from the moment I read this fact that one-quarter was an underestimate, but I suspected that perhaps it was more accurate than, say, "one-third". But it's not.

(The actual point of the article is not that the tropics make up one-fourth, or two-fifths, or whatever fraction of the earth, but that they are "widening"; this uses an atmospheric definition of the tropics which is different from the astronomical one implied by the quote above.)

The "tenth dimension"

Imagining the tenth dimension, by Rob Braynton. The place where I originally read about this link thought it was kind of cringeworthy, but I didn't agree at first; it's not a bad popular explanation at the beginning...

But at one point the voice claims that quantum wavefunctions exist in five dimensions, invoking some. This isn't reasonable; the space of wavefunctions is a hell of a lot larger than one-dimensional. Sometime around here I stopped paying too much attention. And all dimensions above four, in this explanation, seem to arise in the same way. Why stop at ten? (In the video, somehow seven-dimensional space gets collapsed to a single point. I won't pretend to explain it. Then ten is seven plus three.)

While I'm on the subject, it's kind of annoying that the narrator says "the tenth dimension" as if you can put "the dimensions" in order. Space may be ten dimensional, but there's no canonical ordering of the elements. "Because we live from moment to moment in the third dimension" -- no! We live in three dimensions. Insofar as the third dimension is anything, it's a single dimension, so this nomenclature seems to insist we live in one-dimensional space. Dimension is a number (usually an integer) which is an invariant of a space; there's not some canonical set of three things associated with our three-dimensional space. (Yes, a basis for our space has three dimensions, but there's no canonical choice of basis.)

And don't even get me started about science fiction that talks about "creatures from the fourth dimension". "Four-dimensional creatures" are at least mathematically acceptable.

In the end he's trying to sell a book, and there's a blog; in one post there's a list of where the ten dimensions arise from but it feels like the methodology (if one could call it that) could justify any particular number of dimensions.