Let random variables X1, X2, . . . , Xn be independent p(x), x X . Let Nx denote the

number of occurences of a symbol x in a given sequence x1, x2, . . . , xn. The empirical

probability mass function is defined by

pn(x) = Nx

n

, for x X

(a) Show that

p(x1, x2, . . . , xn) = Y

xX

p(x)

Nx

and

1

n

log p(x1, x2, . . . , xn) = H(pn) + D(pn||p)

(b) For a given x1, x2, . . . , xn what is

max

p

p(x1, x2, . . . , xn)

where the maximization is over all probability mass functions on X ? What probability

mass function achieves this maximum likelihood?