Thursday, September 2, 2010

Five-Minute Info Theory Problem

I can't believe it's September already. Astonishingly, I managed to get eight of my nine summer to-do list items done, at least partly.

Here's a simple problem that came up yesterday when I was looking for a quick bound on entropy ... I thought it would be a nice warmup to kick off the term:

Let A and B be independent random variables. WLOG, suppose H(A) <= H(B).

Show that H(A) <= H(B) <= H(A+B) <= H(A)+H(B).

Post your answer in the comments.

4 comments:

Anonymous said...

H(A+B, A) = H(A) + H(A+B|A)
= H(A) + H(B)

Therefore, H(A+B) <= H(A) + H(B) ---(1)

Also,
H(A+B,A) = H(A+B) + H(A|A+B).
=>
H(A+B) + H(A|A+B) = H(A) + H(B)
H(A+B) + H(A) >= H(A) + H(B)
H(A+B) >= H(B) ----(2).

Although I am able to "work through" the expressions, I dont get the intuition for H(A+B)>=H(B). It's just that I tried a couple of inequalities at random and one of them clicked... how do we go about picking the approach?

Anonymous said...

On thinking some more, I am now not sure if the assertion is correct. Is
H(A+B) >= max(H(A),H(B)) always?

Let A and B have the following joint dist:
Pr(A=1, B=-1) = 1/2
Pr(A=-1, B=1) = 1/2.

Then, A+B is always 0, so H(A+B)=0.
However, H(A) and H(B) are both 1.

Now, going back to the proof I had in the earlier comment, it seems like the "hand-waving" assumption was:
H(A+B|A) = H(B). While it is fair to say H(A+B|A) <= H(B), the equality is not always true.

Anonymous said...

Ha, I just saw ur problem statement: A and B are independent!

Andrew said...

You got it. As far as intuition is concerned, I prefer to solve H(A+B) >= H(B) by noting that H(A+B|A) = H(B) (which is part of your solution), and then realizing that H(A+B|A) <= H(A+B) (because side information always reduces entropy).

Put less formally, if you know A+B and A, then you know B for sure. But if you A+B, then you need more information to describe it than either A or B alone.