Re: distribution of n point on the unit circle
- From: matt271829-news@xxxxxxxxxxx
- Date: 30 Dec 2006 18:07:48 -0800
Ralf Goertz wrote:
Hi,
I've been working on this problem for quite a while now and although it
didn't seem to be too difficult, I got stuck.
Consider n points distributed uniformly and independently on the unit
circle. What is the probability density function or the distribution
function for the smallest angle alpha such that all points are on a
sector of the unit circle with that opening angle.
For n=2 this is easy. alpha cannot be bigger than pi. Therefore
p.d.f.(alpha)=1/pi and d.f.(alpha)=alpha/pi.
In general, alpha must be smaller than or equal to 2pi*(n-1)/n. Using
Monte Carlo simulations I found out that for n=3 the p.d.f. is piecewise
linear with
3x/(2pi^2) for 0<=x<=pi
-9x/(2pi^2)+6/pi for pi<x<=4*pi/3
but I have no clue how to derive this analytically let alone how to
extend it to arbitrary n. Does anyone have an idea?
The exact general case looks messy, though quite possibly there will be
a nice smooth analytic approximation for larger n. To derive the n = 3
result that you found experimentally, you can proceed like this. Please
excuse my cavalier manipulation of the quantity d_alpha!
Consider a configuration where the smallest covering angle is alpha. We
immediately know that 0 <= alpha <= 4*pi/3. The largest gap is beta =
2*pi - alpha. Label the points 1, 2, 3 anticlockwise, where the largest
gap is between points 3 and 1. What is the probability of this
configuration? Imagine placing the points one by one.
Point 1 can lie anywhere, and the probability of this is 1.
If alpha <= beta (that is, alpha <= pi), then point 2 can lie anywhere
between point 1 and point 3 (anticlockwise from point 1 and clockwise
from point 3, that is). The probability of this is alpha/(2*pi).
However, if alpha > beta (i.e. alpha > pi) then the anticlockwise angle
of point 2 from point 1 must lie between alpha - beta and beta
(otherwise there would be an angle greater than beta in there). The
probability of this is (beta - (alpha - beta))/(2*pi) = (4*pi -
3*alpha)/(2*pi).
Point 3 has to be at anticlockwise angle alpha from point 1, so we'll
say the probability of it being there is d_alpha/(2*pi), where d_alpha
is conceptually an infinitesimal variation in angle.
We get the total probability by multiplying the probabilities of the
individual points being where they need to be. However, the points
could be placed in any order. There are 3! = 6 possible orders, so we
need to finally multiply the result by 6. This gives:
0 <= alpha <= pi
Probability = 1 * alpha/(2*pi) * d_alpha/(2*pi) * 6
pi < alpha <= 4*pi/3
Probability = 1 * (4*pi - 3*alpha)/(2*pi) * d_alpha/(2*pi) * 6
For the probability density function, which I'll denote P(alpha) we
conceptually need to, erm, divide the actual probability by d_alpha.
Doing this and simplifying gives
0 <= alpha <= pi
P(alpha) = 3*alpha/(2*pi^2)
pi < alpha <= 4*pi/3
P(alpha) = (12*pi - 9*alpha)/(2*pi^2)
which is what you had.
In theory you could extend this method to any n. However, the number of
cases you need to keep track of (depending on whether certain
quantities are greater or smaller than others) looks to explode, so it
all becomes nasty. There may be some recursive way (or totally
different approach) to make the calculation easier... not sure.
.
- Follow-Ups:
- Re: distribution of n point on the unit circle
- From: Ralf Goertz
- Re: distribution of n point on the unit circle
- References:
- distribution of n point on the unit circle
- From: Ralf Goertz
- distribution of n point on the unit circle
- Prev by Date: Re: Small set Theory:final version.
- Next by Date: Re: On finite reflection groups
- Previous by thread: distribution of n point on the unit circle
- Next by thread: Re: distribution of n point on the unit circle
- Index(es):
Relevant Pages
|
|
