A Proofs of results from Section 2

Proof of Theorem 1

The empirical mean in canonical exponential families satisfies a large deviation principle (LDP).

Lemma 2

Let \(\mu _k\) be the mean of a distribution in a canonical one-parameter exponential family. Then the empirical mean \(\hat{\mu }_{T,k}\) of \(T\) samples of that distribution obeys an LDP with rate \(T\) and good rate function \(x \mapsto \mathrm{KL}(x, \mu _k)\).

Let \(\mathrm{int} S\) be the interior of a set \(S\), and \(\mathrm{cl} S\) be its closure. An application of the Gärtner-Ellis theorem, as done in [ GJ04 ] , leads to the following theorem.

Theorem 9

Let \(\mathcal A_\omega ^{sp}\) be a static proportions algorithm parametrized by \(\omega \in \triangle _K^0\). On problem \(\mu \in \mathcal D\), the empirical mean vector \(\hat{\mu }_T\) obeys a LDP with rate \(T\) and good rate function \(\lambda \mapsto \sum _{k=1}^K \omega _k \mathrm{KL}(\lambda _k, \mu _k)\). As a consequence, for any set \(S \subseteq \mathbb {R}^K\),

\begin{align*} - \inf _{\lambda \in \mathrm{int} S} \sum _{k=1}^K \omega _k \mathrm{KL}(\lambda _k, \mu _k) \le \liminf _{T\to +\infty } \frac{1}{T} \log \mathbb {P}_{\mu , \mathcal A_\omega ^{sp}}(\hat{\mu }_T \in S) \: , \\ \limsup _{T\to +\infty } \frac{1}{T} \log \mathbb {P}_{\mu , \mathcal A_\omega ^{sp}}(\hat{\mu }_T \in S) \le - \inf _{\lambda \in \mathrm{cl} S} \sum _{k=1}^K \omega _k \mathrm{KL}(\lambda _k, \mu _k) \: . \end{align*}

By continuity of the Kullback-Leibler divergence in exponential families, for all \(\mu \in \mathcal D\) and \(\omega \in \triangle _K\) the infimum over the interior and the closure are equal to the infimum over the set. Thus, the LDP of Theorem 9 gives the equality

\begin{align*} \lim _{T \to +\infty }\rho _{\mu , T}(\mathcal A^{sp}_\omega ) & = \lim _{T \to +\infty }\left(- \frac{1}{T} \log \mathbb {P}_{\mu , \mathcal A_\omega ^{sp}}(\hat{\mu }_T \in \mathrm{Alt}(\mu )) \right)^{-1} \\ & = \left(\inf _{\lambda \in \mathrm{Alt}(\mu )} \sum _{k=1}^K \omega _k \mathrm{KL}(\lambda _k, \mu _k) \right)^{-1} \: . \end{align*}