Mixing
Shannon Entropy of 0.922, 3 Distinct Values
up vote
9
down vote
favorite
Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.
Taken from the introduction on this wikipedia page:
https://en.wikipedia.org/wiki/Entropy_%28information_theory%29
So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?
Thank you in advance.
information-theory mathematical-foundations entropy binary
edited 20 hours ago
David Richerby
64.3k1597185
asked 22 hours ago
Sean C
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
9
down vote
favorite
Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.
Taken from the introduction on this wikipedia page:
https://en.wikipedia.org/wiki/Entropy_%28information_theory%29
So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?
Thank you in advance.
information-theory mathematical-foundations entropy binary
edited 20 hours ago
David Richerby
64.3k1597185
asked 22 hours ago
Sean C
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
9
down vote
favorite
up vote
9
down vote
favorite
Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.
Taken from the introduction on this wikipedia page:
https://en.wikipedia.org/wiki/Entropy_%28information_theory%29
So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?
Thank you in advance.
information-theory mathematical-foundations entropy binary
edited 20 hours ago
David Richerby
64.3k1597185
asked 22 hours ago
Sean C
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.
Taken from the introduction on this wikipedia page:
https://en.wikipedia.org/wiki/Entropy_%28information_theory%29
So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?
Thank you in advance.
information-theory mathematical-foundations entropy binary
information-theory mathematical-foundations entropy binary
edited 20 hours ago
David Richerby
64.3k1597185
asked 22 hours ago
Sean C
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 20 hours ago
David Richerby
64.3k1597185
asked 22 hours ago
Sean C
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 20 hours ago
David Richerby
64.3k1597185
edited 20 hours ago
David Richerby
64.3k1597185
edited 20 hours ago
David Richerby
64.3k1597185
64.3k1597185
asked 22 hours ago
Sean C
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 22 hours ago
Sean C
483
asked 22 hours ago
Sean C
483
483
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Sean C is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
up vote
11
down vote
accepted
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $tfrac{8}{10}$, and $B$ and $C$ with probability $tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't represent strings generated from this distribution using less than $0.992$ bits per character, on average.
It might be quite hard to develop a code that will achieve this rate.* For example, Huffman coding would allocate codes $0$, $10$ and $11$ to $A$, $B$ and $C$, respectively, for an average of $1.2$ bits per character. That's quite far from the entropy, though still a good deal better than the naive encoding of two bits per character. Any attempt at a better coding will probably exploit the fact that even a run of ten consecutive $A$s is more likely (probability $0.107$) than a single $B$.
* Turns out that it isn't hard to get as close as you want – see the other answers!
answered 20 hours ago
David Richerby
64.3k1597185
add a comment |
up vote
11
down vote
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:
First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.
This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).
The average number of bits per symbol pair for the above encoding is
$$frac{8}{10} cdot frac{8}{10} cdot 1 + 3 cdot frac{8}{10} cdot frac{1}{10} cdot 3 + frac{1}{10} cdot frac{8}{10} cdot 4 + 4 cdot frac{1}{10} cdot frac{1}{10} cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.
answered 17 hours ago
nomadictype
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
8
down vote
Let $mathcal{D}$ be the following distribution over ${A,B,C}$: if $X sim mathcal{D}$ then $Pr[X=A] = 4/5$ and $Pr[X=B]=Pr[X=C]=1/10$.
For each $n$ we can construct prefix codes $C_ncolon {A,B,C}^n to {0,1}^*$ such that
$$
lim_{ntoinfty} frac{operatorname*{mathbb{E}}_{X_1,ldots,X_n sim mathcal{D}}[C_n(X_1,ldots,X_n)]}{n} = H(mathcal{D}).
$$
In words, if we encode a large number of independent samples from $mathcal{D}$, then on average we need $H(mathcal{D}) approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.
This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.
answered 20 hours ago
Yuval Filmus
187k12176337
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
11
down vote
accepted
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $tfrac{8}{10}$, and $B$ and $C$ with probability $tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't represent strings generated from this distribution using less than $0.992$ bits per character, on average.
It might be quite hard to develop a code that will achieve this rate.* For example, Huffman coding would allocate codes $0$, $10$ and $11$ to $A$, $B$ and $C$, respectively, for an average of $1.2$ bits per character. That's quite far from the entropy, though still a good deal better than the naive encoding of two bits per character. Any attempt at a better coding will probably exploit the fact that even a run of ten consecutive $A$s is more likely (probability $0.107$) than a single $B$.
* Turns out that it isn't hard to get as close as you want – see the other answers!
answered 20 hours ago
David Richerby
64.3k1597185
add a comment |
up vote
11
down vote
accepted
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $tfrac{8}{10}$, and $B$ and $C$ with probability $tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't represent strings generated from this distribution using less than $0.992$ bits per character, on average.
It might be quite hard to develop a code that will achieve this rate.* For example, Huffman coding would allocate codes $0$, $10$ and $11$ to $A$, $B$ and $C$, respectively, for an average of $1.2$ bits per character. That's quite far from the entropy, though still a good deal better than the naive encoding of two bits per character. Any attempt at a better coding will probably exploit the fact that even a run of ten consecutive $A$s is more likely (probability $0.107$) than a single $B$.
* Turns out that it isn't hard to get as close as you want – see the other answers!
answered 20 hours ago
David Richerby
64.3k1597185
add a comment |
up vote
11
down vote
accepted
up vote
11
down vote
accepted
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $tfrac{8}{10}$, and $B$ and $C$ with probability $tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't represent strings generated from this distribution using less than $0.992$ bits per character, on average.
It might be quite hard to develop a code that will achieve this rate.* For example, Huffman coding would allocate codes $0$, $10$ and $11$ to $A$, $B$ and $C$, respectively, for an average of $1.2$ bits per character. That's quite far from the entropy, though still a good deal better than the naive encoding of two bits per character. Any attempt at a better coding will probably exploit the fact that even a run of ten consecutive $A$s is more likely (probability $0.107$) than a single $B$.
* Turns out that it isn't hard to get as close as you want – see the other answers!
answered 20 hours ago
David Richerby
64.3k1597185
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $tfrac{8}{10}$, and $B$ and $C$ with probability $tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't represent strings generated from this distribution using less than $0.992$ bits per character, on average.
It might be quite hard to develop a code that will achieve this rate.* For example, Huffman coding would allocate codes $0$, $10$ and $11$ to $A$, $B$ and $C$, respectively, for an average of $1.2$ bits per character. That's quite far from the entropy, though still a good deal better than the naive encoding of two bits per character. Any attempt at a better coding will probably exploit the fact that even a run of ten consecutive $A$s is more likely (probability $0.107$) than a single $B$.
* Turns out that it isn't hard to get as close as you want – see the other answers!
answered 20 hours ago
David Richerby
64.3k1597185
edited 7 hours ago
answered 20 hours ago
David Richerby
64.3k1597185
answered 20 hours ago
David Richerby
64.3k1597185
answered 20 hours ago
David Richerby
64.3k1597185
64.3k1597185
add a comment |
add a comment |
up vote
11
down vote
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:
First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.
This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).
The average number of bits per symbol pair for the above encoding is
$$frac{8}{10} cdot frac{8}{10} cdot 1 + 3 cdot frac{8}{10} cdot frac{1}{10} cdot 3 + frac{1}{10} cdot frac{8}{10} cdot 4 + 4 cdot frac{1}{10} cdot frac{1}{10} cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.
answered 17 hours ago
nomadictype
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
11
down vote
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:
First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.
This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).
The average number of bits per symbol pair for the above encoding is
$$frac{8}{10} cdot frac{8}{10} cdot 1 + 3 cdot frac{8}{10} cdot frac{1}{10} cdot 3 + frac{1}{10} cdot frac{8}{10} cdot 4 + 4 cdot frac{1}{10} cdot frac{1}{10} cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.
answered 17 hours ago
nomadictype
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
11
down vote
up vote
11
down vote
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:
First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.
This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).
The average number of bits per symbol pair for the above encoding is
$$frac{8}{10} cdot frac{8}{10} cdot 1 + 3 cdot frac{8}{10} cdot frac{1}{10} cdot 3 + frac{1}{10} cdot frac{8}{10} cdot 4 + 4 cdot frac{1}{10} cdot frac{1}{10} cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.
answered 17 hours ago
nomadictype
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:
First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.
This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).
The average number of bits per symbol pair for the above encoding is
$$frac{8}{10} cdot frac{8}{10} cdot 1 + 3 cdot frac{8}{10} cdot frac{1}{10} cdot 3 + frac{1}{10} cdot frac{8}{10} cdot 4 + 4 cdot frac{1}{10} cdot frac{1}{10} cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.
answered 17 hours ago
nomadictype
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 17 hours ago
nomadictype
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 17 hours ago
nomadictype
2112
answered 17 hours ago
nomadictype
2112
2112
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
nomadictype is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
up vote
8
down vote
Let $mathcal{D}$ be the following distribution over ${A,B,C}$: if $X sim mathcal{D}$ then $Pr[X=A] = 4/5$ and $Pr[X=B]=Pr[X=C]=1/10$.
For each $n$ we can construct prefix codes $C_ncolon {A,B,C}^n to {0,1}^*$ such that
$$
lim_{ntoinfty} frac{operatorname*{mathbb{E}}_{X_1,ldots,X_n sim mathcal{D}}[C_n(X_1,ldots,X_n)]}{n} = H(mathcal{D}).
$$
In words, if we encode a large number of independent samples from $mathcal{D}$, then on average we need $H(mathcal{D}) approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.
This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.
answered 20 hours ago
Yuval Filmus
187k12176337
add a comment |
up vote
8
down vote
Let $mathcal{D}$ be the following distribution over ${A,B,C}$: if $X sim mathcal{D}$ then $Pr[X=A] = 4/5$ and $Pr[X=B]=Pr[X=C]=1/10$.
For each $n$ we can construct prefix codes $C_ncolon {A,B,C}^n to {0,1}^*$ such that
$$
lim_{ntoinfty} frac{operatorname*{mathbb{E}}_{X_1,ldots,X_n sim mathcal{D}}[C_n(X_1,ldots,X_n)]}{n} = H(mathcal{D}).
$$
In words, if we encode a large number of independent samples from $mathcal{D}$, then on average we need $H(mathcal{D}) approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.
This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.
answered 20 hours ago
Yuval Filmus
187k12176337
add a comment |
up vote
8
down vote
up vote
8
down vote
Let $mathcal{D}$ be the following distribution over ${A,B,C}$: if $X sim mathcal{D}$ then $Pr[X=A] = 4/5$ and $Pr[X=B]=Pr[X=C]=1/10$.
For each $n$ we can construct prefix codes $C_ncolon {A,B,C}^n to {0,1}^*$ such that
$$
lim_{ntoinfty} frac{operatorname*{mathbb{E}}_{X_1,ldots,X_n sim mathcal{D}}[C_n(X_1,ldots,X_n)]}{n} = H(mathcal{D}).
$$
In words, if we encode a large number of independent samples from $mathcal{D}$, then on average we need $H(mathcal{D}) approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.
This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.
answered 20 hours ago
Yuval Filmus
187k12176337
Let $mathcal{D}$ be the following distribution over ${A,B,C}$: if $X sim mathcal{D}$ then $Pr[X=A] = 4/5$ and $Pr[X=B]=Pr[X=C]=1/10$.
For each $n$ we can construct prefix codes $C_ncolon {A,B,C}^n to {0,1}^*$ such that
$$
lim_{ntoinfty} frac{operatorname*{mathbb{E}}_{X_1,ldots,X_n sim mathcal{D}}[C_n(X_1,ldots,X_n)]}{n} = H(mathcal{D}).
$$
In words, if we encode a large number of independent samples from $mathcal{D}$, then on average we need $H(mathcal{D}) approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.
This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.
answered 20 hours ago
Yuval Filmus
187k12176337
answered 20 hours ago
Yuval Filmus
187k12176337
answered 20 hours ago
Yuval Filmus
187k12176337
answered 20 hours ago
Yuval Filmus
187k12176337
187k12176337
add a comment |
add a comment |
Sean C is a new contributor. Be nice, and check out our Code of Conduct.
Sean C is a new contributor. Be nice, and check out our Code of Conduct.
Sean C is a new contributor. Be nice, and check out our Code of Conduct.
Sean C is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f100278%2fshannon-entropy-of-0-922-3-distinct-values%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
