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

81–87 of 87 posts

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

#81

Post by bee_rider »

contravariant wrote: post #38
bee_rider wrote: post #18

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.

Quibble: I don’t think “fail” is an understatement, it is as strong a word as anything else for something that doesn’t work.

Actually, it is an overstatement I think, or something orthogonal; the algorithm is still correct just wildly inefficient. Fail should be reserved for algorithms that produce the wrong result, not ones that produce the right result very slowly, however slowly.

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

#82

Post by lazide »

zamadatix wrote: post #61
lazide wrote: post #58

Earlier quoted context omitted.

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

I think you’re getting confused? Or we’re talking past each other?

Knowing the outcome of a die roll after the roll doesn’t make the roll of the die non-random.

Any more than the die coming up 6 a bunch of times in a row does. Though maybe it would be a good idea to check the weight/balance of it, hah.

Knowing what the last card has to be after all the other cards have been played doesn’t make the process which made that card the last card any less random either.

Picking cards off a deck isn’t a randomization/non-randomization event, shuffling the deck is what does that.

Probability however, which directly impacts gameplay in some kinds of games, is directly impacted by knowledge exposed during gameplay.

So for instance, the second to last card (and also the last card) can be known with about 50/50 odds (probability wise) if someone is good at counting, which is damn good! Way better than 1/2704 odds of guessing a sequence of two cards at the start of the deck.

In the example of the broken hardware random number generator, knowledge of the defect can be used to attack a system if it assumes a continuous probability distribution out it’s outputs, if the attacker knows this.

The same as an attacker at a casino could probably manipulate a game to make money if they knew something was broken in the deck shuffling and the same two cards were always at some position in a ‘new’ deck.

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

#83

Post by FooBarBizBazz »

renonce wrote: post #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 rando…

This is the way.

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

#84

Post by 0-_-0 »

renonce wrote: post #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 rando…

I can't believe I didn't already know this

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

#85

Post by zamadatix »

lazide wrote: post #82
zamadatix wrote: post #61

Earlier quoted context omitted.

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

I think you’re getting confused? Or we’re talking past each other? Knowing the outcome of a die roll after the roll doesn’t make the roll of the die non-random. Any more than the die coming up 6 a bunch of times in a row does. Though maybe it would be a good idea to check the weight/balance of it, hah. Knowing what the last card has to be after all the other cards have been played doesn’t make the process which made…

> Knowing what the last card has to be after all the other cards have been played doesn’t make the process which made that card the last card any less random either.

Exactly, same page then. The card not being random at the end of game frame of reference places no limitation that it was random from the beginning of the game frame of reference. In the end of game reference the last card is never random, it's only ever the remaining card. In the beginning game reference which card will end up being the last card is still random at that point despite it ceasing to be from the later frame.

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

#86

Post by frankfrank13 »

esafak wrote: post #59
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/

This is what I landed on! It actually works very very well for aggregate data.

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

#87

Post by frankfrank13 »

chpatrick wrote: post #28
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 +…

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

Another user here mentioned Uber's h3, which is actually what I used. You end up being able to anonymize over arbitrarily large geographic areas using something like a tile, rather than a point
Post reply on HN