of universality that we have defined obey an ordering relation.

\[thm:relation\] The log-normalized redundancy quantities satisfy $$\mathcal{L}_n^{+} \ge \mathcal{L}_n^{-} \ge \mathcal{L}_n^{*}(p_{\Theta})$$ and $$\mathcal{L}^{+} \ge \mathcal{L}^{-} \ge \mathcal{L}^{*}(p_{\Theta}) \mbox{.}$$

Minor modification of [@Davisson1973 Theorem 1].

Armed with definitions and relations among several notions of log-blocklength normalized universality, we now study when it is possible to achieve universality. We give a theorem that gives a necessary and sufficient condition on the existence of weighted log-blocklength normalized universal codes.

\[thm:MIuniversal\] The minimum $n$th-order average log-blocklength normalized redundancy is bounded as $$\frac{I(Z_1^n;\Theta)}{\log n} \le \mathcal{L}_{n}^{*}(p_{\Theta}) \le \frac{I(Z_1^n;\Theta)}{\log n} + \frac{1}{\log n} \mbox{.}$$ A necessary and sufficient condition for the existence of weighted log-blocklength normalized universal codes is that $$\mathcal{L}^{*}(p_{\Theta}) = \lim_{n\to\infty} \mathcal{L}_{n}^{*}(p_{\Theta}) = \lim_{n\to\infty} \frac{I(Z_1^n;\Theta)}{\log n} = \mathfrak{I}(Z;\Theta) = 0 \mbox{.}$$

Minor modification of [@Davisson1973 Theorem 2].

Theorem \[thm:MIuniversal\] can be extended to conditions for minimax and maximin log-blocklength normalized universality and can also be strengthened by suitable modification of theorems in [@Gallager1979; @MerhavF1995].

### Class of Memoryless Multisets {#sec:universalMemorylessMultisets}

Consider the class of memoryless, binary multisets. The parameter $\theta$ is the Bernoulli trial parameter. Now suppose that there is a distribution over the parameter space $q_{\Theta}(\theta) \in T$ that is uniform over $[0,1]$. 