Information Theory- DMS question- Binomial dist?

[Zoe-b]

Homework Statement

Let X1, . . . ,Xn be a message from a memoryless source, where Xi are in A. Show
that, as n →∞, the proportion of messages in the typical set converges to zero,
unless Xi is uniform on A.

Homework Equations

The Attempt at a Solution

Confused, possibly because I'm reading the question wrong.
Let B be a 'typical set' (proper subset of A), with P(Xi in B) = p

Then as far as I can tell, if Yn is the number of messages in B up to Xn, Yn has a Binomial (n,p) distribution and so the proportion of messages in B tends to p not to zero! But I'm not using how the actual 'letters' are distributed at all here, or the respective sizes of the sets A, B. Any hints?

 

[mighty2000]

Hello,

Thank you for your response. It seems like you are on the right track, but there are a few key concepts that you may have missed. First, it is important to note that the message from a memoryless source means that each message is independent and identically distributed, which means that each message has the same probability distribution. Second, the typical set is defined as a set of messages that are "typical" for the source, meaning that they are representative of the overall distribution of messages.

Now, let's consider the proportion of messages in the typical set as n approaches infinity. As you correctly stated, Yn has a Binomial (n,p) distribution, where p is the probability of a message being in the typical set. As n approaches infinity, the Binomial distribution approaches a Poisson distribution, with parameter λ = np. This means that the proportion of messages in the typical set can be approximated by P(Yn = 0) = e^(-λ), which approaches zero as n approaches infinity.

So, in conclusion, as n approaches infinity, the proportion of messages in the typical set converges to zero unless the probability of a message being in the typical set (p) is equal to 1, which would only be the case if Xi is uniform on A. I hope this clarifies things for you. Let me know if you have any further questions.