3 ms·

Can anyone describe in a nutshell how measures of randomness work? Every sequence generated by independent random choices is equally likely, right?

leksak 4y ago
They are equally likely, yes. But, the questions here pertain to whether or not an other person would perceive your sequence as random. It wasn't too long ago there was an article on HN (can't find it now) describing what feels random to people. Essentially, a sequence feels more random the harder it is to explain. So, HHHHHHHH doesn't feel random because it's summarized as 8 H's and HTHTHTHT doesn't feel random either because it is HT repeating. Strings that are only really communicable by repeating the string verbatim feel the most random.
- rmetzler 4y ago
  But if this is about perceived randomness shouldn’t people also guess which sequence was created by a human vs sequences created by some algorithm? I understand that to score randomness you probably would create n-grams of the characters and look if these would be equally distributed. But for such short sequences it feels hard to do. Maybe a statistician can explain this? For me, using my right thumb on a smartphone seems enough to skew the randomness. Just by doing it again with my index finger (after writing most of this comment), I raised it from being “more random” than 18% to 84%.
  - cormacrelf 4y ago
    'Perceived as random' seems like a pretty junk measure of other humans' efforts at producing randomness. Garbage in, garbage out. Surely analysing this tells you absolutely nothing about anything? I would understand if the actual measurement is not perceptual but mechanised, i.e. "how small can we compress this stream of random choices using our best known compression methods" or something. (But then a stream of 10 symbols is surely not enough to show you the humans.)
    - pseudo0 4y ago
      They link to a comprehensive description of the randomness score at the bottom of the page: https://www.complexitycalculator.com/HowItWorks.html https://www.complexitycalculator.com/HowItWorks.html It gets pretty theoretical, but basically it's estimating the Kolmogorov complexity by looking at the size of the Turing machine required to generate a particular string, rather than Shannon entropy or implementations of common compression techniques.
  - leksak 4y ago
    > But if this is about perceived randomness shouldn’t people also guess which sequence was created by a human vs sequences created by some algorithm? It's about what the test person think another human will perceive as random so there's a layer of indirection there. If these guesses you suggest would help the study or not I really can't say.
  - JusticeJuice 4y ago
    Yes the visual layout and input method is an interesting bias. If you imagine drawing a line between all choices on the number pad (which I do), I realised my answer avoided doubling-back on itself. My 'random' shape looked more like a nicely distributed squiggle, which is less random.
Closi 4y ago
The measure of randomness chosen in this particular paper appears to be an approximation of the Kolmogorov-Chaitin complexity adapted for small integer/binary sequences. This effectively looks at how easy it would theoretically be to compress/describe the data, for instance HHHHHHHHHH would be low complexity as it could be encoded as '10 H's'. If something is truly random, it shouldn't be possible to encode it due to the pigeon-hole principle. See http://www.scholarpedia.org/article/Algorithmic_complexity http://www.scholarpedia.org/article/Algorithmic_complexity
- Hendrikto 4y ago
  > If something is truly random, it shouldn't be possible to encode it due to the pigeon-hole principle. This statement is obviously untrue. “Random numbers” don’t really exists. The original authors were right about that. Every number/sequence is equally likely to occur. There’s even an XKCD about this [0]. I guess what you mean is: If you have a process that generates sequences randomly, most of those sequences are expected to compress badly. [0]: https://xkcd.com/221/ https://xkcd.com/221/
  - Closi 4y ago
    Yes, you are right on this one - I was 100% wrong and your corrected statement is right

leksak 4y ago

They are equally likely, yes. But, the questions here pertain to whether or not an other person would perceive your sequence as random. It wasn't too long ago there was an article on HN (can't find it now) describing what feels random to people. Essentially, a sequence feels more random the harder it is to explain. So, HHHHHHHH doesn't feel random because it's summarized as 8 H's and HTHTHTHT doesn't feel random either because it is HT repeating. Strings that are only really communicable by repeating the string verbatim feel the most random.

rmetzler 4y ago
But if this is about perceived randomness shouldn’t people also guess which sequence was created by a human vs sequences created by some algorithm? I understand that to score randomness you probably would create n-grams of the characters and look if these would be equally distributed. But for such short sequences it feels hard to do. Maybe a statistician can explain this? For me, using my right thumb on a smartphone seems enough to skew the randomness. Just by doing it again with my index finger (after writing most of this comment), I raised it from being “more random” than 18% to 84%.
- cormacrelf 4y ago
  'Perceived as random' seems like a pretty junk measure of other humans' efforts at producing randomness. Garbage in, garbage out. Surely analysing this tells you absolutely nothing about anything? I would understand if the actual measurement is not perceptual but mechanised, i.e. "how small can we compress this stream of random choices using our best known compression methods" or something. (But then a stream of 10 symbols is surely not enough to show you the humans.)
  - pseudo0 4y ago
    They link to a comprehensive description of the randomness score at the bottom of the page: https://www.complexitycalculator.com/HowItWorks.html https://www.complexitycalculator.com/HowItWorks.html It gets pretty theoretical, but basically it's estimating the Kolmogorov complexity by looking at the size of the Turing machine required to generate a particular string, rather than Shannon entropy or implementations of common compression techniques.
- leksak 4y ago
  > But if this is about perceived randomness shouldn’t people also guess which sequence was created by a human vs sequences created by some algorithm? It's about what the test person think another human will perceive as random so there's a layer of indirection there. If these guesses you suggest would help the study or not I really can't say.
- JusticeJuice 4y ago
  Yes the visual layout and input method is an interesting bias. If you imagine drawing a line between all choices on the number pad (which I do), I realised my answer avoided doubling-back on itself. My 'random' shape looked more like a nicely distributed squiggle, which is less random.

Closi 4y ago

The measure of randomness chosen in this particular paper appears to be an approximation of the Kolmogorov-Chaitin complexity adapted for small integer/binary sequences. This effectively looks at how easy it would theoretically be to compress/describe the data, for instance HHHHHHHHHH would be low complexity as it could be encoded as '10 H's'. If something is truly random, it shouldn't be possible to encode it due to the pigeon-hole principle. See http://www.scholarpedia.org/article/Algorithmic_complexity http://www.scholarpedia.org/article/Algorithmic_complexity

Hendrikto 4y ago
> If something is truly random, it shouldn't be possible to encode it due to the pigeon-hole principle. This statement is obviously untrue. “Random numbers” don’t really exists. The original authors were right about that. Every number/sequence is equally likely to occur. There’s even an XKCD about this [0]. I guess what you mean is: If you have a process that generates sequences randomly, most of those sequences are expected to compress badly. [0]: https://xkcd.com/221/ https://xkcd.com/221/
- Closi 4y ago
  Yes, you are right on this one - I was 100% wrong and your corrected statement is right