16.36: Communication Systems Engineering Lecture 2: Entropy Eytan Modiano
16.36: Communication Systems Engineering Lecture 2: Entropy Eytan Modiano Eytan Modiano Slide 1
Information content of a random variable Random variable x Outcome of a random experiment Discrete R.V. takes on values from a finite set of possible outcomes PMF: P(X=y)=P,ly) How much information is contained in the event x= y? Will the sun rise today Revealing the outcome of this experiment provides no information Will the Celtics win the nba championship? Since this is unlikely, revealing yes provides more information than revealing no Events that are less likely contain more information than likely events
Information content of a random variable • Random variable X – Outcome of a random experiment – Discrete R.V. takes on values from a finite set of possible outcomes PMF: P(X = y) = P x(y) • How much information is contained in the event X = y? – Will the sun rise today? Revealing the outcome of this experiment provides no information – Will the Celtics win the NBA championship? Since this is unlikely, revealing yes provides more information than revealing no • Events that are less likely contain more information than likely events Eytan Modiano Slide 2
Measure of information I(*i)=Amount of information revealed by an outcome X=X i Desirable properties of I(x) 1. If P(x)=1 or P(x=0, then I(x=0 2.0<P(x)<1, then I(x)>0 3. If P(x<Ply), then l(x>ly) 4. If x and y are independent events then i(x, y)=1(x+lly) Above is satisfied by: I(x)=Log2 (1/P(Xl) Base of Log is not critical Base 2=> information measured in bits
Measure of Information • I(xi) = Amount of information revealed by an outcome X = xi • Desirable properties of I(x): 1. If P(x) = 1 or P(x) = 0, then I(x) = 0 2. If 0 < P(x) < 1, then I(x) > 0 3. If P(x) < P(y), then I(x) > I(y) 4. If x and y are independent events then I(x,y) = I(x)+I(y) • Above is satisfied by: I(x) = Log 2(1/P(x)) • Base of Log is not critical – Base 2 => information measured in bits Eytan Modiano Slide 3
Entropy a measure of the information content of a random variable X∈{x1…,XM} ●H(X)=EX=ΣP(x)Log21/P(x) Example: Binary experiment X=X, with probability p X=X2 with probability (1-p) H(X=pLog2(1p) +(1-p)Log2(1/(1-p))=Hb(p) H(X) is maximized with p=1/2, Hb(1/ 2) Not surprising that the result of a binary experiment can be conveyed using one bit
∈ ∑ Entropy • A measure of the information content of a random variable • X ∈ {x1,…,XM} • H(X) = E[I(X)] = ∑P(xi) Log2(1/P(xi)) • Example: Binary experiment – X = x1 with probability p – X = x2 with probability (1-p) – H(X) = pLog2(1/p) + (1-p)Log2(1/(1-p)) = Hb(p) – H(X) is maximized with p=1/2, Hb(1/2) = 1 Not surprising that the result of a binary experiment can be conveyed using one bit Eytan Modiano Slide 4
Simple bounds on entropy Theorem: Given a random variable with m possible values 0<=H(X≤=Log2M A)H(X)=0 if and only if P(x)=1 for some i B)H(X)=Log2 (M)if and only if P(x =1/M for all i Proof of a is obvious Y=x-1 Proof of b requires the Log Inequality if xo then In(x)<=X-1 Equality if X=1 Y=In( 5
Simple bounds on entropy • Theorem: Given a random variable with M possible values – 0 <= H(X) <= Log2(M) A) H(X) = 0 if and only if P( xi) = 1 for some i B) H(X) = Log2(M) if and only if P( xi) = 1/M for all i – Proof of A is obvious Y=x-1 – Proof of B requires – the Log Inequality: – if x>0 then ln(x) <= x-1 – Equality if x=1 Y= ln ( x) Eytan Modiano Slide 5