NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/theory/2358

Text File | 1992-11-08 | 2.8 KB | 66 lines

Newsgroups: comp.theory
Path: sparky!uunet!destroyer!sol.ctr.columbia.edu!The-Star.honeywell.com!umn.edu!thompson
From: [e-mail] (T. Scott Thompson)
Subject: Re: Uniform noise in d-sphere
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News Administration)
Nntp-Posting-Host: daphne.socsci.umn.edu
Reply-To: [e-mail]
Organization: Economics Department, University of Minnesota
References: <[e-mail]>
Date: Fri, 6 Nov 1992 17:26:57 GMT
Lines: 52

[e-mail] (Jacob Hirbawi) writes:

>In sci.math <[e-mail]>
>Michael Murphy <[e-mail]> writes:

>> I am trying to compute uniformly random noise inside a d-dimensional
>> sphere.  I have identified two ways of doing so:
>>
>> [...]

>A third method might be the following: use spherical coordinates and
>pick uniform random numbers for each of the coordinates with the appropriate
>ranges. In three dimensions this would be:

>   (1) radius  uniform over (0,d)
>   (2) angle1  uniform over (0,2 pi)
>   (3) angle2  uniform over (0,  pi)

>This seems to be *too* simple but since I can't think of any point within the
>sphere being more favored than any other point I would think that the
>distribution is in fact uniform.

This does _not_ produce a uniform distribution since (2) and (3) do
not generate a uniform (on the sphere) distribution of directions.
(In fact, this distribution is given as an example of a paradox of
conditional probability in Billingsley's text "Probability and
Measure.")  Intuitively this is because too much probability is
concentrated at the poles.  (Consider that the value of angle1 is
almost irrelevant if angle two is close to zero or pi.)

Also, (1) concentrates too much probability near the center of the
sphere.  (Consider that neither angle matters much if the radius is
close to zero.)

One can generate a uniform distribution using a different form of
polar coordiantes, however.  Let t_1,...,t_{d-1} be independent and
uniformly distributed on [0,pi].  Let x_i = cos(t_i).  Let x_d be a
square root of 1 - (x_1)^2 - ... - (x_{d-1})^2.  Flip a coin to decide
whether to take the positive or negative square root.  Then the vector
x = (x_1,...,x_d) is uniformly distributed on the sphere.

Now let z be uniform on [0,1] and let r = z^(1/d).  (i.e. downweight
small radiuses so that they get probability proportional to the
surface area of the corresponding sphere.)  Then r*x will be uniformly
distributed on the unit ball in R^d.

I don't know how efficient this is, but it clearly dominates rejection
methods for large values of d.
--
T. Scott Thompson              email:  [e-mail]
Department of Economics        phone:  [phone]
University of Minnesota        fax:    [phone]