5 ms·

This process has an infinitely small (but non-zero) chance of never terminating.

kazinator 4y ago
The die also has a very small chance of landing on an edge between two faces, which also requires a repeated roll.
davidgay 4y ago
But that probability rapidly drops below the probability that you will drop dead from some random cause while waiting for the roll's result :)
- phinnaeus 4y ago
  I think the most likely cause of death in that case is being crushed by your d65536
  - a1369209993 4y ago
    I think that would be much less likely than being crushed by your d65538, given the premise.
Smaug123 4y ago
This is a rather sloppy way of saying "this process may fail to terminate, though the set of nonterminating outcomes has probability 0". No real number is infinitely small but nonzero.
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 ago
  Is 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 ago
    No.
    - ffhhj 4y ago
      Why? Is it because it haven't been found, or is there a proof of impossibility?
      - krapp 4y ago
        Any 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 ago
        It 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 ago
        Assuming "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 ago
        If 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.
Dylan16807 4y ago
Which doesn't matter on objects or programs because that chance already exists as a baseline. I'm not building a math here.
a1369209993 4y ago
Actually, it doesn't. If you're working with real numbers, then your step counter is a natural number, you repeat for[2] infinitely many steps, and the probability of failure is exactly zero. If, on the hand, you're working with surreal numbers - which you would have to be for "infinitely small (but non-zero)" to make sense - then your step counter is a ordinal number[1], not a natural, and you repeat for[2] non-well-foundedly many steps (one for each ordinal), after which the probability of failure is again exactly zero. (Otherwise it would be the reciprocal of some surreal number, that is less than some ordinal, and for any ordinal, you can show that you tried a well-founded number of times that is nonetheless strictly greater than it.[0]) The more existent problem is that you can't put any useful upper bound on how many rerolls you'll need, which is terrible for constant-time algorithms, and particularly for cryptography. 0: And you actually only need two to the power of the number of tries to be greater, since the failure probability of one sample is at most 1/2, so the probability after K tries is at most 1/2^K. 1: ie, a positive whole surreal number, rather than a positive whole real number 2: Technically, you repeat for up to but not including that many, since you're guaranteed to terminate by then.
- a1369209993 4y ago
  > ordinal number[1] > 1: ie, a positive whole surreal number, rather than a positive whole real number Actually, ordinals have some additional contraints besides just "positive" and "whole" (eg ω−1 is not a ordinal), that just reduce to "positive whole" in the case of reals, although that doesn't change the actual point any.

The die also has a very small chance of landing on an edge between two faces, which also requires a repeated roll.

But that probability rapidly drops below the probability that you will drop dead from some random cause while waiting for the roll's result :)

phinnaeus 4y ago
I think the most likely cause of death in that case is being crushed by your d65536
- a1369209993 4y ago
  I think that would be much less likely than being crushed by your d65538, given the premise.

Smaug123 4y ago

This is a rather sloppy way of saying "this process may fail to terminate, though the set of nonterminating outcomes has probability 0". No real number is infinitely small but nonzero.

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 ago
Is 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 ago
  No.
  - ffhhj 4y ago
    Why? Is it because it haven't been found, or is there a proof of impossibility?
    - krapp 4y ago
      Any 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 ago
      It 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 ago
      Assuming "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 ago
      If 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.

Dylan16807 4y ago

Which doesn't matter on objects or programs because that chance already exists as a baseline. I'm not building a math here.

a1369209993 4y ago

Actually, it doesn't. If you're working with real numbers, then your step counter is a natural number, you repeat for[2] infinitely many steps, and the probability of failure is exactly zero. If, on the hand, you're working with surreal numbers - which you would have to be for "infinitely small (but non-zero)" to make sense - then your step counter is a ordinal number[1], not a natural, and you repeat for[2] non-well-foundedly many steps (one for each ordinal), after which the probability of failure is again exactly zero. (Otherwise it would be the reciprocal of some surreal number, that is less than some ordinal, and for any ordinal, you can show that you tried a well-founded number of times that is nonetheless strictly greater than it.[0]) The more existent problem is that you can't put any useful upper bound on how many rerolls you'll need, which is terrible for constant-time algorithms, and particularly for cryptography. 0: And you actually only need two to the power of the number of tries to be greater, since the failure probability of one sample is at most 1/2, so the probability after K tries is at most 1/2^K. 1: ie, a positive whole surreal number, rather than a positive whole real number 2: Technically, you repeat for up to but not including that many, since you're guaranteed to terminate by then.

a1369209993 4y ago
> ordinal number[1] > 1: ie, a positive whole surreal number, rather than a positive whole real number Actually, ordinals have some additional contraints besides just "positive" and "whole" (eg ω−1 is not a ordinal), that just reduce to "positive whole" in the case of reals, although that doesn't change the actual point any.