Hacker News Reader

Comment by pfortuny | Hacker News Reader

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

Why is your construction 'uniform' on the circle?

    > 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?

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.

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.

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).

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)

Maybe I was too fast saying "easiest", arc-length works as well. My approach generalizes to arbitrary dimension though.

As for why it's uniform, recall that when X and Y are independent, then P(X and Y) = P(x)P(Y) ~ e^{-x^2-y^2} = e^{-r^2}, which is independent of the angle.

I think you meant 2*pi? Wouldn't that only fill the top half of the circle?

Yes I obviously did mean 2*pi but I always get confused with these two numbers...

Not that it matters much, being a lecturer in Mathematics...

"Not that it matters much, being a lecturer in Mathematics..."

Trigonometry was always my favorite Math. But my second calculus class in college was taught by a brilliant (I later found out) native-Hindi speaker. His English was good enough but it took me three weeks to correctly write down the fractions he was quoting as "three under two".

Reply on news.ycombinator.com