Re: FFT test with few kbits
From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 02/24/04
- Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Previous message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- In reply to: Ernst Lippe: "Re: FFT test with few kbits"
- Next in thread: Ernst Lippe: "Re: FFT test with few kbits"
- Reply: Ernst Lippe: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Tue, 24 Feb 2004 21:33:12 GMT
Ernst Lippe wrote:
> On Mon, 23 Feb 2004 12:58:07 +0000, Cristiano wrote:
>
>> Cristiano wrote:
>>> Bill Unruh wrote:
>>>> 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.
>
> Yes, it is. Bill was referring to the fact that they are not linearly
> correlated, which is, as you correctly noted, a different notion.
>
>> 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,
> (The standard english mathematical term is "necessary" condition)
Thank you for the correction.
>> but not sufficient.
> OK!
>
>> 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.
>
> I am feeling a bit uncomfortable with this sentence.
> First of all, the standard statistical definition of
> independence is a pure black-and-white one, two random variables
> are either independendent or they are not independent. As
> far as I know there is not really a standard measure for the
> "degree of independence".
I agree.
> In one of my previous post I more or less suggested an
> ad-hoc measure of the "degree of independence" based on
> entropy, and I argued that according to this measure
> two different Fourier components are actually what
> you would call highly dependent.
Yes.
> Your statement at
> least suggests that when N becomes very big the
> dependence between two Fourier components becomes
> small.
Yes, "very big" for my test seems to be even 50 or 100 bits.
> In the example that I gave when N is a prime
> the degree of dependence will be high even when
> N becomes very large (and I expect that you will find
> similar results for the case that N is not prime, they
> are just somewhat harder to analyze).
Perhaps too hard. :-)
> So, in order to give a mathematical interpretation to
> your notion of "independence" we should first have
> some way to quantify it, and even when you select
> such a measure, I am not all that certain that it
> is true that the "independence" become really larger
> when N gets larger.
Many times (perhaps all the times) to see if a test is good, one should
tests the test using a good generator (which is one with a good proof).
Strictly speaking, we know that the components are not independent, but this
kind of dependence is somehow reduced when N is "big".
I posted the proof for the mean, the proof for the variance and the proof
for the normal distribution.
Now there is just the academic disquisition about the real independece of
the components.
Well, looking at the results I get with several (p)rng and having the above
proofs, I think my test has solid basis to be used with great confidence.
The real strangeness still open (which need to be fixed) is the non-uniform
distribution of the p-values gotten from the real components. I'm really not
able to find an explanation for that.
Cristiano
- Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Previous message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- In reply to: Ernst Lippe: "Re: FFT test with few kbits"
- Next in thread: Ernst Lippe: "Re: FFT test with few kbits"
- Reply: Ernst Lippe: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
