8 ms·
For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the
by quchen 13y ago
For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the vector. (And two independent Gaussian variables can be easily sampled using the Box-Muller transformation.)
- ronaldx 13y agoor generate a (uniform) random direction from the centre of the circle.
- pfortuny 13y agoI'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 agoPoster 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 agoYes, 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 agoThat'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 agoRight, symmetry! rotational symmetry, which is the one required for this problem. Thanks.
- gibybo 13y agoFor 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 agoNo, 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 agoAh, of course, thanks.
- andrewcooke 13y agoyou 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 agoUse a space-filling curve?
- andrewcooke 13y agothis 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 agoMaybe 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 agoI think you meant 2*pi? Wouldn't that only fill the top half of the circle?
- pfortuny 13y agoYes 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".
- alxbrun 13y agoHow do you prove than the component-wise normal distributions, once normalized, become uniform on the circle? UPDATE - OK, got it in some comments that were posted while I was posting this one!
- mturmon 13y agoI have to disagree with this. It would easier conceptually and faster computationally to use rejection sampling: do { x = uniform() y = uniform() r = x*x + y*y } while (r > 1) x = x/sqrt(r) y = y/sqrt(r) This does generalize to higher dimensions d, although as d gets large, you waste more samples. For spheres embedded in a handful of dimensions, it would still be fine, and it avoids all the transcendental functions associated with Normal variates. It's due to Marsaglia (1972).
- ColinWright 13y agoIt's simple, clean, clear, and works well in low dimensions. I regularly work in a few thousand dimensions, and it doesn't work at all because the volume of the sphere is too small. These are great discussions to have with a candidate. If they already know these things then you can see if they understand why, and if they don't already know these things, you can see how they react to learning new and rather esoteric stuff that turns out to be useful.
- RyanZAG 13y agoIntriguing, what do you use something like this random multi dimensional sphere for?
- ColinWright 13y agoChoosing a random direction uniformly for various varieties of hill-climbing optimization algorithms. The uniformity is necessary for the analysis of termination conditions.
- cmsmith 13y agoAlternatively, just use the method in the article (scale the uniform random distribution) and if your point is more than 1u away from the origin then throw it out and try again. You would throw out 36% of the points, but you might get that back from not using trig functions.
- deleted 13y ago[deleted]
- noAlchemy 13y agoGood point, but if you wanted to work with an arbitrary distribution in the plane as a generalisation of this I think you'd need to look for an equal-area map from R2 to S2? (eg http://en.m.wikipedia.org/wiki/Lambert_azimuthal_equal-area_projection http://en.m.wikipedia.org/wiki/Lambert_azimuthal_equal-area_...) Edit: I mean R2 to S2 (although this is bijective)
- sopooneo 13y agoThis would generalize properly beyond two dimensions, right?