Proof that $H(X) leq log(|A|)$ (Shannon entropy)
up vote
0
down vote
favorite
The full question states:
"Show that $$H(X) leq log(|A|)$$
with equality if and only if $P_X$ is uniform. Hint: use the Gibbs or log-sum inequality "
I used "$A$" as the alphabet in here. My lecturer is using curly "X" which I don't know how to type in MathJax.
The equality part is rather straight forward.
Suppose $A={1,...,m}$ and $P_X(x)=frac{1}{m} forall x$. Then of course $|A|=m$
And $$H(X)=-sum_{x=1}^m frac{1}{m}log(frac{1}{m})=-log(frac{1}{m})=log(m)=log(|A|)$$
It is the inequality part that I am not sure how to show. Thanks for any help
probability logarithms information-theory entropy
add a comment |
up vote
0
down vote
favorite
The full question states:
"Show that $$H(X) leq log(|A|)$$
with equality if and only if $P_X$ is uniform. Hint: use the Gibbs or log-sum inequality "
I used "$A$" as the alphabet in here. My lecturer is using curly "X" which I don't know how to type in MathJax.
The equality part is rather straight forward.
Suppose $A={1,...,m}$ and $P_X(x)=frac{1}{m} forall x$. Then of course $|A|=m$
And $$H(X)=-sum_{x=1}^m frac{1}{m}log(frac{1}{m})=-log(frac{1}{m})=log(m)=log(|A|)$$
It is the inequality part that I am not sure how to show. Thanks for any help
probability logarithms information-theory entropy
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The full question states:
"Show that $$H(X) leq log(|A|)$$
with equality if and only if $P_X$ is uniform. Hint: use the Gibbs or log-sum inequality "
I used "$A$" as the alphabet in here. My lecturer is using curly "X" which I don't know how to type in MathJax.
The equality part is rather straight forward.
Suppose $A={1,...,m}$ and $P_X(x)=frac{1}{m} forall x$. Then of course $|A|=m$
And $$H(X)=-sum_{x=1}^m frac{1}{m}log(frac{1}{m})=-log(frac{1}{m})=log(m)=log(|A|)$$
It is the inequality part that I am not sure how to show. Thanks for any help
probability logarithms information-theory entropy
The full question states:
"Show that $$H(X) leq log(|A|)$$
with equality if and only if $P_X$ is uniform. Hint: use the Gibbs or log-sum inequality "
I used "$A$" as the alphabet in here. My lecturer is using curly "X" which I don't know how to type in MathJax.
The equality part is rather straight forward.
Suppose $A={1,...,m}$ and $P_X(x)=frac{1}{m} forall x$. Then of course $|A|=m$
And $$H(X)=-sum_{x=1}^m frac{1}{m}log(frac{1}{m})=-log(frac{1}{m})=log(m)=log(|A|)$$
It is the inequality part that I am not sure how to show. Thanks for any help
probability logarithms information-theory entropy
probability logarithms information-theory entropy
edited Nov 21 at 15:38
Bernard
117k637109
117k637109
asked Nov 21 at 15:34
Kudera Sebastian
525216
525216
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
For any probability distributions $p, q$ on $A$, Gibbs inequality states that
$$
H(p)=-sum_{kin A} p(k)log p(k)leq -sum_{kin A} p(k)log q(k)
$$
with equality iff $p=q$. Take $q$ to correspond to a uniform distribution on $A$. Then
$$
H(p)leq -sum_{kin A} p(k)log frac{1}{|A|}=log|A|
$$
with equality iff $p$ is a uniform distribution as desired.
add a comment |
up vote
0
down vote
Let $p_i$s be the corresponding probabilities of the source $X$ and $q_i={1over |A|}$ for $i=1,2,cdots , |A|$ . Therefore using Gibbs' inequality we obtain:$$H(X)=-sum p_ilog p_ile -sum p_ilog q_i=-log {1over |A|}sum p_i=log |A|$$
For further reading, you can refer to https://en.wikipedia.org/wiki/Gibbs%27_inequality
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
For any probability distributions $p, q$ on $A$, Gibbs inequality states that
$$
H(p)=-sum_{kin A} p(k)log p(k)leq -sum_{kin A} p(k)log q(k)
$$
with equality iff $p=q$. Take $q$ to correspond to a uniform distribution on $A$. Then
$$
H(p)leq -sum_{kin A} p(k)log frac{1}{|A|}=log|A|
$$
with equality iff $p$ is a uniform distribution as desired.
add a comment |
up vote
1
down vote
accepted
For any probability distributions $p, q$ on $A$, Gibbs inequality states that
$$
H(p)=-sum_{kin A} p(k)log p(k)leq -sum_{kin A} p(k)log q(k)
$$
with equality iff $p=q$. Take $q$ to correspond to a uniform distribution on $A$. Then
$$
H(p)leq -sum_{kin A} p(k)log frac{1}{|A|}=log|A|
$$
with equality iff $p$ is a uniform distribution as desired.
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
For any probability distributions $p, q$ on $A$, Gibbs inequality states that
$$
H(p)=-sum_{kin A} p(k)log p(k)leq -sum_{kin A} p(k)log q(k)
$$
with equality iff $p=q$. Take $q$ to correspond to a uniform distribution on $A$. Then
$$
H(p)leq -sum_{kin A} p(k)log frac{1}{|A|}=log|A|
$$
with equality iff $p$ is a uniform distribution as desired.
For any probability distributions $p, q$ on $A$, Gibbs inequality states that
$$
H(p)=-sum_{kin A} p(k)log p(k)leq -sum_{kin A} p(k)log q(k)
$$
with equality iff $p=q$. Take $q$ to correspond to a uniform distribution on $A$. Then
$$
H(p)leq -sum_{kin A} p(k)log frac{1}{|A|}=log|A|
$$
with equality iff $p$ is a uniform distribution as desired.
answered Nov 21 at 16:02
Foobaz John
20.3k41250
20.3k41250
add a comment |
add a comment |
up vote
0
down vote
Let $p_i$s be the corresponding probabilities of the source $X$ and $q_i={1over |A|}$ for $i=1,2,cdots , |A|$ . Therefore using Gibbs' inequality we obtain:$$H(X)=-sum p_ilog p_ile -sum p_ilog q_i=-log {1over |A|}sum p_i=log |A|$$
For further reading, you can refer to https://en.wikipedia.org/wiki/Gibbs%27_inequality
add a comment |
up vote
0
down vote
Let $p_i$s be the corresponding probabilities of the source $X$ and $q_i={1over |A|}$ for $i=1,2,cdots , |A|$ . Therefore using Gibbs' inequality we obtain:$$H(X)=-sum p_ilog p_ile -sum p_ilog q_i=-log {1over |A|}sum p_i=log |A|$$
For further reading, you can refer to https://en.wikipedia.org/wiki/Gibbs%27_inequality
add a comment |
up vote
0
down vote
up vote
0
down vote
Let $p_i$s be the corresponding probabilities of the source $X$ and $q_i={1over |A|}$ for $i=1,2,cdots , |A|$ . Therefore using Gibbs' inequality we obtain:$$H(X)=-sum p_ilog p_ile -sum p_ilog q_i=-log {1over |A|}sum p_i=log |A|$$
For further reading, you can refer to https://en.wikipedia.org/wiki/Gibbs%27_inequality
Let $p_i$s be the corresponding probabilities of the source $X$ and $q_i={1over |A|}$ for $i=1,2,cdots , |A|$ . Therefore using Gibbs' inequality we obtain:$$H(X)=-sum p_ilog p_ile -sum p_ilog q_i=-log {1over |A|}sum p_i=log |A|$$
For further reading, you can refer to https://en.wikipedia.org/wiki/Gibbs%27_inequality
answered Nov 21 at 17:15
Mostafa Ayaz
13.5k3836
13.5k3836
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2fmath.stackexchange.com%2fquestions%2f3007877%2fproof-that-hx-leq-loga-shannon-entropy%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