Hacker News Reader

Comment by ColinWright | Hacker News Reader

    > Why is your construction 'uniform' on the circle?

That's a very good question, and the sort of thing that would need to be in a comment somewhere. The answer is that the bi-normal distribution is rotationally symmetrical, a fact that is not immediately obvious.

    > I'd rather take a random uniform distribution
    > from 0 to pi and take it as the arc-length.

That's a good solution for the simple one-dimensional circle in two dimensional space, but does not generalize to higher dimensions. The technique of drawing points from a normal distribution and normalizing works for any dimension. That's the usual follow up question when the candidate gives your (very good for the given question) solution.

How would you generate points distributed uniformly on the surface of a three dimensional ball?

View on HN

Poster here, I actually had considered adding both of these methods to the end of the post, but decided to keep it focused on the problem itself.

edit

Maybe I'll write about them in a follow-up post.

For a ball, can't I just randomly generate two angles (0-2pi)?

  > For a ball, can't I just randomly generate
  > two angles (0-2pi)?

Why would that be uniformly distributed?

No, because the two angles can't easily be combined to make the resulting point uniform on the sphere.

For instance, if you call one of the angles "latitude", and one "longitude", then you will get too many samples near the poles -- think about how the lines of constant longitude start out widely spaced on the equator, but then converge at the poles. This would cause points to pile up at the poles.

Your proposal hits on the nub of why this problem is hard. It is, in general, hard to generate a bunch of non-independent random variables with a prescribed distribution. In this case, it's the angles that are not independent.

Ah, of course, thanks.

you can use longitude and z (height "up the axis") (it's uniform because a ring of thickness dz at height z is of area 2pi * z * cos(lat) * dz/cos(lat) (so the latitude cancels nicely - it's a trick used for equal area map projections).

Yes, I see and understand. Thanks for the info.

It is obvious if you think of it (exp(x1^2+...+xn^2) is symmetric on all the variables). Yep, understood.

That's not quite what "rotational symmetry" means in this context. A collection of random variables independently distributed according to identical "doubly-rectified" exponential distributions would also be symmetric under variable interchange.

However, this represents invariance only under sequences of axis-aligned rotations that are multiples of pi/2. The joint distribution of a collection of independently and identically normally-distributed random variables is invariant under arbitrary rotations, which is a much stronger form of invariance.

E.g., if you drew [x1...xn] from a distribution like exp(-|x1|-|x2|-...-|xn|), which is invariant with respect to variable interchange, and normalized to unit length, the resulting distribution would be markedly non-uniform over the surface of the n-dimensional unit hyper-sphere.

In fact, the differences in the symmetries of these distributions are crucial to the relative behaviors of L1 and L2 regularizers in machine learning. These differences have significant practical, and not merely theoretical consequences.

Right, symmetry! rotational symmetry, which is the one required for this problem. Thanks.

Use a space-filling curve?

this a a cute idea, but i don't know of one (on the surface of a sphere). do you? also, are all space-filling curves uniformly dense in the limit? (presumably it depends on how you transform from a plane to a sphere, and if you get that right, you can just use it directly)

Reply on news.ycombinator.com