3 ms·

In the example about picking a random 3-d vector, it seems like the "draw components from a Gaussian distribution" method is the most common, but I don't really

In the example about picking a random 3-d vector, it seems like the "draw components from a Gaussian distribution" method is the most common, but I don't really understand why you can't just pick two angles ([0, pi) and [0, 2pi) respectively) from a uniform distribution and interpret those as spherical coordinates on a unit sphere. Given that the "draw from a Gaussian and normalize" seems like the hard way to do it and also is the only one anyone is suggesting, I assume I'm missing something. Anyone know what the problem is?

adament 9y ago
That is actually a really nice question, essentially it boils down to the same trouble as he described with the taking each coordinate between -1 and 1 and normalizing, in that you get certain preferred directions and not the uniform distribution on the sphere. In your case you get that each of the circles described by your first angle are equally probable. But when you look at a sphere and trace them out, they have different lengths, hence they should have different probabilities. The most extreme case is that the pole (a single direction) has just as high a probability as the entire equator combined. Just for prudence sake; one way of seeing why the normalization of n independent gaussian draws works. Is that the multivariate normal distribution in n-dimensions with independent coordinates is rotationally symmetric. One can visualize this in 2 dimensions by making a graph of the probability density and seeing it is invariant under rotations of the plane. This generalizes to higher dimensions. This is exactly the property that any direction is equally likely.
- x1798DE 9y ago
  Ah, this makes a lot of sense. I tooled around a bit plotting some distributions with matplotlib after I posted my comment and indeed found that drawing random angles was clustered around the poles. From your explanation, now it seems almost obvious that it would be that way.
  - bb88 9y ago
    Yeah, I hit a similar problem way back in college when trying to generate random light rays from a point. I remember it being a tricky problem and hard to model without some kind of software to figure out if the randomness was correct.
- tzs 9y ago
  Suppose you are in a spaceship, and you want to pick a random direction to travel. You want to do so with at most one pitch change, one roll change, and one yaw change. One could of course do this by picking the direction first, and then calculating the necessary pitch/roll/yaw changes to point that way, but I wonder if there is a good way to it without selecting the direction first? In other words, can you do it just by using your random numbers to pick pitch, roll, and yaw changes, assuming you only have the common random number generator distributions available. First thing that comes to mind would be to do a random pitch change in [-pi, pi) then a random yaw change in [-pi, pi), but I think that is still going to be non-uniform. It doesn't have the same problem as the lat/long approach (because both pitch and yaw move on great circles, so you don't have anything like the variable length latitude line problem), but it still favors some points. Including a random roll step in there changes it from two favored points to a favored great circle (I think...visualizing this is hurting my brain), but I suspect that no finite sequence of pitch, roll, yaw random steps determined by independent random numbers with distributions that are not changing based on prior selections can erase biases that stem from the fact that this approach is starting with the ship pointing at a particular point and having a particular initial orientation.
  - rzzzt 9y ago
    "Hot spots" of directions appear because the more your spacecraft pitches "up" or "down", the less contribution yaw changes make on the final result. At the extremes, the entire range of yaw values is effectively wasted on rolling: https://en.wikipedia.org/wiki/Gimbal_lock#In_three_dimensions https://en.wikipedia.org/wiki/Gimbal_lock#In_three_dimension... gattr suggests in another comment to look for clues around global illumination methods on how to solve this problem; his reference has the equations for picking polar coordinates from two random numbers generated from a [0..1] uniform distribution in section IV. B.
cs_ 9y ago
I think that tends to produce a distribution clustered at the poles. At high latitudes, the impact of the longitude is much smaller than it would be around the equator. Mathworld has a nice write up that visualizes the effect and details more of the reasoning for the Gaussian method. [0] http://mathworld.wolfram.com/SpherePointPicking.html http://mathworld.wolfram.com/SpherePointPicking.html
- theoh 9y ago
  Yes, it is literally analogous to choosing points from the set of intersections of lines of integral latitude and longitude, which is not what you want. The specialness of the Gaussian has been mentioned here before: https://news.ycombinator.com/item?id=9446126 https://news.ycombinator.com/item?id=9446126
deleted 9y ago
[deleted]
madcaptenor 9y ago
Longitude on the sphere is uniformly distributed. Latitude isn't. If you chose the angle in [0, pi) (the "colatitude" - https://en.wikipedia.org/wiki/Colatitude https://en.wikipedia.org/wiki/Colatitude) from the right distribution this would work. See for example https://en.wikibooks.org/wiki/Mathematica/Uniform_Spherical_Distribution https://en.wikibooks.org/wiki/Mathematica/Uniform_Spherical_... - it looks like selecting 2 arcsin sqrt(X), where X is uniform on [0, 1], does the trick.
FabHK 9y ago
Your sample points will be denser at the pole than the equator (think about what happens when your first coordinate is near zero vs when it's near pi/2).
tbabb 9y ago
You can use polar coordinates; you just have to be sure to correct for the pinching of a polar coordinate system, which will bunch your samples toward the poles. This gets more complicated in higher dimensions, and at that point it is easier (and perhaps cheaper) to do the gaussian thing. But for 3D it is reasonable if you get your math right. Another option is to pick a random point inside the unit (hyper-)cube with a uniform random coordinate along each axis, and merely re-roll if your point falls outside the sphere. This gets worse and worse in higher dimensions, though, as the volume of the ball shrinks relative to the volume of the cube.

adament 9y ago

That is actually a really nice question, essentially it boils down to the same trouble as he described with the taking each coordinate between -1 and 1 and normalizing, in that you get certain preferred directions and not the uniform distribution on the sphere. In your case you get that each of the circles described by your first angle are equally probable. But when you look at a sphere and trace them out, they have different lengths, hence they should have different probabilities. The most extreme case is that the pole (a single direction) has just as high a probability as the entire equator combined. Just for prudence sake; one way of seeing why the normalization of n independent gaussian draws works. Is that the multivariate normal distribution in n-dimensions with independent coordinates is rotationally symmetric. One can visualize this in 2 dimensions by making a graph of the probability density and seeing it is invariant under rotations of the plane. This generalizes to higher dimensions. This is exactly the property that any direction is equally likely.

x1798DE 9y ago
Ah, this makes a lot of sense. I tooled around a bit plotting some distributions with matplotlib after I posted my comment and indeed found that drawing random angles was clustered around the poles. From your explanation, now it seems almost obvious that it would be that way.
- bb88 9y ago
  Yeah, I hit a similar problem way back in college when trying to generate random light rays from a point. I remember it being a tricky problem and hard to model without some kind of software to figure out if the randomness was correct.
tzs 9y ago
Suppose you are in a spaceship, and you want to pick a random direction to travel. You want to do so with at most one pitch change, one roll change, and one yaw change. One could of course do this by picking the direction first, and then calculating the necessary pitch/roll/yaw changes to point that way, but I wonder if there is a good way to it without selecting the direction first? In other words, can you do it just by using your random numbers to pick pitch, roll, and yaw changes, assuming you only have the common random number generator distributions available. First thing that comes to mind would be to do a random pitch change in [-pi, pi) then a random yaw change in [-pi, pi), but I think that is still going to be non-uniform. It doesn't have the same problem as the lat/long approach (because both pitch and yaw move on great circles, so you don't have anything like the variable length latitude line problem), but it still favors some points. Including a random roll step in there changes it from two favored points to a favored great circle (I think...visualizing this is hurting my brain), but I suspect that no finite sequence of pitch, roll, yaw random steps determined by independent random numbers with distributions that are not changing based on prior selections can erase biases that stem from the fact that this approach is starting with the ship pointing at a particular point and having a particular initial orientation.
- rzzzt 9y ago
  "Hot spots" of directions appear because the more your spacecraft pitches "up" or "down", the less contribution yaw changes make on the final result. At the extremes, the entire range of yaw values is effectively wasted on rolling: https://en.wikipedia.org/wiki/Gimbal_lock#In_three_dimensions https://en.wikipedia.org/wiki/Gimbal_lock#In_three_dimension... gattr suggests in another comment to look for clues around global illumination methods on how to solve this problem; his reference has the equations for picking polar coordinates from two random numbers generated from a [0..1] uniform distribution in section IV. B.

cs_ 9y ago

I think that tends to produce a distribution clustered at the poles. At high latitudes, the impact of the longitude is much smaller than it would be around the equator. Mathworld has a nice write up that visualizes the effect and details more of the reasoning for the Gaussian method. [0] http://mathworld.wolfram.com/SpherePointPicking.html http://mathworld.wolfram.com/SpherePointPicking.html

theoh 9y ago
Yes, it is literally analogous to choosing points from the set of intersections of lines of integral latitude and longitude, which is not what you want. The specialness of the Gaussian has been mentioned here before: https://news.ycombinator.com/item?id=9446126 https://news.ycombinator.com/item?id=9446126

deleted 9y ago

[deleted]

madcaptenor 9y ago

Longitude on the sphere is uniformly distributed. Latitude isn't. If you chose the angle in [0, pi) (the "colatitude" - https://en.wikipedia.org/wiki/Colatitude https://en.wikipedia.org/wiki/Colatitude) from the right distribution this would work. See for example https://en.wikibooks.org/wiki/Mathematica/Uniform_Spherical_Distribution https://en.wikibooks.org/wiki/Mathematica/Uniform_Spherical_... - it looks like selecting 2 arcsin sqrt(X), where X is uniform on [0, 1], does the trick.

FabHK 9y ago

Your sample points will be denser at the pole than the equator (think about what happens when your first coordinate is near zero vs when it's near pi/2).

tbabb 9y ago

You can use polar coordinates; you just have to be sure to correct for the pinching of a polar coordinate system, which will bunch your samples toward the poles. This gets more complicated in higher dimensions, and at that point it is easier (and perhaps cheaper) to do the gaussian thing. But for 3D it is reasonable if you get your math right. Another option is to pick a random point inside the unit (hyper-)cube with a uniform random coordinate along each axis, and merely re-roll if your point falls outside the sphere. This gets worse and worse in higher dimensions, though, as the volume of the ball shrinks relative to the volume of the cube.