+\documentclass{article}
+
+\title{Using complexity of short strings to define new statistical tests for PRNGs}
+
+
+\begin{document}
+\maketitle
+
+
+\begin{abstract}
+blabalbabla
+\end{abstract}
+
+
+\section{Introduction}
+
+\section{Algorithmic complexity for short strings}
+
+In their paper, they introduced a method to compute the complexity of $D(n)$.
+With D(4), 5 970 768 960 machines halt. There are 1832 different strings.
+
+\section{Property: a PRNG must preserve the distribution of short strings}
+
+In this section, we propose to measure the quality of a PRNG by considering that
+a good PRNG must preserve the distribution of short strings. More precisely, the
+pseudo-random numbers obtained by a PRNG can form the states of the Rado's
+original Busy Beaver. Then, machines obtained by such a construction can be
+executed and if the PRNG is good, machines should generate the same strings with
+the same distribution than the theoretical Busy Beaver (with all the enumeration
+of states). In practice, PRNGs will not generate all the strings with exactly
+the same probabilities. Nevertheless, the distance between the theoretical
+probabibilities and the obtained probabilities with a PRNG is a good indication
+of the quality of the PRNG.
+
+In the following we report our experiments. Let $S(n)_i$ be the string number
+$i$ obtained by the busy beaver $D(n)$, $S(n)$ is the set of strings of
+$D(n)$. With $D(4)$ there are 1832 strings, so $|S(4)|=1832$. $N_{bb}(S(n)_i)$ is
+the number of occurrences of the string $S(n)_i$ obtained by the Busy Beaver and $N_{PRNG}(S(n)_i)$ is the
+number of occurrences of the string $S(n)_i$ obtained with the execution of a given
+PRNG. In order to measure the distance between the theoretical result and the
+pratical one, we use this measure:
+\begin{equation}
+Dist(PRNG,BB)=\sum_{i=1}^{|S(n)|} \frac{|N_{bb}S(n)_i-N_{PRNG}S(n)_i|}{N_{bb}S(n)_i}
+\end{equation}
+
+Here are the result for some PRNGS: bbs, lcg, xor128, rand, xorshift, devrandom,
+newprng, isaac. These results are reported for experiments with different
+numbers of random number generation.
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+ & Number of experiments\\
+\hline
+Name of PRNG & 500,000,000\\
+\hline
+lcg & 491.78\\
+\hline
+rand & 382.04\\
+\hline
+xor128 & 380.69\\
+\hline
+dev random & 376.78\\
+\hline
+xorshift & 372.68\\
+\hline
+new prng & 367.42\\
+\hline
+isaac & 366.91\\
+\hline
+BBS & 358.38\\
+\hline
+
+\end{tabular}
+\caption{Distance for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+ & Number of experiments\\
+\hline
+Name of PRNG & 500,000,000\\
+\hline
+lcg & 2652694\\
+\hline
+rand & 1511.34\\
+\hline
+xor128 & 1489.53\\
+\hline
+dev random & 1477.99\\
+\hline
+xorshift & 1474.00\\
+\hline
+BBS & 1403.50\\
+\hline
+isaac & 1397.28\\
+\hline
+new prng & 1356.76\\
+\hline
+
+\end{tabular}
+\caption{Chi squared for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+ & Number of experiments\\
+\hline
+Name of PRNG & 50,000,000\\
+\hline
+lcg & 1191.87\\
+\hline
+rand & 1187.18\\
+\hline
+xorshift & 1257.87\\
+\hline
+new prng & 1210.77\\
+\hline
+dev random & 1190.33\\
+\hline
+xor128 & 1190.11\\
+\hline
+isaac & 1188.74\\
+\hline
+BBS & 1185.77\\
+\hline
+
+\end{tabular}
+\caption{Distance for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+ & Number of experiments\\
+\hline
+Name of PRNG & 50,000,000\\
+\hline
+lcg & 2664408\\
+\hline
+xorshift & 14904.91\\
+\hline
+new prng & 14711.53\\
+\hline
+dev random & 14189.61\\
+\hline
+BBS & 13857.77\\
+\hline
+isaac & 13933.8\\
+\hline
+xor128 & 13426.15\\
+\hline
+rand & 13339.74\\
+\hline
+
+\end{tabular}
+\caption{Chi squared for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+
+
+\end{document}
