I am currently studying Shannon's entropy and I have just come across an exercise related to typical sets. More specifically, given a certain type $t$ for the set, the exercise asks to demonstrate that $$|B_t|≤2^{nH(t)}$$, where $$B_t=\{B:t_B=t\}$$. I have made an attempt using the entropy and the Kullback-Leibler divergency but all I was able to do was to show that $$|B_t|≤2^{n(H(t) + D(t||p))}$$, where p is the probability distribution of letters in the english language. What am I missing to conclude the last step? Thanks for the replies!

  • $\begingroup$ Your argument can’t work, since the KL divergence could be positive. Perhaps you’d like to explain us the actual question, and your current argument? $\endgroup$ – Yuval Filmus May 13 at 10:38
  • $\begingroup$ So the exercise has a couple of points. In the first one I demonstrate that the probability of a typical set B of type t is $$p(B) = 2^{-n(H(t) + D(t || p))}$$ . Then it asks me to find an upper limit to the size of the set of typical sets of type t, using the demonstrated probability. It gives an hint to start by considering that $$1 >= t(B_t) = \sum_{B in B_t} t(B)$$ where $t(B)$ is the probability of B given its $t$ empiric distribution. $\endgroup$ – Francesco Lucarelli May 13 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.