lower bound is not tight due to the positive chance of ties among members of a multiset drawn from a discrete parent. If the chance of ties is small (if $|\mathcal{X}|$ is sufficiently large and $n$ is sufficiently small), the lower bound is a good approximation.

For any given source distribution and $n$, a multiset of samples $\{x_i\}_{i=1}^n$ can be cast as a superletter drawn from an alphabet of multisets, itself having a known distribution. By the lossless block-to-variable source coding theorem [@Shannon1948], the entropy of the superletter is an asymptotically tight lower bound on the rate required for representation. Since the type specifies the multiset, as mentioned in Section \[sec:ordervalue\], we can write $$H(\{X_i\}_{i=1}^n) = H(K_1,K_2,\ldots,K_{|\mathcal{X}|}) \mbox{,}
\label{eq:multinomialEquiv}$$ where $K_i$ is the number of occurrences of $x_i$ in $n$ trials. While we will exhibit a few explicit calculations, our main interest is in relating the rate requirement to the sample size $n$. For this we first consider finite alphabets and then infinite alphabets.

Finite Alphabets
----------------

If the multiset is drawn i.i.d., the distribution of types is given by a multinomial distribution derived from the parent distribution [@deMoivre1756 Problem VI]. Suppose $x_i \in \mathcal{X}$ has probability $p_i$ in the 