Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to generate uniformly random points on n-spheres and in n-balls

extremelearning.com.au

Post reply on HN
Print view View original

31–40 of 87 posts

Re: How to generate uniformly random points on n-spheres and in n-balls

#31

Post by dmd »

As an RA, before starting grad school, I hacked together some code to choose a random point on a sphere, for some psychophysics experiment I was doing.

Fortunately, I never used it for anything, because I made the classic naive mistake of simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles.

Somehow *12 years later* my subconscious flagged it up and I woke up in the middle of the night realizing the issue. Even though I'd never revisited it since then!

https://github.com/dmd/thesis/commit/bff319690188a62a79821aa...

Re: How to generate uniformly random points on n-spheres and in n-balls

#32

Post by lazide »

zamadatix wrote: post #15
wodenokoto wrote: post #9

Earlier quoted context omitted.

No. I would go so far as to say, if it’s not uniformly random, it isn’t random. My reasoning is, if you are counting cards in a game, you are giving yourself an advantage. But what really happens is that from your point of view cards will be drawn less and less uniformly randomly. Or put in another way, if you know the distribution is normal, you can bet on the the result being near the center and come out on top, bu…

Random (in statistics) means you cannot conclude the next value ahead of time. That's different than saying the next value is uniformly likely to be any value and the two concepts are actually orthogonal. E.g. If I had a bag with 99 red balls and 1 blue ball then randomly selected one you may assume there is a high chance there will be a red ball, based on the odds, but you aren't able to actually know which ball wil…

The second pick will have better odds of a blue ball, assuming the first one picked was red and the ball was not put back however - correct?

Even more so if you’ve gone 50 picks like that, and are now down to 49 red balls and one blue ball.

That is what card counting helps you with - knowing the odds based on your current state, as compared to the initial state.

Re: How to generate uniformly random points on n-spheres and in n-balls

#33

Post by marcodiego »

dmd wrote: post #31

As an RA, before starting grad school, I hacked together some code to choose a random point on a sphere, for some psychophysics experiment I was doing. Fortunately, I never used it for anything, because I made the classic naive mistake of simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Somehow *12 years later* my subconscious flagged it up and I woke up i…

A friend of mine made this mistake a long time ago when sampling points in a circle. He was baffled and couldn't understand why there was concentration of points around some areas of the circle. My explanation: draw a square around this circle; trace a horizontal line passing along its center; now, draw a diagonal line; can you see it is more likely that a randomly sampled point is closer to the diagonal than to horizontal line? He said "sure!" and I asked "why?" to what he promptly answered "because its longer.". He then asked what he should do about it, I simply said: "just ignore the points that are too far". He immediately understood that points inside the square but outside the disk were the reason for the concentration of the points.

Re: How to generate uniformly random points on n-spheres and in n-balls

#34

Post by xanderlewis »

dmd wrote: post #31

As an RA, before starting grad school, I hacked together some code to choose a random point on a sphere, for some psychophysics experiment I was doing. Fortunately, I never used it for anything, because I made the classic naive mistake of simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Somehow *12 years later* my subconscious flagged it up and I woke up i…

> simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles.

Am I right in thinking that it’s because circles of constant theta on the sphere contain the same ‘expected’ number of points (since phi is uniformly distributed), and these circles get smaller (and in the limit, shrink to a point) as one travels towards the poles — hence, higher density of points…?

…makes me realise that spherical polar coordinates, as natural as they seem, aren’t in some way homogeneous in the sense that whilst the mapping (theta, phi) —> (x, y, z) is continuous, it isn’t uniformly so… or something like that. I don’t know enough (possibly differential) geometry to articulate it properly, but it feels like the problem of getting genuinely uniform sampling from a sphere (or indeed any manifold) is somewhat equivalent to having a ‘nice’ coordinate system (one that respects the symmetry of the sphere). Basically, polar coordinates are prejudiced and treat points differently depending on how close to the poles they are.

By definition, our sampling in the domain space (two intervals) is uniform; the problem comes when we project through a coordinate system that doesn’t respect this.

Which better solution did you use? I’m having trouble reading your code on my current device.

Re: How to generate uniformly random points on n-spheres and in n-balls

#35

Post by dmd »

xanderlewis wrote: post #34
dmd wrote: post #31

As an RA, before starting grad school, I hacked together some code to choose a random point on a sphere, for some psychophysics experiment I was doing. Fortunately, I never used it for anything, because I made the classic naive mistake of simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Somehow *12 years later* my subconscious flagged it up and I woke up i…

> simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Am I right in thinking that it’s because circles of constant theta on the sphere contain the same ‘expected’ number of points (since phi is uniformly distributed), and these circles get smaller (and in the limit, shrink to a point) as one travels towards the poles — hence, higher density of points…? …makes…

> Which better solution did you use?

I didn't, since I haven't touched or needed this code since 2003. I just put a warning saying don't use it.

Re: How to generate uniformly random points on n-spheres and in n-balls

#37

Post by saalweachter »

wodenokoto wrote: post #9
JadoJodo wrote: post #2

I'm definitely not at all qualified to talk about this, but... aren't "uniform" and "random" antonyms?

No. I would go so far as to say, if it’s not uniformly random, it isn’t random. My reasoning is, if you are counting cards in a game, you are giving yourself an advantage. But what really happens is that from your point of view cards will be drawn less and less uniformly randomly. Or put in another way, if you know the distribution is normal, you can bet on the the result being near the center and come out on top, bu…

A simple example of non-uniform randomness is the two-dice roll.

Rolling two dice gives you a number which is random in [2, 12], but not uniform -- 7 is far more likely than 2 or 12.

Re: How to generate uniformly random points on n-spheres and in n-balls

#38

Post by contravariant »

bee_rider wrote: post #18
frankfrank13 wrote: post #6

I actually needed this at work once! We needed to fuzz peoples address in a mapped view for analytics, without revealing PII. It ended up never being shipped, but we needed to fuzz geographic data and the thinking was like: 1. Truncate your lat longs to some arbitrary decimal place (this is very very stupid, you end up with grid lines [1]) 2. The above method ^^ but everyone tries basically doing like random angle +…

The rejection method smells pretty good to me, in the sense that it should be pretty obvious to anybody with, like, middle school level math I think (right?). It might fail for higher dimensions, but lots of programs only run on a 3D sphere of a planet, haha!

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential.

I don't actually know of any useful algorithms with worse asymptomatic behaviour.

Re: How to generate uniformly random points on n-spheres and in n-balls

#39

Post by _dain_ »

wodenokoto wrote: post #9
JadoJodo wrote: post #2

I'm definitely not at all qualified to talk about this, but... aren't "uniform" and "random" antonyms?

No. I would go so far as to say, if it’s not uniformly random, it isn’t random. My reasoning is, if you are counting cards in a game, you are giving yourself an advantage. But what really happens is that from your point of view cards will be drawn less and less uniformly randomly. Or put in another way, if you know the distribution is normal, you can bet on the the result being near the center and come out on top, bu…

The uniform distribution is in some sense the most random distribution you can choose, given that you have a finite number of cards. Formally, it's the maximum entropy distribution on a finite domain.

But what if the domain isn't finite? e.g. the entire real line? Then we can't define a uniform distribution, because the total probability can never sum to one. We can still define a maximum entropy distribution, but only by making some more assumptions. The normal distribution is the maximum entropy distribution on the real line, given a particular mean and variance.

Other examples: on the positive real line, the exponential distribution is maximum-entropy for a given mean. Poisson distribution is the equivalent on the non-negative integers.

Re: How to generate uniformly random points on n-spheres and in n-balls

#40

Post by atum47 »

Some years ago I saw a blue and red image that caught my attention. The red dots seemed to be floating around the blue ones. I later found out that has a name - Chromostereopsis [1]. So I decided to make my own image and needed to distribute some points in a circle, this how I did it [2].

[1] - https://en.wikipedia.org/wiki/Chromostereopsis

[2] - https://jsfiddle.net/victorqribeiro/vxf2ajzm/48/

Post reply on HN