10 October 2007

Probabilities on the circle

At my department's tea yesterday, the following problem came up: Given three random points on a circle, what is the probability that they lie in the same semicircle?

(Incidentally, why do we insist on calling it "tea" when most of the people there drink coffee? I suspect British influence at some point.)

First, by "random" I mean "uniformly at random, with respect to angle or arc length"; a classic problem in this sort of thing is to determine the probability that the length of a random chord of a circle is larger than the length of a side of an equilateral triangle inscribed in the circle. This is Bertrand's paradox. A chord is uniquely determined by its midpoint, and the result is different if you choose a chord by picking its midpoint uniformly at random from the interior of the circle than by choosing its endpoints uniformly at random from the boundary. I feel this is "more ambiguous" in the two-point case than in the three-point case, because there's a nice way to associate a single point in the interior with two points on the boundary.

The answer to my problem is 3/4.

Consider the circle as the interval [0, 1] with the endpoints identified. Then the problem is one about choosing triplets of real numbers (x1, x2, x3) in that interval, where these numbers are chosen uniformly at random and independently. Replacing these with (0, y2, y3) = (0, x2-x1, x3 - x1) corresponds to rotating the circle by x1 and therefore doesn't change the probability of our event. Finally, if either of y2 and y3 are between 1/2 and 1, subtract 1 from it; now we're just viewing the circle as the interval [-1/2, 1/2] (centered on the first point) instead of [0, 1].

So now our event is just that |y3 - y2| ≤ 1/2. If y3 and y2 have the same sign, this is obviously true, and we can take the semicircle [0, 1/2] or [-1/2, 0]. If y3 and y2 have different signs, but |y3 - y2| ≤ 1/2, then some interval of size 1/2 containing y2 and y3. But if |y2 - y3| ≤ 1/2, -- for example, if y2 = 0.3, y3 = -0.3 -- then we lose. Any interval of width one-half containing both of those -- say the union of [0.25, 0.5] and [-0.5, -0.25], recalling that 0.5 and -0.5 are identified -- won't contain zero.

And the probability that two random points in a unit interval are within distance 1/2 of each other is just 3/4.

Alternatively, if we're trying to find this interval, one of the points is at the "counterclockwise" end of the interval. So fix which point is counterclockwisemost in the interval, there are three ways to do that. Then the other two points must be within 180 degrees clockwise from that point; the probability of that is 1/4. The "most counterclockwise" point is unique, so we can just add up the three probabilities to get 3/4. In general, if "semicircle" is replaced with some section of the circle making up a proportion c of the whole, where c ≤ 1/2, the probability that three randomly chosen points lie in an interval of that size is 3c2.


Anonymous said...

I think the easiest way to see this is with some simple diagrams and some conditional probability.

Since all three points are placed independently, let's imagine that two points are placed first. The distance between these points is uniformly drawn from [0, .5] circumference lengths. Ignore the endpoints for a moment and consider the (0, .5) cases: draw radii from the endpoints to the center. The first two points and radii through them form a wedge, varying in size from 0 to half the circle.

Now extend those radii to be diameters of the circle. It's easy to see that the points that are not within a semicircle of the original two points are the points that fall into the symmetrically opposite wedge. Anything within the larger portion of arc bounded by the diameters drawn from the first two points is within a semicircle of the first two points. The portion excluded is an arc that's symmetrically opposite, and of the same size as the distance between the first two points. This arc size will vary uniformly between 0 and 1/2 circumferences.

The conditional probability that the third point will fall in that arc therefore varies uniformly between 0 and 1/2. The expectation of this conditional probability is therefore 1/4. Since the placement of the three points is independent, this conditional probability that the third point does not fall into the same semicircle as the first two, based on the distance between the first two must be the same as the actual probability that the three points will not be in the same semicircle. We are interested in 1 - this probability, or the probability that all three points are within the same semicircle, which is, of course, 3/4, just as you said.

Finally, at the two endpoints of the distance between the first two points (which occur with probability zero), the portion of the circle exluded is either zero or 1/2, which averages to 1/4, just as the interior points do.

Anonymous said...

i see your explanations - but somehow i am confused.

please temme if this logic is sensible?

ans = prob(angle subtended by two points = x) * prob(third point is inside x)
= x/pi * x/2pi
integral of above from 0-pi

= pi/6

Anonymous said...

Anonymous, close but wrong.

The ans. = 1 - (exp(prob.(third point is inside x)).

The prob that the angle = x is the same for every value of x: 0. The probability for the angle between the first two points is uniform. You gave the probability that the angle is less than or equal to x, which is x/pi.

The expectation of the probability of the third point being in that arc is simply the integral of (1/pi) * (x/2pi) from 0 to pi.

The integral is (1/pi) * (x^2/4pi). Evaluated at the endpoints this gives 1/4. One minus this expecation = 3/4.

Anonymous said...

Please tell me what's wrong with this argument:

The first and second points are free to be anywhere on the circle.

Whether or not the three points lie in a semicircle depends on the placement of the third point. The proprtion of the circumference where this will happen will depend on the acute angle (theta) between between the first two points.

For example if 1st point was at 0 degrees and the second at 180. Then the three points will all lie in a semicrcle with certainty.

If both points lie at 0 degrees, again they all lie in semicirlce with certainty.

If 1st point lies at 0 degrees and second at 90, then the three points will lie in the same semicircle with probability 3/4.

As the theta changes from 0 to 90, the probability decreases linearly from 1 to 3/4. As theta increases from 90 to 180 the probability increases from 3/4 back to 1.

The probability is therefore 7/8.

(Much easier to explain with diagrams)


Anonymous said...

Scrap that last argument. I've just realised what i was doing wrong. thanks anyway

sam said...

Sorry guys. I am not so good in maths.

Wide Circles

Anonymous said...

This is very important site for math’s students. Math is my favorite subject so I like this site very much.

Anonymous said...

Interesting blog as for me. I'd like to read something more concerning this matter. Thanx for sharing this info.
Sexy Lady
English escort

Brad said...

Was thinking about dropping n points on circle, and it occurred to me that for any successful outcome, there exists exactly one of the points where a clockwise (WLOG) semi-circle contains all n points.

We can then solve the trivial problem of finding the probability that the next n-1 points all fall in the clockwise semi-circle determined by the first point.

1/2^(n-1) is this answer.

Essentially we're realizing that the order of dropping doesn't matter, so we're just looking at the mass of the set of all successful outcomes, and realizing that we've counted 1/n of them. So, the total probability is just n/2^(n-1).

This avoids conditional probability. We instead find a clever way to identify the set of outcomes in question, such that computing the probabilistic measure of each is trivial.