3. ( 1 ) Linear Congruential Generator:LCG 6) (Mersenne Twister:MT ), L 1 ( 2 ) 4 4 G (i,j) < G > < G 2 > < G > 2 g (ij) i= L j= N

Size: px

Start display at page:

Download "3. ( 1 ) Linear Congruential Generator:LCG 6) (Mersenne Twister:MT ), L 1 ( 2 ) 4 4 G (i,j) < G > < G 2 > < G > 2 g (ij) i= L j= N"

まいかいちぞの
5 years ago
Views:

1 RMT 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) Vasiliki Plerou ) L 1. N L N N N 1 1 λ + λ P RMT Q 4)5) P RMT (λ) = Q (λ+ λ)(λ λ ) (1) 2πλ λ ± = 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

2 3. ( 1 ) Linear Congruential Generator:LCG 6) (Mersenne Twister:MT ), L 1 ( 2 ) 4 4 G (i,j) < G > < G 2 > < G > 2 g (ij) i= L j= 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 P RMT Q N L L N 2 c 2011 Information

3 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 L 4.2 LCG LCG 9 =500 =1500 Q 3 X n+1 = (ax n + b)modm (7) a b M a= /65536 b=12345/65536 M= =3 4.3 MT MT 7) HP MT 8) LCG LCG 5 LCG =3 4.4 Box-Muller 2 B-M LCG MT Box-Muller 6 6 =100 = LCG Box-Muller 5 1 [λ λ +] Box-Muller 6. L N 3 c 2011 Information

4 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 [λ λ +] 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 [λ λ + ] MT LCG MT RMT-PCA Fig. 9 Evaluation of LCG(left) and MT(right) by RMT-PCA 4 c 2011 Information

5 Table 1 Table 2 1 LCG Comparision of the logarithmic rang and theoretical of eigenvector(lcg) Q min max Q= Q= Q= Q= Q= Q= Q= Q= Q= MT Comparision of the logarithmic rang and theoretical of eigenvector(mt) Q min max Q= Q= Q= Q= Q= Q= Q= Q= Q= ) 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) FIT pp (2010).. 3) Laloux, L., Cizeaux, P., Bouchaud, J. and Potters, M.: Noise Dressing of Financial Correlation Matrices, Physical Review Letters, Vol.83, pp (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 (1994). 5) Sengupta, A. and Mitra, P.: Distribution of Singular Values for Some Random Matrices, Physical Review E, Vol.60, pp (1999). 6) Park, S. and Miller, K.: Random Number Generators: Good Ones are Hard to Find, Communication of ACM, Vol.31, pp (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) LCG MT LCG MT RTM 5 c 2011 Information

情報処理学会研究報告 IPSJ SIG Technical Report Vol.2012-MPS-88 No /5/17 RMT テストの性能検証 ~NIST 乱数検定との比較 ~ 三賀森悠大 1,a) 楊欣 1 糸井良太 1 田中美栄子 1,b) 概要 : 我々が以前に提案した,R

情報処理学会研究報告 IPSJ SIG Technical Report Vol.2012-MPS-88 No /5/17 RMT テストの性能検証 ~NIST 乱数検定との比較 ~ 三賀森悠大 1,a) 楊欣 1 糸井良太 1 田中美栄子 1,b) 概要 : 我々が以前に提案した,R RMT テストの性能検証 ~NIST 乱数検定との比較 ~ 三賀森悠大,a) 楊欣糸井良太田中美栄子,b) 概要 : 我々が以前に提案した,RMT との比較による乱数度計測法, すなわち RMT テストの誤差基準を NIST 検定との比較によって再考察した結果を報告する. 様々な乱数度の数列を用意するため, 完全規則列から出発してそれにシャッフルをかけることにより, 異なる乱数度のデータ列を作成し,RMT