Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:21 ADT
Bill Stewart (bill.stewart@pobox.com)
Mon, 13 Jul 1998 18:22:55 -0700
>>If you have a (really) uniform distribution in [0,1) and add to
>>it another arbitrary distribution in [0,1) and take mod 1, the result
>>is a uniform distribution. This sounds strange but is true.
>Yes, and this can be extended by induction to N distributions: unlike what
>it happens with the simple sum of random variables, whose distribution comes
>to approximate a gaussian bell curve (Central Limit Theorem), the modular
>addition of uniformly-distributed variables maintains a uniform
>distribution. The simple sum has always a distribution which is the
>convolution of the two individual distributions: in our case, a triangle
>rising from (x=0, y=0) to (x=1, y=1) and then decreasing to (x=2, y=0). If
>you take the mod 1, the left side of the triangle is added to the right side
>(because e.g. both 1.3 and 0.3 in the sum contribute to 0.3 in the sum
>modulo 1), and we again have a rectangular shape.
My first reaction to the assertion was "that doesn't sound right",
and my second reaction was "Boy, it's been a long time since I've
done a definite integral, much less a definite double integral" :-)
But after playing with triangles a bit, I realized that there's a
much stronger approach for modular sums of uniform distributions
and arbitrary other distribution:
Let X1 = arbitrary_distn on [0,1)
Let X2 = U[0,1)
Let X = (X1+X2) mod 1
For ANY specific value x1, there's a 1:1 mapping between (x1+X2)mod 1 and [0,1) -
the range x1 <= X=(x1+X2) < 1 maps to 0 <= X2 < x1 , and
the range 0 <= X=((x1+X2)-1) < x1 maps to x1<= X2 < 1
so the probability distribution is U[0,1) for ANY value of X1,
and therefore uniform for any probability distribution of X1,
whether it's uniform, spike, normal, or whatever.
>By the way, this also supplies a proof that low bits (or digits) of a random
>variable represent a new variable with a distribution very close to uniform,
>regardless of the original distribution.
The modular disistribution is what makes it work; otherwise the distribution
may be much different from uniform. Consider X1 as a bimodal distribution
X1=0 p=0.50
X1=2 p=0.50
X=(X1+X2) has two uniform sections with a big gap in between.
This doesn't affect your low-bit assumption, but you can concoct
reasonable distributions that do, at least over discrete spaces
(which is what typical crypto applications work with.)
Thanks!
Bill
Bill Stewart, bill.stewart@pobox.com
PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:21 ADT