Testing PRNG w/ Chi-Squared & Kolmogorov-Smirnov Tests

  • Thread starter anachin6000
  • Start date
  • Tags
    Testing
In summary, the conversation discusses the use of The Chi-Squared test and The Kolmogorov-Smirnov Test to test a physical RNG, specifically for n=1000. However, there is no set of values for n=1000 and a formula is used instead, which includes a -O(1/n) term that causes trouble. Big O notation is explained as a way to approximate functions and ignore constant coefficients, and is also used in computer science to analyze algorithm efficiency.
  • #1
anachin6000
51
3
I was developing a physical RNG and I was trying to test it using The Chi-Squared test and The Kolmogorov-Smirnov Test. The latter gives me some problems.
I have an attached photo with a table. In the table, n is the number of generated numbers. The book says that the test should be run for n=1000. I've made a program that calculates the K parameters and I should compare them with values from the table. There is no set of values for n=1000, but there is a formula in the table to continue to calculate values.
In the formula, there is a -O(1/n) that troubles me. I reversed the formula to get -O(1/n) from the data in the table, but it makes no sense.
 

Attachments

  • Screenshot (55).png
    Screenshot (55).png
    44 KB · Views: 394
Last edited:
Physics news on Phys.org
  • #2
The values from the formula are wrong by something that is probably of the order of 0.001. Mathematically O(1/n) doesn't guarantee that, but it won't be significantly larger.
You can probably ignore it, or include it as conservative estimate in the direction that hurts you.
 
  • Like
Likes anachin6000
  • #3
Big O notation is used to indicate that a formula or equation is just an approximation, and the O(x) tells you an asymptotic bound on the size of the error in the approximation. Usually, you see this when the approximation is some kind of series expansion for a transcendental function, and the series has been cut off at some point.
e.g.
##exp(x) = 1 + x + x^2/2 + O(x^3)##
This approximation is valid for |x| << 1. When |x| < 1, higher powers like ##x^4, x^5## are smaller than ##x^3##. So, we say the error bound is O(x^3) and absorb all the smaller higher order terms into the largest error. The big O notation ignores constant coefficients because we don't care about that level of detail when working with asymptotic behavior. Really, we are only interested something even coarser than an order of magnitude.

For x > 1, it isn't correct to absorb terms like x^4, x^5, ... into the error of the x^3 term since these higher terms get bigger, not smaller. It doesn't make sense to do a series approximation in terms of increasing powers. But for some functions, you can do a series approximation in terms of decreasing powers (1/x, 1/x^2, 1/x^3 ...). In this case, you can write something like f(x) = g(x) + c/x + O(1/x^2).
All the higher terms get absorbed into O(1/x^2).

It sounds kind of wishy washy, but there is a rigorous formality to it.
 
  • Like
Likes anachin6000
  • #4
Big O notation is also used in computer science to talk about the time or memory used by an algorithm as we scale the problem size. Basically, we want algorithms that scale well, like O(n) or O(n log n), and not like O(2^n) which is basically means we will never be able to use this algorithm for a large size of n, no matter how fast our computers get.
 
  • Like
Likes anachin6000

FAQ: Testing PRNG w/ Chi-Squared & Kolmogorov-Smirnov Tests

1. What is PRNG and why is it important in scientific testing?

PRNG stands for Pseudorandom Number Generator, which is a computer algorithm used to generate a sequence of numbers that appear to be random but are actually determined by a starting value called a seed. PRNG is important in scientific testing because it allows for the creation of repeatable and controlled experiments, which is crucial for accurate and reliable results.

2. What is the Chi-Squared test and how is it used to test PRNG?

The Chi-Squared test is a statistical test used to determine whether there is a significant difference between observed data and expected data. In the context of testing PRNG, the Chi-Squared test is used to compare the frequency of generated numbers to the expected frequency of a truly random sequence. If there is a significant difference, it suggests that the PRNG may not be truly random.

3. What is the Kolmogorov-Smirnov test and how does it differ from the Chi-Squared test?

The Kolmogorov-Smirnov (KS) test is another statistical test used to determine the randomness of a sequence. It measures the maximum difference between the cumulative distribution function of the observed data and the expected distribution function. Unlike the Chi-Squared test, the KS test does not require the expected frequencies to be known, making it a more flexible tool for testing PRNG.

4. What are some limitations of using Chi-Squared and Kolmogorov-Smirnov tests to test PRNG?

One limitation is that these tests can only detect certain types of non-randomness and may not be able to identify more subtle patterns in the sequence. Additionally, the results of these tests can be influenced by the sample size and the selection of significance level, so it is important to carefully consider these factors when interpreting the results.

5. How can the results of PRNG testing with Chi-Squared and Kolmogorov-Smirnov tests be used in scientific research?

The results of PRNG testing can provide valuable insights into the quality and reliability of the generated data, which is important in many scientific research fields. If the PRNG is found to be non-random, it may be necessary to use a different algorithm or to implement additional measures to ensure the randomness of the data. This can help improve the accuracy and validity of research findings.

Back
Top