Problem setup:

X1, X2... are i.i.d. random variables drawn according to PMF p(x), x {1, 2, ... , m}. Thus, . We know that in probability. Let , where q is another PMF on {1, 2,...,m}.

Evaluate where X1, X2,... are i.i.d. ~p(x).

So the tricky part is that the X's are still distributed according to p(x), but now I should compute instead what the entropy would be using the wrong PMF. Or is that even the entropy I'm computing? It looks more like the entropy rate.

Solution:

I tried to solve the problem like this, do you agree, and if you do, perhaps you can see an alternative solution?

// need to introduce a relation between q and p since we know what this expression evaluates to when p(x) is plugged in

// r_i is the difference between the real and the incorrect probability of r.v. number i