3 ms·
You need an equal number of 0's and 1's, and you can use compressibility to see why. If there are more 1's than 0's, your compression tool could start by assumi
by sp332 13y ago
You need an equal number of 0's and 1's, and you can use compressibility to see why. If there are more 1's than 0's, your compression tool could start by assuming that all the bits are 1's, and only storing information about where the 0's are. To minimize compressibility, you have to make sure there's no bias toward certain patterns, even patterns of length 1.
- robrenaud 13y agoYou need every bit string to be maximally unpredictable a priori. EG, every bit string of length n is equally likely. This is not the same as having exactly equal numbers of 0s and 1s. That doesn't really even make sense, because with the constraint as mentioned, you can't ever transmit an odd length string. Also, if you are transmitting a bit string of length 2, knowing the first bit guarantees you know the second, which is low entropy (you only have one bit of entropy in a 2 bit message). On the other hand, it is the case that most long bit strings sampled from a maximally entropic source have roughly the same number of 0s and 1s.
- dlubarov 13y agoLet's say the string contains 100 0s and 101 1s. How would you encode the positions of the 0s without using more than 201 bits in total? Nearly all random strings of sufficient length have different numbers of 0s and 1s. So if your argument were true, your compression scheme would reduce the average length of completely random strings, which is impossible.
- robrenaud 13y agoEven knowing the exact number of 1s and 0s buys you a few bits of information. log(201 choose 100) / log(2) = 196.843 Order the 201 choose 100 strings on 201 bits with exactly 100 0s lexicographically, write down the index in that list of your particular message in 197 bits in a completely ordinary fashion ;P. But to be clear, I don't disagree with what you mean at all.
- Retric 13y agoUse 200 bit's to encode the message except the last bit which is determined if the message had 100 1's or 101 1's. QED knowing the number of 1's buy's you at least one bit of information. Edit: You can do better than this by counting the number of 201 bit messages with 100 0's which is well below 2^201 and then encoding which of those corresponds to the original message. Aka if you had an 8 bit message with one zero 11111101 you have a total of 8 options which means you can encode it as 3 bits.