Re: FFT test with few kbits

From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 02/23/04 

Date: Mon, 23 Feb 2004 12:58:07 GMT

Cristiano wrote:
> Bill Unruh wrote:
>> "Cristiano" <cristiano.pi@NSquipo.it> writes:
>>
>> ]Ernst Lippe wrote:
>> ]> On Tue, 17 Feb 2004 22:06:26 +0000, Cristiano wrote:
>> ]>
>> ]>> Eric Backus wrote:
>> ]>>> "Ernst Lippe" <ernstl-at-planet-dot-nl@ignore.this> wrote in
>> message ]>>> news:40311637$0$1201$ba620dc5@nova.planet.nl...
>> ]>>>> On Wed, 11 Feb 2004 13:11:29 +0000, Eric Backus wrote:
>> ]>>>>
>> ]>>>>> To get useful statistical tests, I think the DFT should have a
>> ]>>>>> much larger number of bits, so that you can make assumptions
>> ]>>>>> about the distributions approaching Gaussian. In addition,
>> since ]>>>>> the output values clearly are not completely
>> independent, I think ]>>>>> that only a subset of the output values
>> should be analyzed. ]>>>> This is only correct when you can show that
>> all items in your ]>>>> subset are independent. I believe that every
>> pair of F coefficients ]>>>> is dependent, so I don't think that your
>> approach will work. ]>>>
>> ]>>> I agree that they are probably all dependent. But I'm guessing
>> (and ]>>> yes, it's a completely unsubstantiated guess) that each
>> pair ]>>> approaches being independent as the size of the transform
>> gets ]>>> large. Are they "independent enough" to be useful in a
>> test for ]>>> randomness?
>> ]>>
>> ]>> Each pair? I don't know. But the transformed values, yes; they
>> are ]>> "independent enough" to be useful in a test for randomness.
>> ]>
>> ]> No, they are definitely not independent.
>>
>> ]I agree, but I'd like to say that they are "independent enough"
>> because the ]test is *perfectly* reliable; it works like expected and
>> now I think I have ]the proof.
>> ]I try to translate the answer of an Italian mathematician:
>>
>> ]I have a random sequence of indipendent bits (with probability of 0
>> and 1 ]equal 1/2).
>> ]The mean is 1/2 and the variance is 1/4.
>>
>> ]I calculate the DFT, it means that I calculate
>>
>> ]c[m] = \sum_{k=0}^{n-1} b[k] * cos(2*pi*k*m/n) (1)
>>
>> ]the same for the sine.
>>
>> ]It is obvious that <c[m]> (the mean value) is
>>
>> ]<c[m]> = (1/2) \sum_{k=0}^{n-1} cos(2*pi*k*m/n)
>>
>> ]which is 0, but for m=0 it is n/2.
>>
>> ]For the variances I have
>>
>> ]Var(c[m]) = (1/4) \sum_{k=0}^{n-1} cos^2(2*pi*k*m/n) = n/8.
>>
>> ]The sum (1) is over n equilimited (we say "equilimitate", they are
>> values ]between -1 and +1) indipendent random variate. I can use the
>> central limit ]theorem.
>>
>> ]I know the mean and the variance, the theorem add only the fact that
>> the ]distribution become normal as n gets larger.
>>
>> ]So each c[m] is normal (but they are not indipendents).
>>
>> Yes, they are independent.
>> <c(m)c(n)>= sum_k sum_l <b(k)b(l)> cos(2 pi m k) cos( 2 pi n l)
>> = sum_k <b^2(k)> cos(2 pi m k)cos(2 pi n k)
>> =<b^2> sum_k [cos(2 pi (m+n) k) +cos(2 pi (m-n) k) ]/2
>> =0 unless m=n or m=-n
>> Similarly for the sine and teh cross ones.
>> I used that the bits are different positions are independent, and
>> that all of the positions have the same mean square (1/2 in your
>> system). Thus the correlations between different values are zero.
>
> As you know, my math skill is poor, so I sent your answer to the
> Italian mathematician to hear his thought.

I got his answer; hard translation...

To be honest, when I said they are not independent I had a doubt. But
strictly speaking I'm right. The question is a bit subtle.

Showing that the mean value of the product of two random variate is the
product of the mean values is just a needed condition for the independence,
but not sufficient.

You can easily see that they are not independent taking a small n, e.g. n=2.
For big n's the c[m] tend to be normal and for random variate normally
distributed the above condition is also sufficient.
Thus they are _not_ independent, but they are independent as n get bigger;
in other word, increasing n, the independence is stronger.

Cristiano