Random with care
eev.ee
eev.ee
An apocryphal story from a former finance professor who taught me about MCMC: One of his former colleagues was working for a hedge fund in commodity futures markets, and he had developed a monte carlo model for trading in a very specific market that was working exceptionally well. Then one day it stopped working so well...returns cut by 1/2 of their original level. It wasn't a gradual decline, but rather one day it was one level and then overnight that changed. He eventually got poached by a competing hedge fund working in the same exact markets, and he found out that the reason his returns declined was because one of the mathematicians at his new company had almost perfectly reverse engineered his model by guessing his RNG seed, conveniently a number in the name of his former hedge fund.
moral of the story: behind every RNG Cthulhu waits, sleeping.
Given that the "draw from a Gaussian and normalize" seems like the hard way to do it and also is the only one anyone is suggesting, I assume I'm missing something. Anyone know what the problem is?
Just for prudence sake; one way of seeing why the normalization of n independent gaussian draws works. Is that the multivariate normal distribution in n-dimensions with independent coordinates is rotationally symmetric. One can visualize this in 2 dimensions by making a graph of the probability density and seeing it is invariant under rotations of the plane. This generalizes to higher dimensions. This is exactly the property that any direction is equally likely.
One could of course do this by picking the direction first, and then calculating the necessary pitch/roll/yaw changes to point that way, but I wonder if there is a good way to it without selecting the direction first? In other words, can you do it just by using your random numbers to pick pitch, roll, and yaw changes, assuming you only have the common random number generator distributions available.
First thing that comes to mind would be to do a random pitch change in [-pi, pi) then a random yaw change in [-pi, pi), but I think that is still going to be non-uniform. It doesn't have the same problem as the lat/long approach (because both pitch and yaw move on great circles, so you don't have anything like the variable length latitude line problem), but it still favors some points.
Including a random roll step in there changes it from two favored points to a favored great circle (I think...visualizing this is hurting my brain), but I suspect that no finite sequence of pitch, roll, yaw random steps determined by independent random numbers with distributions that are not changing based on prior selections can erase biases that stem from the fact that this approach is starting with the ship pointing at a particular point and having a particular initial orientation.
gattr suggests in another comment to look for clues around global illumination methods on how to solve this problem; his reference has the equations for picking polar coordinates from two random numbers generated from a [0..1] uniform distribution in section IV. B.
The specialness of the Gaussian has been mentioned here before: https://news.ycombinator.com/item?id=9446126
This gets more complicated in higher dimensions, and at that point it is easier (and perhaps cheaper) to do the gaussian thing. But for 3D it is reasonable if you get your math right.
Another option is to pick a random point inside the unit (hyper-)cube with a uniform random coordinate along each axis, and merely re-roll if your point falls outside the sphere. This gets worse and worse in higher dimensions, though, as the volume of the ball shrinks relative to the volume of the cube.
Playing around with distributions as the author does is surely fine if you just want to get something that "feels right", but if the applications depend on precise randomness properties, then, for example, "let's just multiply these two PDFs" is dangerous (not least because the result is almost guaranteed not to be a PDF, and may not even be normaliseable to one).
Although it surely won't be applied for random f (no pun intended), the transformation from P(f(u) ≤ x) to P(u ≤ f^(-1)(x)) relies very much on f being (strictly, in order to have an inverse) increasing—so it's even dangerous to use f(x) = x^2 if we don't know that u is non-negative-valued.
Using the output of RNG still requires some skill, but that's about designing a "fair" set of rules. Not a better way of obtaining truly random, random enough, or plausibly pseudo-random numbers from a given system.
As the article discussed, there are times when a designer might want to add in bias to make the response of the system fit within desired constraints.
One such example might be a load balancing daemon removing targets from a distribution entirely if they are either unresponsive or under sufficiently greater load (relative to other targets).
A loop of 10 million iterations of straight rand() output produces unique values only about 2% of the time -- the other 98% of values are repeated throughout the sequence. (This may be due to time-of-day as seed.)
gawk 'BEGIN {srand(); for (i=0;i<10000000;i++) printf("%s\n", rand())}' | sort | uniq -c | wc -l
This information may be well documented, though I find it in neither the gawk manpage (yes, I'm aware FSF deprecates manpages, an idiotic move), nor the online gawk manual, linked below.
Again -- if you're just playing around, this may not hurt you, but if you're fond of gawk and think you can develop high-strength crypto or security code using it, you're going to need to go beyond the built-ins at the very least.
Earlier: https://plus.google.com/104092656004159577193/posts/exhAxhd4...
Interesting tidbit! So all the times I've furiously cursed at my gameboy because I swear the 'I' is by far the rarest tetrimino and it hasn't given me one for at least 20 turns... was just classic cognitive bias.
Anyone know why?
2^255 = 5.7896045e+76
52! = 8.0658175e+67
EDIT: I misread 2^225 as 2^255, thanks for the heads up from rzzzt.
2^225 = 5.3919893e+67, which is indeed smaller.
2^225 = 5.3919893e+67
2^226 = 1.0783979e+68
int getRandomNumber()
{
return 4; // chosen by fair dice roll.
// guaranteed to be random.
}