How is the statistic of autocorrelation test for randomness arrived at?
in [Cryptography]
|
Prev: How is the statistic of autocorrelation test for randomness arrivedat?
Next: How is the statistic of autocorrelation test for randomness arrived at?
From: David Sexton on 4 Apr 2010 16:55 On Apr 3, 3:36 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > The test statistic of the autocorreoation test for randomness > (see HAC, p.182, X_5) is claimed to approximately follow an N(0,1) > distribution if n-d>=10. I couldn't find any detailed explanation > of this in a dozen of statistic textbooks accessible to me that are > relevant to the issue. Could some expert kindly help? > > Thanks in advance. > > M. K. Shen Doesn't the statistic equal the number of standard deviations above population mean? That makes sense because the example gives a threshold of 1.96 for a 0.05 level of significance. These numbers (according to the text) come from Table 5.1. Table 5.1 is "Selected Percentiles of the Standard Normal Distribution." David
From: WTShaw on 7 Apr 2010 04:15 On Apr 4, 4:29 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > David Sexton wrote: > > Doesn't the statistic equal the number of standard deviations above > > population mean? > > > That makes sense because the example gives a threshold of 1.96 for a > > 0.05 level of significance. These numbers (according to the text) > > come from Table 5.1. Table 5.1 is "Selected Percentiles of the > > Standard Normal Distribution." > > Sorry for my poor comprehension. Could you explain a bit more how > (why) the A(d), which is the xor of the bits at distance d, goes in that > "specific" form into the formaula for the stated test statistic there? > > M. K. Shen It must be because it looked like a secure form of magic when drawn on a chalkboard.
From: David Sexton on 7 Apr 2010 12:56
On Apr 4, 2:29 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > David Sexton wrote: > > Doesn't the statistic equal the number of standard deviations above > > population mean? > > > That makes sense because the example gives a threshold of 1.96 for a > > 0.05 level of significance. These numbers (according to the text) > > come from Table 5.1. Table 5.1 is "Selected Percentiles of the > > Standard Normal Distribution." > > Sorry for my poor comprehension. Could you explain a bit more how > (why) the A(d), which is the xor of the bits at distance d, goes in that > "specific" form into the formaula for the stated test statistic there? > > M. K. Shen For that test I would use, and have used, a chi-squared statistic. Nevertheless, I should be able to remember what this one-sided test statistic is called. I don't. I'll keep thinking about it and looking around; it bothers me that I can't remember. In the mean time.... The probablility that a bit in will be different than another bit in the sequence at a given offset should be 0.5. In the formula, (n - d) is the number of bits considered. There are no bits at offset "d" with which to xor the other "d" bits in the sequence, which is "n" bits long. So, (n - d) bits all have a 0.5 probability of being 1. The "expected" number of 1s is (n - d) / 2. A(d) - (n - d)/2 is the difference between the observed number of 1s and the expected number of 1s. The whole statistic must be equal to the number of standard deviations away from (n - d)/2 of A(d). The test depends on the fact that, for a large number of trials, the binomial distribution approximates the normal (Gaussian) distribution. David |