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

51–60 of 87 posts

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

#51

Post by [deleted] »

jerf wrote: post #23
pvg wrote: post #5

Earlier quoted context omitted.

No, 'uniform' refers to the distribution, which need not be uniform, e.g. https://numpy.org/doc/stable/reference/random/generated/nump... Or in god's own words ( TAOCP section 3.4 ): Applications of random numbers often call for other kinds of distributions, however; for example, if we want to make a random choice from among k alternatives, we want a random integer between 1 and k. If some simulation process calls fo…

"All distributions are uniform" is one of the two cardinal crimes of a school level of statistics understanding, the other being "all probabilities are independent".

[deleted]

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

#52

Post by porphyra »

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 distribution over the unit disk.

Tao, T., Vu, V., and Krishnapur, M. (2010) Random matrices: universality of ESDs and the circular law. The Annals of Probability. 38(5) 2023-2065.

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

#53

Post by xyzzy_plugh »

nighthawk454 wrote: post #29
chpatrick wrote: post #28

Earlier quoted context omitted.

What if someone lives in a really remote location so they're the only ones in the heat map cell?

I should think after defining a uniform distribution of points, you could cluster them as needed to form larger lower-resolution chunks according to population size. Binning everyone in that region to say the central most point. Which could then be adaptive as the populations change.

This is the correct answer. You need an aggregation threshold that restricts precision when population count is too low. In this case, the cell size needs to increase until there are at least N users.

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

#54

Post by throwaway81523 »

ianferrel wrote: post #45
contravariant wrote: post #38

Earlier quoted context omitted.

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.

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.

When I saw "n" in the title I assumed they wanted something that worked reasonably for large n. Rejection is no good because of the notorious "curse of dimensionality". So my idea was to choose a suitable distribution on the radius, then draw from it and choose the angles at random (not sure what those angles are called). You might have to delete the point at the center for that to work.

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

#55

Post by zamadatix »

lazide wrote: post #32
zamadatix wrote: post #15

Earlier quoted context omitted.

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.

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.

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

#57

Post by kadoban »

tiffanyh wrote: post #56

Off topic: isn't "uniformly random" a contradiction of terms?

No. Random just means you can't predict what value will be chosen, but doesn't tell you how likely different values are.

If I roll a 12-sided die, that's random. If I roll two 6-sided dice and add the result, that's also random, but it has a different distribution of values.

The two dice verison, there's one way to get a result of 2, but _several_ ways to get 7. You'll get 7 way more often than you'll get 2.

The one-die version each outcome is equally likely. You're exactly as likely to get 2 as you are to get 7 or any other value in the range of possibilities.

The one-die version is a uniform distribution. The two-dice version is not uniform.

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

#58

Post by lazide »

zamadatix wrote: post #55
lazide wrote: post #32

Earlier quoted context omitted.

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.

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.

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

#59

Post by esafak »

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

I'd just have used Uber's hexagonal tiling library. https://www.uber.com/blog/h3/
Post reply on HN