5 ms·

uh... yes, yes it is. see for example http://mathworld.wolfram.com/HyperspherePointPicking.html http://mathworld.wolfram.com/HyperspherePointPicking.html

lpage 10y ago
Yup, as described in TAOCP vol 2 as well.
dahart 10y ago
It's uniform if you reject points with length > 1 before normalizing (your link mentions this), but not uniform as written. It's a simple adjustment, but you do have to cull. Edit: yeah oops, I goofed and I'm wrong. I didn't notice it was randn - normally distributed. No culling necessary.
- murbard2 10y ago
  If you try rejection sampling in 300 dimensions, you're gonna have a bad time.
  - dahart 10y ago
    Is it bad for a unit sphere specifically, or just a generally bad idea? I was just thinking the volume ratio of the hyper sphere to the hyper cube is always over 0.5 in any number of dimensions? But I'm not sure about that. Or do you mean more that it sucks pretty bad to generate 300 rands and then throw them away, even once?
    - asafira 10y ago
      Rejection sampling is not necessarily a bad idea in general, but in this particular case it would be bad. You are going to choose 300 random numbers between -1 and 1, and then throw away this batch if their norm is greater than 1. As you increase dimension (in this case 300), you are including more numbers that give a non-negative contribution to this norm, and so you are increasing your chance of rejection with each dimension. Re-reading your comment, I notice you made a higher-level note regarding the volume of the hypercube vs. hypersphere. While my comment was right, I now think you are right that the volume ratio of hyper sphere to hypercube is, in fact, always over 0.5. I'm gonna run a quick simulation anyway, but you can convince yourself of this by considering that the line segment connecting (1,0) and (0,1) in 2D lies within the unit circle, but a similar construction will always work for high dimensions (I think).
    - asafira 10y ago
      Nope, I was wrong --- the volume of the hyper sphere to the hyper cube is not always over 0.5.
      - murbard2 10y ago
        It in fact decreases exponentially
        dahart 10y ago
        Yeah, wild, I didn't know this. https://en.m.wikipedia.org/wiki/Volume_of_an_n-ball https://en.m.wikipedia.org/wiki/Volume_of_an_n-ball Jeez, my intuition stinks. I initially thought it was obvious why the 3D sphere to unit cube ratio is > 0.5, by analogy to the 2d diamond embedded in a square, but in 3D the embedded octagon volume isn't 0.5. Obvious now, but that'll teach me not to guess. Indeed, rejection sampling the 300 dimensional unit sphere will suck really bad.

lpage 10y ago

Yup, as described in TAOCP vol 2 as well.

dahart 10y ago

It's uniform if you reject points with length > 1 before normalizing (your link mentions this), but not uniform as written. It's a simple adjustment, but you do have to cull. Edit: yeah oops, I goofed and I'm wrong. I didn't notice it was randn - normally distributed. No culling necessary.

murbard2 10y ago
If you try rejection sampling in 300 dimensions, you're gonna have a bad time.
- dahart 10y ago
  Is it bad for a unit sphere specifically, or just a generally bad idea? I was just thinking the volume ratio of the hyper sphere to the hyper cube is always over 0.5 in any number of dimensions? But I'm not sure about that. Or do you mean more that it sucks pretty bad to generate 300 rands and then throw them away, even once?
  - asafira 10y ago
    Rejection sampling is not necessarily a bad idea in general, but in this particular case it would be bad. You are going to choose 300 random numbers between -1 and 1, and then throw away this batch if their norm is greater than 1. As you increase dimension (in this case 300), you are including more numbers that give a non-negative contribution to this norm, and so you are increasing your chance of rejection with each dimension. Re-reading your comment, I notice you made a higher-level note regarding the volume of the hypercube vs. hypersphere. While my comment was right, I now think you are right that the volume ratio of hyper sphere to hypercube is, in fact, always over 0.5. I'm gonna run a quick simulation anyway, but you can convince yourself of this by considering that the line segment connecting (1,0) and (0,1) in 2D lies within the unit circle, but a similar construction will always work for high dimensions (I think).
  - asafira 10y ago
    Nope, I was wrong --- the volume of the hyper sphere to the hyper cube is not always over 0.5.
    - murbard2 10y ago
      It in fact decreases exponentially
      - dahart 10y ago
        Yeah, wild, I didn't know this. https://en.m.wikipedia.org/wiki/Volume_of_an_n-ball https://en.m.wikipedia.org/wiki/Volume_of_an_n-ball Jeez, my intuition stinks. I initially thought it was obvious why the 3D sphere to unit cube ratio is > 0.5, by analogy to the 2d diamond embedded in a square, but in 3D the embedded octagon volume isn't 0.5. Obvious now, but that'll teach me not to guess. Indeed, rejection sampling the 300 dimensional unit sphere will suck really bad.