rate due to not knowing the source distribution is negligible.

In this section we take a finer look at universal lossless coding of multisets. We will see that for a finite-alphabet source, the redundancy cannot be made a negligible fraction of the coding rate. Since the coding rate with full distributional knowledge is $\Theta(\log n)$, we come to this conclusion using new information and redundancy measures that have normalization by $\log n$ rather than by $n$. We will find that zero-redundancy universal coding of multisets is *not* possible with respect to the class of memoryless multisets, using the more stringent redundancy definition. Zero redundancy is thus also not possible for more general classes of sources such as sources with memory or with infinite alphabets.

### Log-Blocklength Normalized Information Measures

We formulate several definitions and extend the source coding theorems to these definitions. Let $Z_1^1,\,Z_1^2,\,\ldots$ represent a sequence of random variables over a sequence of alphabets $\mathcal{Z}_1,\,\mathcal{Z}_2,\,\ldots$. (For sequence coding we would have $Z_1^n = (X_i)_{i=1}^n$ and $\mathcal{Z}_n = \mathcal{X}^n$ is an alphabet of sequences. For multiset coding we would have $Z_1^n = \{X_i\}_{i=1}^n$ and $\mathcal{Z}_n = \mathcal{K}(\mathcal{X},n)$ is an alphabet of types.) Define the log-blocklength normalized entropy rate as $$\mathfrak{H}(\mathfrak{Z}) 