4 ms·
The process has exactly zero chance of never terminating in the usual probability space of infinite strings with iid characters, even though the set of strings
by mananaysiempre 4y ago
The process has exactly zero chance of never terminating in the usual probability space of infinite strings with iid characters, even though the set of strings (of RNG results) on which it does not terminate is nonempty (uncountably infinite, even, provided N ≥ M + 2); the term of art is that it terminates almost surely. An alternative definition is that you can throw out these strings from the space and no well-posed question of probability (as opposed to set) theory will get a different answer. They’re gremlins, essentially, except for the part where an (uncountably) infinite union of gremlin (null) sets may not yield a gremlin set.
(The usual definition of that space via “cylinder sets” may seem contrived, but it’s usually introduced first because it’s “elementary” in that it does not require developing the machinery of limits of [not in] probability spaces. Those can be made to work, though, and then you can say that the space of infinite strings is the limit of the spaces of length-n strings for n → ∞ and obtain the same thing. In fact, the cylinder-set definition is essentially the limit definition with the notion of limit inlined.)
- ffhhj 4y agoIs there some method to determine whether a sequence of numbers, being generated from a black-box, reaches a point at which we can confidently say it's a random sequence?
- krapp 4y agoNo.
- ffhhj 4y agoWhy? Is it because it haven't been found, or is there a proof of impossibility?
- krapp 4y agoAny conceivable sequence could theoretically be generated by randomness. A perfect random number generator could generate a list of social security numbers or an infinite sequence of zeros. Likewise any sequence that appears random may just have a pattern which hasn't emerged from what has observed.
- lmm 4y agoIt would require P=NP (widely assumed to be false) and the nonexistence of one-way functions (actually an even stronger assumption). Any one-way function can be used as a PRNG, and it's computationally infeasible to distinguish that from a true random number generator, almost by definition.
- orangecat 4y agoAssuming "random" means that there is no program to generate the sequence that is shorter than the sequence itself, proving the nonexistence of such a program is equivalent to the halting problem. See https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
- Someone 4y agoIf you observe a black box producing a sequence N items, you can’t know whether it will, after that, repeat the same sequence at infinitum (it might just contain a circular tape of N items, for example), or keep producing a single identical item, or keep producing only two different items, etc.