5 ms·

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?

ColinWright 13y ago
> 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?
- MidsizeBlowfish 13y ago
  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.
- pfortuny 13y ago
  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.
  - psb217 13y ago
    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.
    - pfortuny 13y ago
      Right, symmetry! rotational symmetry, which is the one required for this problem. Thanks.
- gibybo 13y ago
  For a ball, can't I just randomly generate two angles (0-2pi)?
  - ColinWright 13y ago
    > For a ball, can't I just randomly generate > two angles (0-2pi)? Why would that be uniformly distributed?
  - mturmon 13y ago
    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.
    - gibybo 13y ago
      Ah, of course, thanks.
      - andrewcooke 13y ago
        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).
- deleted 13y ago
  [deleted]
- nothingspecial 13y ago
  Use a space-filling curve?
  - andrewcooke 13y ago
    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)
quchen 13y ago
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.
smoyer 13y ago
I think you meant 2*pi? Wouldn't that only fill the top half of the circle?
- pfortuny 13y ago
  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...
  - smoyer 13y ago
    "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".

ColinWright 13y ago

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

MidsizeBlowfish 13y ago
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.
pfortuny 13y ago
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.
- psb217 13y ago
  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.
  - pfortuny 13y ago
    Right, symmetry! rotational symmetry, which is the one required for this problem. Thanks.
gibybo 13y ago
For a ball, can't I just randomly generate two angles (0-2pi)?
- ColinWright 13y ago
  > For a ball, can't I just randomly generate > two angles (0-2pi)? Why would that be uniformly distributed?
- mturmon 13y ago
  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.
  - gibybo 13y ago
    Ah, of course, thanks.
    - andrewcooke 13y ago
      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).
deleted 13y ago
[deleted]
nothingspecial 13y ago
Use a space-filling curve?
- andrewcooke 13y ago
  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)

quchen 13y ago

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.

smoyer 13y ago

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

pfortuny 13y ago
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...
- smoyer 13y ago
  "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".