desired entropy $H(\{X_i\}_{i=1}^n)$ is upper-bounded by the logarithm of $|\mathcal{K}(\mathcal{X},n)|$. Thus, $$H(\{X_i\}_{i=1}^n) \leq |\mathcal{X}| \log(n+1)
                     = O(\log n)$$ since $|\mathcal{X}|$ is finite.

Note that the theorem holds for any source, not just for i.i.d. sources. For a non-trivial i.i.d. source we can use the calculation (\[eq:binomialEntropy\]) to show an $\Omega(\log n)$ lower bound, so in fact we have $H(\{X_i\}_{i=1}^n) = \Theta(\log n)$.

For an i.i.d. source, the upper bound in the proof is quite loose. To achieve the bound with equality, each of the types would have to be equiprobable; however by the strong asymptotic equipartition property [@Yeung2002], collectively, all non-strongly typical types will occur with arbitrarily small probability. The number of types in the strongly typical set is polynomial in $n$, so any upper bound would still be $\Theta(\log n)$.

Countable Alphabets {#sec:losslessCountable}
-------------------

Theorem \[thm:HRzero\] with its presented proof obviously does not extend to infinite alphabets. To get an interesting bound we must do more than enumerate types.

Define the entropy rate of a multiset as $$H(\mathfrak{X}) = \lim_{n \rightarrow \infty} \tfrac{1}{n}H(\{X_i\}_{i=1}^n) \mbox{.}$$ Theorem \[thm:HRzero\] shows that finite-alphabet sources yield multisets with zero entropy rate. Using a dictionary–pattern decomposition, we will show a related result for countable-alphabet sources.

