Live data from Hacker News

The cursed d65536

aleph.se

41–50 of 74 posts

Re: The cursed d65536

#41
post #22

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

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

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.

Re: The cursed d65536

#42

Earlier quoted context omitted.

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

I think the most likely cause of death in that case is being crushed by your d65536

I think that would be much less likely than being crushed by your d65538, given the premise.

Re: The cursed d65536

#43
post #7
post #2

I know it's not the point of TFA, but you can just roll a d8 6 times, generating 3 bits each time, for a total of 18 bits, and then discard two of them.

Why not just roll 4D16? https://www.amazon.com/Lanema-Polyhedral-Dungeons-Dragons-Si...

Are those dice fair?

Re: The cursed d65536

#44
Look at the humble d10 for inspiration. The trick is to avoid making a spherical-looking die. A fair d65536 could look like a pair of cones glued together, with 32768 sides per cone. Alternatively, one can make a fair 65536-sided cylinder with rounded ends.

Re: The cursed d65536

#45
post #22

Earlier quoted context omitted.

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

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-pos…

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?

Re: The cursed d65536

#46
post #45

Earlier quoted context omitted.

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-pos…

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?

No.

Re: The cursed d65536

#47
post #46
post #45

Earlier quoted context omitted.

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?

No.

Why? Is it because it haven't been found, or is there a proof of impossibility?

Re: The cursed d65536

#48
post #47
post #46

Earlier quoted context omitted.

No.

Why? Is it because it haven't been found, or is there a proof of impossibility?

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.

Re: The cursed d65536

#50
post #44

Look at the humble d10 for inspiration. The trick is to avoid making a spherical-looking die. A fair d65536 could look like a pair of cones glued together, with 32768 sides per cone. Alternatively, one can make a fair 65536-sided cylinder with rounded ends.

In practice though I'd go with four of those: https://commons.wikimedia.org/wiki/File:D16_HEX_dice.JPG (assuming that I can get them in four different colors)
Post reply on HN