4 ms·
>Think of a series of random bits that can be either 0 or 1 with equal probability. How likely is it that they are all 0 or all 1? Not very likely. There is exa
by coldtea 5y ago
>Think of a series of random bits that can be either 0 or 1 with equal probability. How likely is it that they are all 0 or all 1? Not very likely. There is exactly one configuration. How likely is it that they have a specific configuration of 0 and 1? Equally likely.
Well, there are only 2 states with all 1 or all 0.
But there are 2^N states of mixed 1 and 0.
Even if you treat the sets of bits as opaque items, and pick one from a bucket, I'd expect getting one of the 2^N - 2 configurations to be a far more likely outcome than one of the 2 remaining.
In fact, we could bet on it...
- jbay808 5y agoBut there's only one state that is 10010001111110101000.
- coldtea 5y agoSure, but that's irrelevant. There are billions that are similar, and only one that's all 0.
- jbay808 5y ago"similar" is in the eye of the observer! This fact should be especially clear in the context of bit strings. If 10010001111110101000 is my login password, don't be surprised if other permutations fail to grant you access, even if you have the correct number of 1's and 0's.
- coldtea 5y ago>"similar" is in the eye of the observer! Nope, also similar in algorithmic complexity theory (e.g. counting compressibility).
- jbay808 5y agoThat's a very good, and deep, point, and I agree that there is something important there. However, algorithmic complexity is still only defined relative to an arbitrary reference computer. If my reference computer happens to, in hardware, XOR its inputs and outputs with the bitstring 10010001111110101000, then (in terms of bits that end up represented on the drive), that will be the one that has the lowest algorithmic complexity, although the algorithm might think that it's outputting all 0's.