6 ms·
To answer the obvious next question: Four 5-bit values in order have 20 bits of entropy, so cannot be stored in 16 bits. Four 5-bit values without order have
by ajkjk 9y ago
To answer the obvious next question:
Four 5-bit values in order have 20 bits of entropy, so cannot be stored in 16 bits.
Four 5-bit values without order have 20 - log2(4!) =~ 20 - 4.59 = 15.41 bits of entropy (corresponding to log(2^20/4!) possible configurations), and thus can fit in 16 bits of data if you're clever about it.
- Buttons840 9y agoIs there a specific topic of study that taught you those formulas?
- gpm 9y agoNot the person you asked but 4! is the number of permutations of a list - it's commonly seen throughout CS theory and other forms of discrete math. log_2(n) is the number of bits needed to store a integer from 0 to n - it's reasonably commonly used in CS theory education.
- cameldrv 9y agoProbability theory and information theory.
- SilasX 9y agoAs cameldrv said, information theory. The late David MacKay has a good free book: http://www.inference.org.uk/itprnn/book.html http://www.inference.org.uk/itprnn/book.html The intro chapters cover the topic of measuring informational entropy. Aside: One interesting application is to the problem of “use a balance scale only three times to determine which of twelve balls has the wrong weight (too heavy or light)”. You choose the weighings so as as to maximize the entropy of the outcome i.e. so there are many possible outcomes of equal probability.
- abpavel 9y agotry combinatorics branch of mathematics
- arnarbi 9y agohttps://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Information_theory
- ajkjk 9y agoAs others have mentioned, it comes up in information theory, or maybe in some subfields of combinatorics and probability. I learned it tangentially in various parts of physics. But I might just recommend going to the source! which is Claude Shannon's seminal masters thesis on coding: http://affect-reason-utility.com/1301/4/shannon1948.pdf http://affect-reason-utility.com/1301/4/shannon1948.pdf . It's surprisingly readable and worth at least skimming if you like this stuff.
- londons_explore 9y agoYour math is wrong. If two of the numbers happen to be the same, order no longer matters for those numbers, so your log2(4!) needs to be larger...
- jack9 9y agoThe maximum entropy is what is important, to the encoding challenge, as I understood it.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- scatters 9y agoRight. So the true answer is log2((32*31*30*29)/(4*3*2) + (32*31*30)/2 + (32*31) + (32*31)/2) = 15.675 which is still smaller than 16.
- yorwba 9y agoAre you sure you don't mean log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34 using the number of sets of values from {0, 2^5-1} with at most 4 elements? If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_multisets https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... ) log2( (35*34*33*32)/(4*3*2*1) ) = 15.676
- pishpash 9y agoThe second answer, 15.676, is the correct one. It can also be arrived at by: log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)
- marcoperaza 9y ago[deleted]
- dboreham 9y agoThey're not ordered: that's the whole point.
- marcoperaza 9y agoMy bad, I misread!