RMT 1 1 1 N L Q=L/N (RMT), RMT,,,., Box-Muller, 3.,. Testing Randomness by Means of RMT Formula Xin Yang, 1 Ryota Itoi 1 and Mieko Tanaka-Yamawaki 1 Random matrix theory derives, at the limit of both dimension N and length of sequences L going to infinity, that the eigenvalue distribution of the cross correlation matrix between time series with high random nature can be expressed by a simple function of Q=L/N. Using this fact, we propose a new method of testing randomness of a given sequence. Namely, the randomness of a sequence passes the test if the eigenvalue distribution of the cross correlation matrix matches the RMT formula. We have applied this method on two machine-generated random numbers, the linear congruential generator(lcg) and the Mersenne Twister(MT). Both cases passed the test. 1. Random Matrix Theory:RMT 1)2) RMT RMT-PCA 3) 2. 2.1 Vasiliki Plerou 2002 1) L 1. N L N N N 1 1 λ + λ P RMT Q 4)5) P RMT (λ) = Q (λ+ λ)(λ λ ) (1) 2πλ λ ± = 1 + 1 Q ± 1 Q Q = L N 2.2 (2) (3) 1 Tottori University, Graduate School of Engineering,Department of Information and Electronics 1 c 2011 Information
3. ( 1 ) Linear Congruential Generator:LCG 6) (Mersenne Twister:MT ), 1 2... L 1 ( 2 ) 4 4 G (i,j) < G > < G 2 > < G > 2 g (ij) i=1 2... L j=1 2... N 5 6 G (i,j) < G > g (i,j) = (4) < G2 > < G > 2 G = g 1(1) g 1(N)....... g L(1) g L(N) C = 1 L GGT (6) ( 3 ) ( 4 ) (5) 1 Fig. 1 Data Type 2 3 Fig. 2 Example of High Randomness Fig. 3 Example of Low Randomness 2 3 4. 4.1 P RMT Q N L L N 2 c 2011 Information
Fig. 4 4 LCG Example of Evaluation by LCG Fig. 5 5 MT Example of Evaluation by MT 6 Box-Muller N 0 1 N 5 1 Fig. 6 Result of Randomness by Box-Muller N(0,1)(left) and N(5,1)(right) Q 1 Q 2 3... 10 L 4.2 LCG LCG 9 =500 =1500 Q 3 X n+1 = (ax n + b)modm (7) a b M a=1103515245/65536 b=12345/65536 M=32768 4 =3 4.3 MT MT 7) 2 19937 1 HP MT 8) LCG LCG 5 LCG =3 4.4 Box-Muller 2 B-M LCG MT Box-Muller 6 6 =100 =300 0 1 LCG Box-Muller 5 1 [λ λ +] Box-Muller 6. L N 3 c 2011 Information
5. 7 LCG Fig. 7 Evaluation of LCG Initial Data 5.1 LCG MT 5.2 LCG 5.3 RMT-PCA LCG MT RMT-PCA 9 N 500 L N 3 1500 [λ λ +] 1 2 1.2 Fig. 8 8 LCG 500 MT Evaluation Result of Discard of LCG s Initial 500 NUM.(left) and MT(right) 4.5 LCG LCG 7 7 =100 =500 [λ λ + ] 500 8. MT 500 8 9 LCG MT RMT-PCA Fig. 9 Evaluation of LCG(left) and MT(right) by RMT-PCA 4 c 2011 Information
Table 1 Table 2 1 LCG Comparision of the logarithmic rang and theoretical of eigenvector(lcg) Q min max Q=2 0.05 3.48 3.42 2.82 Q=3 0.11 2.90 2.78 2.30 Q=4 0.18 2.57 2.39 2 Q=5 0.23 2.38 2.14 1.78 Q=6 0.27 2.24 1.96 1.63 Q=7 0.31 2.12 1.81 1.51 Q=8 0.34 2.04 1.70 1.41 Q=9 0.37 1.97 1.60 1.33 Q=10 0.39 1.90 1.50 1.26 2 MT Comparision of the logarithmic rang and theoretical of eigenvector(mt) Q min max Q=2 0.04 3.47 3.43 2.82 Q=3 0.11 2.91 2.80 2.30 Q=4 0.18 2.60 2.41 2 Q=5 0.23 2.38 2.15 1.78 Q=6 0.27 2.24 1.96 1.63 Q=7 0.31 2.13 1.82 1.51 Q=8 0.34 2.04 1.70 1.41 Q=9 0.37 1.97 1.60 1.33 Q=10 0.39 1.88 1.49 1.26 1) Plerou, V., Gopikrishnan, P., Rosenow, B., Amaral, L. and Stanley, H.: Random Matrix Approach to Cross Correlation in Fianancial Data, Physical Review E, Vol.65 (2002). 2) FIT2010 9 pp.153 156 (2010).. 3) Laloux, L., Cizeaux, P., Bouchaud, J. and Potters, M.: Noise Dressing of Financial Correlation Matrices, Physical Review Letters, Vol.83, pp.1467 1470 (1998). 4) Marcenko, V. and Pastur, L.: Distribution of Eigenvalues for Some Sets of Random Matrices, Mathematics of the USSR-Sbornik, Vol.1-(4), pp.457 483 (1994). 5) Sengupta, A. and Mitra, P.: Distribution of Singular Values for Some Random Matrices, Physical Review E, Vol.60, pp.3389 3392 (1999). 6) Park, S. and Miller, K.: Random Number Generators: Good Ones are Hard to Find, Communication of ACM, Vol.31, pp.1192 1201 (1988). 7) Matsumoto, M. and Nishimura, T.: Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudorandom Number Generator, ACM Transactions on Modeling and Computer Simulation, Vol.8, pp.3 30 (1998). 8) Tamura, Y.: Random Number Library (2010). http://random.ism.ac.jp/random. 6. LCG MT LCG MT RTM 5 c 2011 Information