Curves on a Sphere – the Solution

Here’s the riddle and a solution. And here’s a solution fitting a probablog:

pick a random hemisphere!

All we need to prove now is that this solution works with positive probability, ergo it works.

Consider the circumference of a (uniformly) random hemisphere – it is a random great circle. Now, if this great circle does not intersect the curve, then it is contained in the hemisphere (or in its complement) and we’re done. So we want to analyze the random variable X that is the number of points of intersection of the curve and a random great circle. Specifically, we want to show that X=0 with positive probability.

Consider the expectation, \mathbb{E}(X). As always, the expectation is additive, therefore it depends only on the length of the curve and in a linear way. So, \mathbb{E}(X)=c \ell, where \ell is the length of the curve and c is some constant. To find out what the contant is, just take a curve for which calculating the expectation is easy – a great circle. The length of a great circle is \ell = 2 \pi and a uniformly random great circle intersects a great circle at exactely 2 points, almost surely. Therefore c=1/\pi.

Since our curve is shorter then a great circle, \mathbb{E}(X) < 2. However, X\neq 1, almost surely, so whenever X>0, it is at least 2. This means that the probability of X>0 cannot be 1, for then its expectation would be at least 2. Q.E.D.

This solution is not constructive at all (perhaps it could be derandomized?), but that’s also part of its strength, since it can be applied to all kinds of variations of the original riddle. Perhaps I’ll write another post about that. Note, however, that a simple constructive solution exists, and is given in Winkler’s book.

If you’re into (and have some experience with) probability, you probably recognized the connection to Buffon’s needle (not to mention his noodle).

Advertisements

~ by Ori on October 29, 2008.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: