4
$\begingroup$

I'm trying to take a normal distribution of points, and force them to become a uniform distribution. I've had little success on S.O., so I thought I'd ask here.

Basically, I have a hash function which takes an X, Y, and seed value and generates numbers in a normal distribution with a mean of 0. These numbers vary only slightly from the numbers on all sides of them. When mapped out with the X and Y and the hashed value being Z, it creates a terrain map. The map has some large peaks far past 1 and -1, but the middle 50% of the values lie between (-0.4,0.4). I'm trying to smooth this map out so that it retains its shape, but has a more-or-less uniform (rather than normal) distribution.

As I said, the middle 50% of the values lie between (-0.4,0.4). The theoretical bounds for the hash function is (-2.25,2.25), though after generating a billion samples, the range of numbers found were about (-1.75,1.75).

I think I need to take the above information to determine the best fit normal distribution, then use it to transform each value. As I found out on S.O., it's a really tough problem for me to explain. Hopefully someone here can at least point me in the right direction explaining it, or understands what I'm trying to do.


The probability densities of my distribution, in blue, and Normal(0,.72), in red: [-3.8,3.8]

alt text


Their cumulative probabilities: [-3.8,3.8]

alt text


The probability density after inverse probability transform: [0,1]

alt text


And the cumulative probability compared to Uniform: [0,1] alt text

$\endgroup$
  • 1
    $\begingroup$ There are many ways to interpret (or misinterpret) your description, Daniel, so let me know where this attempt at a clarification might be wrong: You have a set of (x,y) coordinates. You apply a function to them to obtain a set of (x,y,z) values, a "terrain map." The z values can in principle lie in [-2.25,2.25] but actually they lie in [-1.75,1.75] with the middle 40% of them in [-0.4,0.4]. You seek a transformation f so that the collection of f(z) is uniformly distributed in [-1,1]. (If this characterization is correct, there's a simple solution involving a linear transform of the rank.) $\endgroup$ – whuber Sep 13 '10 at 14:58
  • $\begingroup$ @whuber - This sounds like a perfect interpretation. $\endgroup$ – dlras2 Sep 13 '10 at 16:07
  • $\begingroup$ @Daniel: Which probability integral are you using? If you used the one appropriate for the upper (green) curve, then the lower (red) curve should be perfectly horizontal. $\endgroup$ – whuber Sep 13 '10 at 20:24
  • $\begingroup$ @whuber - I'm using cubic interpolation between integral points generated from a hash function. $\endgroup$ – dlras2 Sep 13 '10 at 20:32
  • $\begingroup$ @Daniel: Although I'm quite familiar with all those terms, without more details it's hard to say whether the problems with the lower red curve are to be expected (e.g., if you're using a spline with a small number of knots) or are actually serious. I'm startled by the amount of error in the tails, though. $\endgroup$ – whuber Sep 13 '10 at 20:46
4
$\begingroup$

Interpreting your question as asking for the "inverse probability transform," as ars has indicated and you have confirmed in comments to the question, gives a simple solution: perform a sort to rank all the $z$ values in ascending order from $1$ to $N$ (the amount of data), then convert each $z$ into $2 Rank(z)/(N+1) - 1$. If you want to be really careful, scan over the ranked $z$'s to look for ties and assign each value within a group of tied values the average of their ranks.

$\endgroup$
  • $\begingroup$ The problem with this method is that I never actually have a complete map. The my noise function generates [x,y] independently from [x+n,y+m], and should have, on its own, a uniform distribution. I'm trying to make the function uniform. A uniform distribution over the map is simply a byproduct. (Granted, I didn't really make this clear in the question; +1 for the idea.) $\endgroup$ – dlras2 Sep 13 '10 at 19:07
  • $\begingroup$ @Daniel: Hmm, your actual situation is a little unclear. Maybe you could edit the question to say more about what your doing. Anyway, I'm operating on the assumption that the references to normality may be a bit of a red herring. $\endgroup$ – whuber Sep 13 '10 at 20:23
3
$\begingroup$

The inverse probability transform seems to be what you want.

To get a better uniform fit, the CDF $F(x)$ in the inverse probabiliy transform needs to be the actual distribution generating the data. If this isn't actually normal, then that could account for the relatively poor fit. You might try a Q-Q plot or normality test first. Or your data may very well be normal, just with some noise, in which case you can obtain a best fit. I would suggest trying in order:

  1. Standardize your data to N(0, 1) and see if the transformation improves.
  2. After a normality test, fit a normal distribution to your data, then apply the transformation.
$\endgroup$
  • $\begingroup$ This is looking good, but I'm having trouble interpreting my results (which I edited in above.) I think it means my starting distribution isn't exactly normal, but I can't seem to tweak it to work. I'm using x = (1 - erf(x))/2. Am I missing a constant scalar of some sort? $\endgroup$ – dlras2 Sep 13 '10 at 19:17
  • 1
    $\begingroup$ @Daniel: Don't think you're missing a constant, but scaling might help. Think your intuition about normality is correct though. I updated my answer with some suggestions. $\endgroup$ – ars Sep 13 '10 at 19:56
3
$\begingroup$

OK, your hash function is generating numbers according to some distribution. You're thinking of it as normal, but it's really not.

There's a simple way to convert between any univariate distribution and a uniform distribution. That is to use the cumulative distribution function CDF, which is a simple monotonic function, S-shaped, going from y = 0 to y = 1.

So to convert a number x from your hash distribution into a uniform number y, simply take y = CDF(x). To convert from uniform y to hash number x, just invert the CDF function.

To get the CDF function, just make a table lookup. Generate a large number N of your hash function numbers, put them in a big array, and sort them in ascending order. That is your table. Then to calculate CDF(x), just lookup x in the table, by binary search. Then its index i in the table tells what y is, by y = i/N. (Actually, I'm cheating a bit. You will be more accurate if you do interpolation between two adjacent entries.)

If you want to invert the CDF function, just take your uniform number y, and get i = N*y. That gives you an index in the table, where you find x. Of course, you should interpolate, but if N is big enough, and you're not really fussy about accuracy, you don't really need to.

P.S. I'm glossing over some details, like what to do at the very ends of the table, or what if your table contains duplicate values, but this should get you going.

$\endgroup$
  • $\begingroup$ I think this may be the way I'm going to go. I fear you're right about the hash function not being completely normal. $\endgroup$ – dlras2 Sep 13 '10 at 20:59
  • $\begingroup$ @Daniel: I suspect it doesn't matter if it's normal or not. If you want to know how normal it is, generate N numbers from a normal distribution, sort it, and plot against the numbers in your table. If your table is normal you'll get a straight line (QQ plot). If not, it will not be straight. Useful thing. $\endgroup$ – Mike Dunlavey Sep 13 '10 at 21:14
  • $\begingroup$ @Daniel: There's a really brain-dead simple way to generate a pretty good normal random number. Just add together 12 uniform numbers from the range -0.5 to 0.5. $\endgroup$ – Mike Dunlavey Sep 13 '10 at 21:16
1
$\begingroup$

Why does your transformation need to be a smooth deformation? Just take the binary representation of each number in 64-bit two's complement fixed point, or 64-bit IEEE floating point, and throw that into SHA-1. Boom, instant hash with uniform distribution of the outputs (assuming no duplicates).

$\endgroup$
  • $\begingroup$ I'm using a hash function to determine the integral points, which is why they have uniform distribution already. Continuity is important, however, between the points. I don't want completely random noise. $\endgroup$ – dlras2 Sep 15 '10 at 19:26
1
$\begingroup$

To recap, you have a function $f(x,y)$ which is continuous, and pseudo-random uniform at integer $(x,y)$, but nearly normal over the plane. You wish to make $f$ pseudo-random uniform over the whole plane. Suppose you could somehow make $f$ parametrized by some parameter $\lambda$, say by using $\theta$ to twiddle the pseudo-random uniform number generated at the lattice points. Then if you took $g(x,y) = \sum_{i} f(x,y,\lambda_i)$ for a whole bunch of $\lambda_i$ values, $g(x,y)$ would look much more normal, via the Central Limit Theorem. You could then invert the normal to get a uniform field. (I was inspired by Mike Dunlavey's comment on adding 12 uniforms to get a normal).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.