Live data from Hacker News

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

extremelearning.com.au

61–70 of 87 posts

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

#61
post #58

Earlier quoted context omitted.

Depends if the balls are placed back or not. Similar to cards, any game which never replenishes the deck and lets you draw all the cards down to the last one lets the last pick (but not the prior ones) be non-random.

I literally stated ‘if the balls don’t get put back’. And the last card was still random, btw. But can be guessed now with perfect precision due to the process of elimination. Random at shuffle doesn’t mean unguessable or unpredictable as the game goes on.

Sorry, meant to say the more generic "replenished" but typed a bit of your comment while reading it at the same time :p. That's what I was saying by the next part, it doesn't matter _how_ it's replenished just that the pool doesn't dwindle to 1 option for any reason. E.g. you could not put them back pull and mix from multiple decks/ball sources as the game progresses and even though 51 cards/99 balls are discarded you don't know what n+1 is for certain yet.

I disagree the last card is "still" random, at least in the sense of statistics. It "was" random up until the measure of uncertainty of the next event reaches 0 (i.e. entropy reaches 0). At that point it's no longer a "guess", there is no uncertainty and the remaining pattern is always 100% predictable in that regardless which proceeding events occured to get there it can always be known what the next value is without uncertainty. Since there ceases to be any uncertainty in what the remaining pattern will be there ceases to be randomness in the next value generated. That the card's value was not known at n=0 does not affect whether the n+1 card still is/isn't random when n=51. In another form, that you didn't previously know the value of card n=52 with past information holds no influence whether the value is random or not with new information. Statistical randomness is all about what you know of the future predictability, not about how something came about.

This is also true of events which fall into predictable patterns at any point along the path. E.g. if I had a (relatively useless) hardware random number generator that generated random numbers 0-127 once per second until it generated a 0 at n=17, at which point it ceased being able to pull randomness from it's dead circuits and always produced 0 afterward, the first 17 values were all statistically random at the time of their draw but n=[18,inf) are all now predictable and no longer random from that point on.

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

#62
post #8

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 +…

I needed something related, n roughly evenly distributed points on the surface of a sphere. Ended up using a Fibonacci spiral. https://extremelearning.com.au/how-to-evenly-distribute-poin...

Hey me too, very interesting problem. I also used this method as well. https://www.sciencedirect.com/science/article/abs/pii/S00104...

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

#63
post #47

Earlier quoted context omitted.

Sure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter. Most maps are 2-dimensional and this is fine.

Maybe n=4 if you have a timestamp as another dimension.

Do your timestamps occupy a hypersphere?

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

#64
post #8

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 +…

I needed something related, n roughly evenly distributed points on the surface of a sphere. Ended up using a Fibonacci spiral. https://extremelearning.com.au/how-to-evenly-distribute-poin...

Force directed layout is my favorite for this.

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

#65
I encountered the need for uniform random points on hyperspheres, and found this solution (with Python code) very helpful: https://stackoverflow.com/a/59279721.

Currently, I am porting my codebase to Rust and did that part over the weekend, so if anyone is interested in this exact implementation, I'd willing to share it (as a crate if necessary).

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

#66
I learned the easiest way to do d-dimension sampling in Foundations of Data Science: see https://news.ycombinator.com/item?id=34575637 or https://www.cs.cornell.edu/jeh/book.pdf?file=book.pdf

I don't think it's a good idea to introduce over 20 different methods before talking about the correct one that works for any number of dimensions, say n, and the reason behind its correctness is very obvious:

* Generate a random vector by sampling n standard normal distributions: `vector = np.random.randn(n)`

* Key step: show that the vector has a uniform direction.

The proof is as follows: you look at the probability density function of a normal distribution, which is `p(x)=1/sqrt(2pi)*exp(-x^2/2)`, and the probability density function of the vector is the product of all these densities of its individual dimensions. Now the product `p(x1)p(x2)...p(xn)=1/sqrt(2pi)^n*exp(-(x1^2+x2^2+...+xn^2)/2)` since `exp(a)exp(b)=exp(a+b)` due to power functions.

Now it's easy to see that probability density is invariant to vector length, which means the vector has uniform probability for any specific value of x1^2+x2^2+...+xn^2. Whatever rotation you apply after sampling this vector, since rotation preserves x1^2+x2^2+...+xn^2 by definition, you get the exact same probability density function and therefore the same distribution of vectors.

* Now that the direction of the vector is uniformly sampled, decide the radius separately: for n-sphere the radius is just 1, and for n-ball the volume of the radius is proportional to the nth power of the radius, so you sample a uniform number from [0,1] as the volume and take the nth root as the radius: `radius = np.random.uniform(0, 1)*(1/n)`

* Normalize the vector to the radius: `vector = vector / np.sqrt((vector*2).sum()) * radius`

I think Section 2 of this book provides a much better perspective on the problem of generating uniform random points, since it also provides intuition behind the geometry of high dimensions and properties of the unit ball, etc.

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

#68

Another way to generate uniformly random points on a 2D disk that the author forgot to mention: let A be an n x n complex matrix whose elements are iid copies of a fixed random variable with unit variance. Let lambda_i be its ith eigenvalue, and let x_i = 1/sqrt(n) real(lambda_i) and y_i = 1/sqrt(n) imag(lambda_i). As n approaches infinity, the distribution of x, y approaches almost certainly to the uniform distribut…

It's very inefficient, both on terms of runtime and in terms wasted entropy.

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

#69

Earlier quoted context omitted.

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.

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

Note: "asymptomatic" does not mean the same as "asymptotic"

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

#70
post #8

Earlier quoted context omitted.

I needed something related, n roughly evenly distributed points on the surface of a sphere. Ended up using a Fibonacci spiral. https://extremelearning.com.au/how-to-evenly-distribute-poin...

Force directed layout is my favorite for this.

...but then the algorithmic complexity goes from O(N) to O(N^2), or at least O(N log N), since points have to interact with each other.

(N denotes the number of points you need to generate)

Post reply on HN