5 ms·

I'm not sure what unbiased randomness is. I haven't heard that phrase before. For Kolmogorov randomness, I was using Wikipedia's description of it (https://en

I'm not sure what unbiased randomness is. I haven't heard that phrase before. For Kolmogorov randomness, I was using Wikipedia's description of it (https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogor...), although there are more technical descriptions available.

Retric 7y ago
Crypto cares a lot about unbiased randomness. X bits of entropy is kind of a measurement of this. Anyway, I suggest you reread the end of that paragraph: “A counting argument is used to show that, for any universal computer, there is at least one algorithmically random string of each length. Whether any particular string is random, however, depends on the specific universal computer that is chosen.” Kolmogorov complexity is really referring to the fact you can’t have lossless compression of arbitrary bit strings. You can’t encode every possible N+1 bit string using an N bit string. The computer chosen can make an arbitrary 1:1 mapping for any input though. So, it’s got nothing to do with randomness in the context of coin flipping as the mapping is predefined. Just remember, you’re choosing the computer and at that point any input can be mapped to any output. But, after that point limits show up.
- deleted 7y ago
  [deleted]
- xornox 7y ago
  If all "randomness" of the universe rises from a one extremely long bit string which has been created once from the source of true randomness, the bit string could contain unimaginable number of zeros only and it would be still random. For example, Lotto numbers 1,2,3,4,5,6,7 may be completely random. Kolmogorov complexity works only if we have a big sample of random numbers, but we do not know if we have such in this universe or not.
  - Retric 7y ago
    Kolmogorov complexity is only meaningful for a specific architecture. Without access to the architecture of the machine the universe runs on you can’t tell if the initial random string would be one bit or nigh infinite bits.
rerefreshment 7y ago
I haven’t really heard much talk about “Kolmogorov randomness” before, and so I’m wondering if you might be running up against the limits of the Wikipedia paradigm when it comes to pioneering scholarship. The citation for that paragraph is a peer-reviewed journal article covering Kolmogorov complexity and randomness. It’s actually a really good article, by someone pretty famous named Per Martin-Löf. Which is all great, except that paper is from 1966, and in 2019 a more studied concept is something called “Martin-Löf randomness” :)

Retric 7y ago

Crypto cares a lot about unbiased randomness. X bits of entropy is kind of a measurement of this. Anyway, I suggest you reread the end of that paragraph: “A counting argument is used to show that, for any universal computer, there is at least one algorithmically random string of each length. Whether any particular string is random, however, depends on the specific universal computer that is chosen.” Kolmogorov complexity is really referring to the fact you can’t have lossless compression of arbitrary bit strings. You can’t encode every possible N+1 bit string using an N bit string. The computer chosen can make an arbitrary 1:1 mapping for any input though. So, it’s got nothing to do with randomness in the context of coin flipping as the mapping is predefined. Just remember, you’re choosing the computer and at that point any input can be mapped to any output. But, after that point limits show up.

deleted 7y ago
[deleted]
xornox 7y ago
If all "randomness" of the universe rises from a one extremely long bit string which has been created once from the source of true randomness, the bit string could contain unimaginable number of zeros only and it would be still random. For example, Lotto numbers 1,2,3,4,5,6,7 may be completely random. Kolmogorov complexity works only if we have a big sample of random numbers, but we do not know if we have such in this universe or not.
- Retric 7y ago
  Kolmogorov complexity is only meaningful for a specific architecture. Without access to the architecture of the machine the universe runs on you can’t tell if the initial random string would be one bit or nigh infinite bits.

rerefreshment 7y ago

I haven’t really heard much talk about “Kolmogorov randomness” before, and so I’m wondering if you might be running up against the limits of the Wikipedia paradigm when it comes to pioneering scholarship. The citation for that paragraph is a peer-reviewed journal article covering Kolmogorov complexity and randomness. It’s actually a really good article, by someone pretty famous named Per Martin-Löf. Which is all great, except that paper is from 1966, and in 2019 a more studied concept is something called “Martin-Löf randomness” :)