on computing the entropy of patterns; the entropy computation for patterns of multisets is closely related.

Universal Lossless Coding {#sec:universal}
=========================

The previous section considered source coding for multisets when the source distribution was known. Most prominently in estimation and inference but also in other applications, the underlying distribution is not known. In this section, we discuss universal source coding of multisets, first presenting an achievability result for countable alphabets and then showing that redundancy, defined in a stronger sense than usual, cannot be driven to zero.

Universal Achievability {#sec:achievability}
-----------------------

We propose a source coding scheme that achieves some degree of compression for all members of a source class at the same time. We will not compare to the entropy bound, holding off detailed discussion of redundancy until Section \[sec:Conv\].

Consider classes of countable-alphabet i.i.d. sources that meet Kieffer’s condition for universal encodability for the sequence representation problem [@Kieffer1978; @HeY2005]. For these source classes, the redundancy for encoding $(X_i)_{i=1}^n$ is $o(n)$. We formulate a universal scheme for the multiset representation problem and demonstrate an achievability result, making use of the dictionary–pattern decomposition.

As we saw in Section \[sec:losslessCountable\], a multiset can be represented as the concatenation of the pattern 