Title: Theory / Unimportant / Math / Information theory - Cover Thomas+26 / 2 - Entropy
Tags: hasSeenConjDef récupéré toBinaryFunction convexFunction duplicateToOtherBook mid1510327840148

Question: The base of logarithm in information theory is
Answer: 2.
Page: 14
Chapter: 6
Section: 1
Kind: Def

Question: \(x\log x\), at \(x=0\), is defined as
Answer: 0
Page: 14
Chapter: 6
Section: 1
Kind: Def

Definition: \(-\sum_{x\in\mathcal X}p(x)\log_b p(x)\)
Page: 14
Chapter: 6
Section: 1
Variables: \(X\) a discrete random variable with alphabet \(\mathcal X\)
\(p(x)=Pr(X=x)\)
\(b>0\)
Notation: \(H_b(X)\)
Kind: Def
Definition2: \((\log_2b)H(X)\)

Name: The entropy of \(X\)
Definition: \(E_p\log{\frac1{p(X)}}\)
Page: 14, 15, 21
Chapter: 2
Section: 1, 4
Variables: \(X\) a discrete random variable with alphabet \(\mathcal X\)
\(p(x)=Pr(X=x)\)
Notation: \(H(X)\)
Index: , 1
Kind: Def, lem
Example: 1 bit
Name2: Self information of \(X\)
Example2: 0.
Typ: Bits
Applied to: Fair coin
Notation2: \(H(p)\)
Applied to2: a variable with a single value of non nul probability
Property: In [$][0,\log\abs{\mathcal X}][/$]

Name: The expectation of \(g\)
Definition: \(\sum_{x\in\mathcal X}g(x)p(x)\)
Page: 14
Chapter: 6
Section: 1
Variables: \(X\) a discrete random variable with alphabet \(\mathcal X\)
\(p(x)=Pr(X=x)\)
\(g:X\to\mathbb R\)
Notation: \(E_pg(X)\)
Kind: Def

Name: The joint entropy of \(X\) and \(Y\)
Definition: \(-E\log p(X,Y)\)
Page: 16
Chapter: 2
Variables: \(X,Y\) a pair of discrete random variables,
\(p(x,y)\) their joint distribution
Notation: \(H(X,Y)\)

Name: The conditional entropy of \(Y\) given \(X\)
Definition: \(-E_{X,Y}\log p(Y|X)\)
Page: 17
Chapter: 2
Variables: \(X,Y\) a pair of discrete random variables,
\(p(x,y)\) their joint distribution,
Notation: \(H(Y|X)\)
Kind: Def

Smaller0: \(H(X,Y\mid Z)\)
Greater0: \(H(X\mid Z)+H(Y\mid X,Z)\)
Page: 17, 18
Chapter: 2
Variables: \(X,Y,Z\) discrete random variables,
\(p(x,y,z)\) their joint distribution,
Index: 1
Kind: Theo, Cor
Smaller to greater: =
Name: Chain rule

Smaller0: \(\log p(X,Y)\)
Greater0: \(\log p(X)+\log p(Y\mid X)\)
Page: 18
Chapter: 2
Variables: \(X,Y\) a pair of discrete random variables,
\(p(x,y)\) their joint distribution,
Index: 1
Kind: Theo
Smaller to greater: =

Smaller0: \(H(X)-H(Y)\)
Greater0: \(H(Y\mid X)-H(X\mid Y)\)
Page: 18
Chapter: 2
Variables: \(X,Y\) discrete random variables,
\(p(x,y)\) their joint distribution,
Index: 1
Kind: Rem
Smaller to greater: =

Name: The relative entropy of \(p\) and \(q\)
Definition: \(E_p\log{\frac{p(x)}{q(x)}}\)
Page: 19, 28
Chapter: 2
Section: 3
Variables: \(X\) a discrete random variable,
\(p,q\) two probability mass function over \(X\)
Notation: \(D(p\parallel q)\)
Index: , 3
Kind: , Theo
Name2: Kullback-Leibler distance
Extra: It is normal that \(q\) is not below \(E\)
Intuition: the inefficiency of assuming that the distribution is \(q\) when the true distribution is \(p\).
Typ: nonnegative

Smaller0: \(=0\)
Greater0: \(p(y\mid x)=q(y\mid x)\) for all \(x,y\) such that \(p(x)>0\)
Page: 19, 28, 29
Chapter: 2
Section: 3
Variables: \(X,Y\) random variables
\(p(x,y),q(x,y)\) probability mass functions
Index: , 3
Kind: , Theo, cor
Smaller to greater: iff
Prefix Smaller: \(D(p(y\mid x)\parallel q(y\mid x))\)

Smaller0: \(=0\)
Greater0: \(X,Y\) are conditionnaly independent given \(Z\)
Page: 29
Chapter: 2
Section: 3
Variables: \(X,Y,Z\) random variables
\(p(x,y),q(x,y)\) probability mass functions
Kind: Cor
Smaller to greater: iff
Prefix Smaller: \(I(X;Y\mid Z)\)

Page: 20, 21, 28
Section: 3, 4, 6
Notation: \(I(X;Y)\)
Variables: \(X,Y\) discrete random variables,
\(p(x,y)\) their joint distribution,
Chapter: 2
Name: The mutual information of \(X\) and \(Y\)
Definition: \(E_{p(x,y)}\log\frac{p(X,Y)}{p(X)p(Y)}=-E_{p(x,y)}\log\frac{p(X)p(Y)}{p(X,Y)}\)
Example: \(H(X)\)
Kind: , Theo
Index: ,3
Commutative: Commutative function
Intuition: the reduction in the uncertainty of \(X\) due to the knowledge of \(Y\).
Extra: No minus before the expectation
Codomain: non-negative
Definition2: \(D(p(x,y)\parallel p(x)p(y))\)
Applied to: \((X,X)\)
Definition3: \(H(X)+H(Y)-H(X,Y)\)
Definition4: \(H(X)-H(X\mid Y)\)

Question: \(I(X;X)\)
Answer: equals \(H(X)\)
Page: 21
Chapter: 2
Section: 4
Variables: \(X\) discrete random variables
\(p(x)\) its distribution

Smaller0: \(H(X_1,\dots, X_n)\)
Greater0: \(\sum H(X_i\mid X_{1},\dots, X_{i-1})\)
Page: 22
Chapter: 2
Section: 5
Variables: \(X_1,\dots, X_n\) discrete random variables
\(p(x_1,\dots, x_n)\) their distribution
Smaller to greater: =
Name: Chain rule for entropy

Smaller0: \(I(X_1,\dots, X_n;Y)\)
Greater0: \(\sum_{i=1}^n I(X_i;Y\mid X_{1},\dots, X_{i-1})\)
Page: 24
Chapter: 2
Section: 5
Variables: \(X_1,\dots, X_n,Y\) discrete random variables
\(p(x_1,\dots, x_n,y)\) their distribution
Smaller to greater: =
Name: Chain rule for information

Page: 20, 21, 23
Section: 4, 5
Notation: \(I(X;Y\mid Z)\)
Variables: \(X,Y,Z\) discrete random variables,
\(p(x,y,z)\) their joint distribution,
Chapter: 2
Name: The conditional mutual information of \(X\) and \(Y\) given \(Z\)
Definition: \(H(X\mid Z)-H(X\mid Y, Z)\)
Commutative: Commutative function
Intuition: the reduction in the uncertainty of \(X\) due to the knowledge of \(Y\)
Definition2: \(E_{p(x,y,z)}\log\frac{p(X,Y\mid Z)}{p(X\mid Z)p(Y\mid Z)}\)

Name: The conditional relative entropy of \(p\) and \(q\)
Definition: \(E_{p(x,y)}\log\left(\frac{p(Y\mid X)}{q(Y\mid X)}\right)\)
Page: 24
Chapter: 2
Section: 5
Variables: \(X,Y\) discrete random variables,
\(p(x,y),q(x,y)\) distributions,
Notation: \(D(p(y\mid x)\parallel q(y\mid x))\)
Extra: no minus before log

Smaller0: \(D(p(y, x)\parallel q(y, x))\)
Greater0: \(D(p(x)\parallel q(x))+D(p(y\mid x)\parallel q(y\mid x))\)
Page: 24
Chapter: 2
Section: 5
Variables: \(X,Y\) discrete random variables,
\(p(x,y),q(x,y)\) distributions,
Smaller to greater: =
Name: Chain rule for relative entropy

Name: A convex function on \((a,b)\)
Definition: A function \(f(x)\) such that \(f(\lambda x_i+(1-\lambda)x_2)\le\lambda f(x_1)+(1-\lambda)f(x_2)\) for \(0<\lambda<1\)
Page: 25
Chapter: 2
Section: 6
Variables: \(a<b\)
Definition2: \(f''>0\) (assuming it exists)
Example: \(x^2\)
Conjdef: A function \(f(x)\) such that, equivalently
Definition3: A function \(f:]a,b[\to\mathbb R\) such that \(\frac{f(x)-f(x_1)}{x-x_1}\le \frac{f(x_2)-f(x)}{x_2-x}\) for \(a<x_1<x<x_2<b\). It means the slope from \(x_1\) to \(x\) is not larger than the slope from \(x\) to \(x_2\).
Example2: [$]\abs{x}[/$]
Extra: Entropy Ch 2.6, Page 25,
Zorich 1. Ch 5.4.3, P 241-244
Linear and integer programming ch 1.3 P 7
Intuition: A function which always lies above any chord
Example3: \(e^x\)
Example4: \(x\log x\) for \(x\ge0\)

Name: A strict concave function on \((a,b)\)
Definition: A function \(f(x)\) such that \(f(\lambda  x_i+(1-\lambda)x_2)>\lambda f(x_1)+(1-\lambda)f(x_2)\) for \(0<\lambda<1\)
Page: 25
Chapter: 2
Section: 6
Variables: \(a<b\)
Definition2: \(f''<0\) (assuming it exists)
Conjdef: A function \(f(x)\) such that, equivalently
Applied to3: A function which always lies strictly below any chord

Name: A concave function on \((a,b)\)
Definition: \(f(\lambda x_i+(1-\lambda)x_2)\ge\lambda f(x_1)+(1-\lambda)f(x_2)\) for \(0<\lambda<1\)
Page: 25
Chapter: 2
Section: 6
Variables: \(a<b\)
Definition2: \(f''\le0\) (assuming it exists)
Example: \(\log x\)
Conjdef: A function \(f(x)\) such that, equivalently
Definition3: \(-f\) is convex.
Example2: \(\sqrt x\) for \(x\ge0\)
Intuition: A function which always lies below any chord

Smaller0: \(f(EX)\)
Greater0: \(Ef(x)\)
Page: 27
Chapter: 2
Section: 6
Variables: \(f:\mathbb R\to\mathbb R\)
\(X\) a random variable
Kind: Theo
Smaller to greater: \(\le\)
Assuming: \(f\) is convex
Name: Jensen's inequality
Greater to smaller: \(\ge\)

Page: 29
Section: 3
Chapter: 2
Name: D(p(y\mid x)\parallel q(y\mid x))
Variables: \(X,Y\) random variables
\(p(x,y),q(x,y)\) probability mass functions
Kind: Cor
Abbreviation: =0
Algebraic concordance order: iff

Smaller0: the distribution is uniform
Greater0: equals [$]\log\abs{\mathcal X}[/$]
Page: 29
Chapter: 2
Section: 3
Variables: \(X\) a random variable,
\(\mathcal X\) the range of \(X\)
\(p\) probability mass functions
Index: 4
Kind: Theo
Smaller to greater: iff
Prefix Greater: \(H(X)\)

Smaller0: \(X,Y\) are independent
Greater0: equals \(H(X)\)
Page: 29
Chapter: 2
Section: 3
Variables: \(X,Y\) a random variable
\(p\) probability mass functions
Index: 4
Kind: Theo
Smaller to greater: iff
Prefix Greater: \(H(X\mid Y)\)

Smaller0: \(H(X\mid Y)\)
Greater0: \(H(X)\)
Page: 29
Chapter: 2
Section: 3
Variables: \(X,Y\) a random variable
\(p\) probability mass functions
Index: 4
Kind: Theo
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Smaller0: \(H(X_1,\dots, X_n)\)
Greater0: \(\sum_i H(X_i)\)
Page: 30
Chapter: 2
Section: 3
Variables: \(X_1,\dots,X_n\) a random variable
\(p\) probability mass functions
Index: 6
Kind: Theo
Smaller to greater: \(\le\)
Name: Independence bound on entropy
Greater to smaller: \(\ge\)

Smaller0: \(\left(\sum a_i\right)\frac{\sum a_i}{\sum b_i}\)
Greater0: \(\sum a_i\log\frac {a_i}{b_i}\)
Page: 31
Chapter: 2
Section: 7
Variables: \(a_1,\dots,a_n,b_1,\dots,b_n\in\mathbb R\)
Smaller to greater: \(\le\)
Assuming: all variables non negative
Greater to smaller: \(\ge\)

Smaller0: \(\frac {a_i}{b_i}\) constant
Greater0: \(\sum a_i\log\frac {a_i}{b_i}\)
Page: 31
Chapter: 2
Section: 7
Variables: \(a_1,\dots,a_n,b_1,\dots,b_n\in\mathbb R\)
Smaller to greater: iff
Assuming: all variables non negative
Greater1: \(\left(\sum a_i\right)\frac{\sum a_i}{\sum b_i}\)
Connect Greater0: =