Random Number Generation Tests of NIST Test Suite

• 15 tests, and a number of tests in the test suite have the standard normal and the chi-square as reference distributions.
• For each applied test, a decision or conclusion is derived that accepts or rejects the null hypothes is, i.e., whether the generator is (or is not) producing random values, based on the sequence that was produced.
• From this reference distribution, a critical value
  is determined (typically, this value is "far out" in the tails of the distribution, say out at the 99 % point). During a test, a test statistic value is computed on the data (the sequence being tested). This test statistic value is compared to the critical value. If the test statistic value exceeds the critical value, the null hypothesis for randomness is rejected. Otherwise, the null hypothesis (the randomness hypothesis) is not rejected (i.e., the hypothesis is accepted
• 1-3 & 1-4

1. Frequency (Monobits) Test
2. Frequency Test within a Block
3. Runs Test
4. Test for the Longest Run of Ones in a Block
5. Binary Matrix Rank Test
6. Discrete Fourier Transform (Specral) Test
7. Non-Overlapping Template Matching Test
8. Overlapping Template Matching Test
9. Maurer’s “Universal Statistical” Test
10. Linear Complexity Test
11. Serial Test
12. Approximate Entropy Test
13. Cumulative Sums (Cusum) Test
14. Random Excursions Test
15. Random Excursions Variant Test

基礎知識

1. Null hypothesis
   假設兩個檢測的現象並無關聯

Runs Test for Detecting Non-randomness

檢測一序列是否由隨機的方法產生

• run : 一串連續遞增或遞減的數列
  • value : 這個 run 的值是它的長度，也就是含括的數字個數；value 在平均值(median)之上的話，定義為正，反之則定義為負
  • probability : the (I+1)th value is larger or smaller than the Ith value follows a binomial distribution, which forms the basis of the runs test.
• H0 : 由隨機的方法產生的序列
• Ha : 不是由隨機的方法產生的序列
• 計算方法
  
• Significance Level : α ?
• Critical Region : The runs test rejects the null hypothesis if
  

檢測步驟

1. 計算有幾個 runs 在我們的 data (sequence) 裡面

參考資料

1. YW's Homepage
2. Runs Test for Detecting Non-randomness

https://onlinecourses.science.psu.edu/stat414/node/330
https://en.wikipedia.org/wiki/Statistical_randomness
https://softwareengineering.stackexchange.com/questions/147134/how-should-i-test-randomness

http://www.cse.wustl.edu/~jain/cse567-08/ftp/k_27trg.pdf
http://web.stanford.edu/~kknair/pdf/Allen_pap.pdf
http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf

https://blog.gisonrg.me/2017/03/Unix-numeric-sort-implementation-in-Java/