If $S$ is a finite set (such as outcomes of a dice). If I have a sequence $x_0 ... x_n$ of elements over $S$, how can I measure randomness quality of such a sequence as compared to measuring quality of random bits?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I've tried to enhance the quality of your question, including the info below the answer of Paul. Please check if the question is still correct. $\endgroup$– Maarten Bodewes ♦Commented Oct 13, 2019 at 13:33
-
2$\begingroup$ There is no such thing as randomness of a sample. Randomness is a property of a process that could produce any of various outcomes and you don't know which. Taken literally, this question is unanswerable: you can talk about randomness of a process (involving, e.g., physics), or tests of a sample to distinguish distributions, but not randomness of a sample. See, e.g., crypto.stackexchange.com/a/71437 for what I suspect you might mean to be asking about, and crypto.stackexchange.com/a/58132 for further discussion of what statistical hypothesis tests mean. $\endgroup$– Squeamish OssifrageCommented Oct 13, 2019 at 13:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
The simplest approach is the bias away from uniformity of the sequence, $\epsilon$. $P(x_n = \text{any member of S}) = \frac{1}{|S|} \pm \epsilon$. So a regular die has 6 possible outcomes and thus a cardinality of 6. Therefore in the case of a perfectly fair die, $P(x_n = \text{any member of S}) = \frac{1}{6} + 0.$
The USA's NIST organisation aims for $\epsilon = 2^{-64} $ when characterising a sequence as 'fully' random. And this leads to issues of mensuration as it's very difficult to generate and managed the amount of data needed for an accurate determination with such small bias.
We therefore resort to stochastic methods within acceptable bounds of certainty, like chi-square tests. To that end, see How many rolls do I need to determine if my dice are fair? Cryptographic tests typically use a confidence level of 0.1%.
answered Oct 13, 2019 at 12:17
-
$\begingroup$ Thanks, the Hypothesis of uniform randomness can be tested for the sequence taken as a sample. I think that is what you are suggesting. My problem arose for testing a sequence produced by practical generator whose output was over alphabets other than 0,1. Hence I need a test for measuring PRness over such alphabets. Not many tests were available other than sequences over 0,1. Rank test could be generalised but was not very accurate. I will highly appreciate more suggestions. $\endgroup$ Commented Oct 13, 2019 at 12:40
-
1$\begingroup$ @VirenSule Your posted question was quite short and seemed to look towards a theoretical understanding of randomness (eg. dice). Are you actually testing a large sample from a RNG impementation? $\endgroup$ Commented Oct 13, 2019 at 13:07
-
$\begingroup$ To Paul Uszak: Yes I am actually testing a sample from a PR generator which has different alphabet than {0,1}. $\endgroup$ Commented Oct 13, 2019 at 14:47