$\displaystyle\frac{\kappa(x^{n}|y^{n})n(\bar{T}_{i}-\eta_{i})q(y^{n}|\theta)}{p(x^{n}|\theta)}$
$\displaystyle-\frac{\kappa(x^{n}|y^{n})q(y^{n}|\theta)}{(p(x^{n}|\theta))^{2}}\frac{\partial
p(x^{n}|\theta)}{\partial\theta_{i}}$ $\displaystyle=$ $\displaystyle
n(\bar{T}_{i}-\eta_{i})p(y^{n}|x^{n},\theta)$
$\displaystyle-\frac{\kappa(x^{n}|y^{n})q(y^{n}|\theta)}{p(x^{n}|\theta)}\frac{\partial\log
p(x^{n}|\theta)}{\partial\theta_{i}}$ $\displaystyle=$ $\displaystyle
n(\bar{T}_{i}-\eta_{i})p(y^{n}|x^{n},\theta)$
$\displaystyle-p(y^{n}|x^{n},\theta)\int
n(\bar{T}_{i}-\eta_{i})p(y^{n}|x^{n},\theta)\nu(dy^{n})$ $\displaystyle=$
$\displaystyle
n(\bar{T}_{i}-\eta_{i})p(y^{n}|x^{n},\theta)-n(\tilde{t}_{i}-\eta_{i})p(y^{n}|x^{n},\theta)$
$\displaystyle=$ $\displaystyle
n(\bar{T}_{i}-\tilde{t}_{i})p(y^{n}|x^{n},\theta).$

Using this formula, we have

$\displaystyle\frac{\partial^{2}\log
p(x^{n}|\theta)}{\partial\theta_{j}\partial\theta_{i}}$ $\displaystyle=$
$\displaystyle\int\frac{\partial
n(\bar{T}_{i}-\eta_{i})}{\partial\theta_{j}}p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle+\int n(\bar{T}_{i}-\eta_{i})\frac{\partial
p(y^{n}|x^{n},\theta)}{\partial\theta_{j}}\nu(dy^{n})$ $\displaystyle=$
$\displaystyle\int(-nG_{ij})(\theta)p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle+\int
n(\bar{T}_{i}-\eta_{i})n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=$ $\displaystyle-nG_{ij}(\theta)$ $\displaystyle+\int
n(\bar{T}_{i}-\eta_{i})n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=$ $\displaystyle-nG_{ij}(\theta)$ $\displaystyle+\int
n(\bar{T}_{i}-\tilde{t}_{i})n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle+\int
n(\tilde{t}_{i}-\eta_{i})n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=$ $\displaystyle-nG_{ij}(\theta)$ $\displaystyle+\int
n(\bar{T}_{i}-\tilde{t}_{i})n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=$ $\displaystyle-nG_{ij}(\theta)+n\tilde{v}_{ij},$

where $\tilde{v}_{ij}=\tilde{v}_{ij}(\theta,x^{n})$ denotes

$\int\sqrt{n}(\bar{T}_{i}-\tilde{t}_{i})\sqrt{n}(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu_{y}(dy^{n}).$

That is, we have

$\displaystyle\frac{\partial^{2}\log
p(x^{n}|\theta)}{\partial\theta_{j}\partial\theta_{i}}=-nG_{ij}(\theta)+n\tilde{v}_{ij},$
(71)

Since $\tilde{v}_{ij}$ is $ij$-entry of ${\rm
Cov}_{\theta}[\bar{T}(Y^{n})|x^{n}]$, this is (67), which directly yields
(68).

To differentiate (71) again, note the following

$\displaystyle\frac{\partial\tilde{t}_{i}}{\partial\theta_{j}}$
$\displaystyle=\frac{\partial}{\partial\theta_{j}}\int\bar{T}_{i}p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=\int\bar{T}_{i}n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=n\int(\bar{T}_{i}-\tilde{t}_{i})(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle=\tilde{v}_{ij}.$

Then,

$\displaystyle\frac{\partial^{3}\log
p(x^{n}|\theta)}{\partial\theta_{k}\partial\theta_{j}\partial\theta_{i}}$
$\displaystyle=$ $\displaystyle-n\frac{\partial
G_{ij}(\theta)}{\partial\theta_{k}}$ $\displaystyle+\int\frac{\partial
n(\bar{T}_{i}-\tilde{t}_{i})}{\partial\theta_{k}}n(\bar{T}_{j}-\tilde{t}_{j})p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle+\int n(\bar{T}_{i}-\tilde{t}_{i})\frac{\partial
n(\bar{T}_{j}-\tilde{t}_{j})}{\partial\theta_{k}}p(y^{n}|x^{n},\theta)\nu(dy^{n})$
$\displaystyle+\int
n(\bar{T}_{i}-\tilde{t}_{i})n(\bar{T}_{j}-\tilde{t}_{j})\frac{\partial
p(y^{n}|x^{n},\theta)}{\partial\theta_{k}}\nu(dy^{n}).$

Since $\partial\bar{T}/\partial\theta_{k}=0$ holds, and since
$\partial\tilde{t}_{i}/\partial\theta_{k}=\tilde{v}_{ik}$ dose not depend on
$y^{n}$, the second and third terms in the last expression in the integral
yield $0$. Hence,

$\displaystyle\frac{\partial^{3}\log
p(x^{n}|\theta)}{\partial\theta_{k}\partial\theta_{j}\partial\theta_{i}}$
$\displaystyle=$ $\displaystyle-n\frac{\partial
G_{ij}(\theta)}{\partial\theta_{k}}$ $\displaystyle+\int
n(\bar{T}_{i}-\tilde{t}_{i})n(\bar{T}_{j}-\tilde{t}_{j})\frac{\partial
p(y^{n}|x^{n},\theta)}{\partial\theta_{k}}\nu(dy^{n}).$

The second term is

$\int
n(\bar{T}_{i}-\tilde{t}_{i})n(\bar{T}_{j}-\tilde{t}_{j})n(\bar{T}_{k}-\tilde{t}_{k})p(y^{n}|x^{n},\theta)\nu(dy^{n}),$

which equals $n^{3/2}\tilde{w}_{ijk}$. Then, we have

$\displaystyle\frac{\partial^{3}\log
p(x^{n}|\theta)}{\partial\theta_{k}\partial\theta_{j}\partial\theta_{i}}=-n\frac{\partial
G_{ij}(\theta)}{\partial\theta_{k}}+n^{3/2}\tilde{w}_{ijk}.$ (72)

This completes the proof of the lemma.

Recall that $G(\theta)$ equals the covariance of $T(y)$ with respect to
$q(y|\theta)$ and note that the expectation of ${\rm Cov}_{\theta}[T(y)|x]$
with respect to $p(x|\theta)$, which we denote by ${\rm
Cov}_{\theta}[T(y)|X]$, is not more than ${\rm Cov}_{\theta}[T(y)]=G(\theta)$
in the sense of positive definiteness. Hence, $J(\theta)$ is positive semi-
definite. Here, the equality holds only if $x$ and $T(y)$ are independent of
each other. To be more precisely, if and only if $x$ and $z^{t}T(y)$ (the
linear combination of each entry of $T(y)$) is independent,
$z^{t}G(\theta)z=z^{t}{\rm Cov}_{\theta}[T(y)|X]z$ holds. Therefore, we assume
that $x$ and $z^{t}T(y)$ with any non-zero $z$ is not independent for
$\theta\in\Theta^{\circ}$.

Since we assume that $T(y)$ is bounded,

$E_{\theta}[\max_{\theta^{\prime}\in
B_{\epsilon}(\theta)}|\hat{J}_{ij}(\theta,x)|]$

and

$E_{\theta}[\max_{\theta^{\prime}\in
B_{\epsilon}(\theta)}(\hat{J}_{ij}(\theta,x)|)^{2}]$

are finite. This means that Assumptions 1 and 1’ hold. By (66),

$\sup_{n\in\mathbb{N}}\sup_{x^{n}\in{\cal X}^{n}}\sup_{\theta\in
K}\Bigl{|}\frac{1}{n}\frac{\partial\log
p(x^{n}|\theta)}{\partial\theta_{i}}\Bigr{|}$

is finite for any compact set $K\subset\Theta^{\circ}$. That is, the log
likelihood function is equicontinuous for all $\theta\in K$, $n$, and $x^{n}$.
Hence, noting positive definiteness of $J(\theta)$, we can prove the maximum
likelihood estimator is uniformly consistent for all $\theta\in K$. In
conclusion, all the assumptions for Theorems 1 and 2 are satisfied and we have
demanded lower bound results.

####  VI-D2 Upper Bounds for Models with Hidden Variables

Note that any order’s moments of $\bar{T}(Y^{n})$ exist at
$p(y^{n}|x^{n},\theta)$. (This is true even if $T(x)$ is not bounded.) Hence,
by (67) of Lemma VI-D1, Assumption 7 holds for any $b>0$. Further, we can show
that $|\hat{J}(x^{n},\theta)|$ and
$|{\partial\hat{J}(\theta,x^{n})/\partial\theta_{k}}|$ is uniformly bounded
for all $x^{n}$ such that $\hat{\theta}\in K$, which means all the assumptions
for the upper bound results hold. In fact, by (72), we have

$\frac{\partial\hat{J}_{ij}(\theta,x^{n})}{\partial\theta_{k}}=\frac{\partial
G_{ij}(\theta)}{\partial\theta_{k}}-n^{2}\tilde{w}_{ijk}(\theta,x^{n}).$

Since the posterior density $p(y^{n}|x^{n},\theta)$ is i.i.d.,
$n^{2}\tilde{w}(\theta,x^{n})$ equals the third order moment of $T(y)$, which
does not depend on $n$. Recalling we assume $T(y)$ is bounded,
$|\partial\hat{J}_{ij}(\theta,x^{n})/\partial\theta_{k}|$ is bounded for
$\theta\in K$.

Hence, we see that our general minimax strategy works for models with hidden
variables assuming that $T(y)$ is bounded and $z^{t}T(y)$ for any nonzero $z$
is not independent of $x$ for all $\theta\in\Theta$.

Note that $\hat{J}(\theta,x^{n})$ is positive definite for all $x^{n}$ and for
all $\theta\in\Theta$, which implies the uniqueness of MLE.

####  VI-D3 Extension to the Whole Strings Set Case for Mixture Families

Next, we consider the mixture family case defined as (65). About the lower
bound, we should examine the consistency of maximum likelihood estimator

$\hat{\theta}(x^{n})=\arg\max_{\theta\in\Theta}p(x^{n}|\theta),$

which is defined relative to the whole parameter space $\Theta$. For the
mixture family, as we see later, log likelihood function is concave. Using
that property, we can prove $\hat{\theta}$ is uniformly consistent for
$\theta\in\Theta$. Therefore, we can apply Theorem 1 for $K=\Theta$ case.
(J.T.: Is this true?)

Now we consider the upper bound for the case that ${\mathcal{K}}={\cal
X}^{n}$. Define a subset $\Theta_{\tau}$ of $\Theta$ as

$\displaystyle\Theta_{\tau}=\\{\theta\in\Theta:\,\theta_{i}\geq\tau,\,i=0,1,\ldots,d\\}.$

Since $\Theta_{\tau}$ for $\tau>0$ is a compact subset of $\Theta^{\circ}$, it
may be possible to design a minimax strategy for the model
$\\{p(x|\theta):\theta\in\Theta_{\tau}\\}$ utilizing the result for the
general case. In fact, we can do it as we show later.

Then we argue the situation that $\tau$ converges to zero as $n$ goes to
infinity. Under that situation we utilize Lemmas 2 and 3. Then we have to
control the behavior of $\kappa_{J}(K)$ and $\lambda^{*}_{K}$ (the maximum of
the largest eigenvalue of $J(\theta)$ among $\theta\in K$), since $K$ changes
as $n$ increases.

To treat the strings with the maximum likelihood estimate being near the
boundary, we employ the technique introduced in [51], which utilizes the
Dirichlet($\alpha$) prior
$w_{(\alpha)}(\theta)\propto\prod_{i=0}^{d}\theta_{i}^{-(1-\alpha)}$ with
$\alpha<1/2$. Note that this prior with $\alpha=1/2$ has the same form as the
Jeffreys prior for the multinomial model. When $\alpha<1/2$ it has higher
density than the Jeffreys prior as $\theta$ approaches the boundary of
$\Theta$.

Our asymptotic minimax strategy is the mixture

$\displaystyle m_{n}(x^{n})$ $\displaystyle=$
$\displaystyle(1-2n^{-r})m_{\Theta}(x^{n})$ $\displaystyle+$ $\displaystyle
n^{-r}\int\\!\\!p_{e}(x^{n}|\theta,\beta)\bar{w}(\theta,\beta)d\theta d\beta$
$\displaystyle+$ $\displaystyle
n^{-r}\int\\!\\!p(x^{n}|\theta)w_{(\alpha)}(\theta)d\theta,$

where $m_{\Theta}$ is the Jeffreys mixture over $\Theta$. Here, the first and
second terms are for the strings with the MLE being away from the boundary,
while the third term works when the MLE approaches the boundary.

We can show the following theorem. The strategy $m_{n}$ defined as (VI-D3)
with $r<(1/2-\alpha)(1-p)$ asymptotically achieves the minimax regret for the
mixture family, i.e.

$\sup_{x^{n}\in{\cal
X}^{n}}\log\frac{p(x^{n}|\hat{\theta})}{m_{n}(x^{n})}\leq\frac{d}{2}\log\frac{n}{2\pi}+\log
C_{J}(\Theta)+o(1).$

To prove Theorem VI-D3, we use the following useful inequalities for the model
with hidden variables. Here $A\leq B$ for two matrices $A$ and $B$ means that
$B-A$ is positive semidefinite. Given a data string $x^{n}$, let
$\hat{\theta}$ denote the MLE for a model with hidden variables
$p(x^{n}|\theta)$ defined by (64). Then, the following holds for all
$x^{n}\in\mathcal{X}^{n}$.

$\displaystyle\forall\theta\in\Theta,\>\>\frac{1}{n}\log\frac{p(x^{n}|\hat{\theta})}{p(x^{n}|\theta)}$
$\displaystyle\leq D(q(\cdot|\hat{\theta})||q(\cdot|\theta)),$ (74)
$\displaystyle\forall\theta\in\Theta,\>\>\hat{J}(\theta,x^{n})$
$\displaystyle\leq G(\theta).$ (75)

In particular, when $q(y|\theta)$ is the multinomial model, the following
holds

$\displaystyle\frac{p(x^{n}|\hat{\theta})}{p(x^{n}|\theta)}\leq\exp(nD(q(\cdot|\hat{\theta})||q(\cdot|\theta)))=\prod_{y\in\mathcal{Y}}\frac{\hat{\eta}_{y}^{n\hat{\eta}_{y}}}{\eta_{y}^{n\hat{\eta}_{y}}},$
(76)

where $\eta_{y}=q(y|\theta)$ and $\hat{\eta}_{y}=q(y|\hat{\theta})$.

The proof is in Appdendix L.

Note that

$\displaystyle\hat{J}_{ij}(\theta,x)$ $\displaystyle=$
$\displaystyle-\frac{\partial^{2}\log
p(x|\theta)}{\partial\theta_{i}\partial\theta_{j}}$ $\displaystyle=$
$\displaystyle\frac{(p_{i}(x)-p_{0}(x))(p_{j}(x)-p_{0}(x))}{(p(x|\theta))^{2}}$

holds, where we have

$\displaystyle\Bigl{|}\frac{p_{i}(x)-p_{0}(x)}{p(x|\theta)}\Bigr{|}\leq\frac{p_{i}(x)+p_{0}(x)}{\sum_{i=0}^{d}\theta_{i}p_{i}(x)}\leq\frac{1}{\theta_{i}}+\frac{1}{\theta_{0}}.$

The last expression is not more than $2\max_{\theta\in
K}\max_{i}\theta_{i}^{-1}$, which is finite. Further, $\partial
V(x^{n}|\theta)/\partial\theta_{i}$ is similarly bounded, so $V(x^{n}|\theta)$
is equicontinuous for all $x^{n}$ : $\hat{\theta}\in K$. This implies the
general mixture strategy works for mixture families with a compact $K$
interior to $\Theta$.

Next, we give a discussion on the case with the set of strings
$\\{x^{n}:\hat{\theta}(x^{n})\in{\Theta}^{\circ}\\}$. We are to examin
Assumptions V and V for $\theta\in\Theta_{\tau}$. Note that, for
$z\in\Re^{d}$,

$\displaystyle z^{t}\hat{J}(\theta,x)z$ $\displaystyle=$
$\displaystyle\frac{\sum_{ij}z_{i}z_{j}(p_{i}(x)-p_{0}(x))(p_{j}(x)-p_{0}(x))}{p(x|\theta)^{2}}$
$\displaystyle=$
$\displaystyle\frac{(\sum_{i}z_{i}(p_{i}(x)-p_{0}(x)))^{2}}{p(x|\theta)^{2}}\geq
0,$

Hence we have

$z^{t}\hat{J}(\theta,x^{n})z\geq 0$

for all $z\in\Re^{d}$ and for all $\theta\in\Theta$. Since

$\frac{\partial\hat{J}_{ij}(\theta,x)}{\partial\theta_{k}}=\frac{-2(p_{k}(x)-p_{0}(x))}{(p(x|\theta))}\hat{J}_{ij}(\theta,x),$

we have

$\displaystyle\frac{\partial
z^{t}\hat{J}(\theta,x)z}{\partial\theta_{k}}=\frac{-2(p_{k}(x)-p_{0}(x))}{(p(x|\theta))}z^{t}\hat{J}(\theta)z,$
(77)

which yields

$\displaystyle\frac{\partial z^{t}\hat{J}(\theta,x^{n})z}{\partial\theta_{k}}$
(78) $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{t}\frac{-2(p_{k}(x_{t})-p_{0}(x_{t}))}{(p(x_{t}|\theta))}z^{t}\hat{J}(\theta,x_{t})z.$

Hence we have for $\theta\in\Theta_{\tau}$,

$\displaystyle\frac{\partial
z^{t}\hat{J}(\theta,x^{n})z}{\partial\theta_{k}}\leq\frac{1}{n}\sum_{t}\frac{2z^{t}\hat{J}(\theta,x_{t})z}{\tau}=\frac{2z^{t}\hat{J}(\theta,x^{n})z}{\tau}$

By this inequality and the fact $z^{t}\hat{J}(\tilde{\theta},x^{n})z\geq 0$,
we have the following inequalities.

$\displaystyle
e^{-2\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}z^{t}\hat{J}(\hat{\theta},x^{n})z$
$\displaystyle\leq z^{t}\hat{J}(\tilde{\theta},x^{n})z$ (79)
$\displaystyle\leq$
$\displaystyle\,e^{2\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}z^{t}\hat{J}(\hat{\theta},x^{n})z.$

By this, we can see that $\bar{h}_{K}$ for $K=\Theta_{\tau}$ is not more than
$e^{2\sqrt{d}}$, as long as $\epsilon\leq\tau$. Further, if
$|\tilde{\theta}-\hat{\theta}|\leq\tau/2\sqrt{d}$,

$z^{t}\hat{J}(\tilde{\theta},x^{n})z\leq
z^{t}\hat{J}(\hat{\theta},x^{n})z\Bigl{(}1+\frac{e\tau}{2\sqrt{d}}\Bigr{)}$

holds for all $z\in\Re^{d}\setminus\\{0\\}$. Note that

$\max_{\tilde{\theta}\in
B_{\epsilon}(\hat{\theta})}|\tilde{\theta}-\hat{\theta}|=\frac{\epsilon}{\lambda_{\rm
min}},$

where $\lambda_{\rm min}$ is the minimum value among $\theta\in\Theta_{\tau}$
of the smallest eigenvalue of $J(\theta)$. Hereafter, we assume
$\epsilon\leq\tau\lambda_{\rm min}/2\sqrt{d}$.

When $\epsilon\leq\tau\lambda_{\rm min}/2\sqrt{d}$ is satisfied,

$z^{t}\hat{J}(\tilde{\theta},x^{n})z\leq
z^{t}\hat{J}(\hat{\theta},x^{n})z\Bigl{(}1+\frac{e\epsilon}{\lambda_{\rm
min}}\Bigr{)}$

holds for all $\tilde{\theta}\in B_{\epsilon}(\hat{\theta})$. This implies
Assumption V holds with $\kappa_{J}=e/\lambda_{\rm min}$ for
$\epsilon\leq\tau\lambda_{\rm min}/2\sqrt{d}$. Note that the argument here
works even if $\tau$ and $\epsilon$ depend on $n$.

Next we examine Assumption V. Concerning this matter, we have the following
lemma. Assume that $||V(x^{n}|\hat{\theta})||_{s}\geq\delta$, $\delta\geq
8\sqrt{d}\epsilon/\tau$, $4\sqrt{d}\epsilon/\tau\leq 1/2$, and $\delta\leq
1/2$. Then, we have for $\tilde{\theta}\in B_{\epsilon}(\hat{\theta})$

$||T(x^{n}|\tilde{\theta})||_{s}\geq||T(x^{n}|\hat{\theta})||_{s}/4.$

Proof: Note that there exists a unit vector $\bar{z}\in\Re^{d}$ such that
$|\bar{z}^{t}V(x^{n}|\hat{\theta})\bar{z}|=||V(x^{n}|\hat{\theta})||_{s}$.
Here we have two cases; i)
$\bar{z}^{t}V(x^{n}|\hat{\theta})\bar{z}=||V(x^{n}|\hat{\theta})||_{s}$ and
ii) $-\bar{z}^{t}V(x^{n}|\hat{\theta})\bar{z}=||V(x^{n}|\hat{\theta})||_{s}$.

First consider the case i), for which we have

$\displaystyle||V(x^{n}|\hat{\theta})||_{s}$
$\displaystyle=\bar{z}^{t}J(\hat{\theta})^{-1/2}\hat{J}(\hat{\theta})J(\hat{\theta})^{-1/2}\bar{z}-1$
$\displaystyle=\frac{\bar{z}^{t}J(\hat{\theta})^{-1/2}\hat{J}(\hat{\theta})J(\hat{\theta})^{-1/2}\bar{z}}{\bar{z}^{t}\bar{z}}-1$
$\displaystyle=\frac{\tilde{z}^{t}\hat{J}(\hat{\theta})\tilde{z}}{\tilde{z}^{t}J(\hat{\theta})\tilde{z}}-1,$

where $\tilde{z}$ denotes $J(\hat{\theta})^{-1/2}\bar{z}$. Hence,

$\displaystyle\frac{\tilde{z}^{t}\hat{J}(\hat{\theta})\tilde{z}}{\tilde{z}^{t}J(\hat{\theta})\tilde{z}}=1+||V(x^{n}|\hat{\theta})||_{s}$
(80)

holds. For the numerator in the left side, from (79) we have

$\tilde{z}^{t}\hat{J}(\tilde{\theta})\tilde{z}\geq
e^{-2\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}\tilde{z}^{t}\hat{J}(\hat{\theta})\tilde{z}.$

As for the denominator, similarly as (79) we can show by (77)

$\displaystyle
e^{-2\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}\leq\frac{\tilde{z}^{t}J(\tilde{\theta})\tilde{z}}{\tilde{z}^{t}J(\hat{\theta})\tilde{z}}\leq
e^{2\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}$ (81)

for $\tilde{\theta}\in\Theta_{\tau}$. Then, we have for all $\tilde{\theta}\in
B_{\epsilon}(\hat{\theta})\cap\Theta_{\tau}$,

$\displaystyle\frac{\tilde{z}^{t}\hat{J}(\tilde{\theta})\tilde{z}}{\tilde{z}^{t}J(\tilde{\theta})\tilde{z}}$
$\displaystyle\geq(1+||V(x^{n}|\hat{\theta})||_{s})e^{-4\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}$
$\displaystyle\geq(1+||V(x^{n}|\hat{\theta})||_{s})e^{-\delta/2}$
$\displaystyle\geq(1+||V(x^{n}|\hat{\theta})||_{s})(1-\delta/2)$
$\displaystyle=1+||V(x^{n}|\hat{\theta})||_{s}-\delta/2-\delta||V(x^{n}|\hat{\theta})||_{s}/2$
$\displaystyle\geq
1+||V(x^{n}|\hat{\theta})||_{s}/2-\delta||V(x^{n}|\hat{\theta})||_{s}/2$
$\displaystyle=1+(1-\delta)||V(x^{n}|\hat{\theta})||_{s}/2$
$\displaystyle=1+||V(x^{n}|\hat{\theta})||_{s}/4.$

Letting
$\xi=J(\tilde{\theta})^{1/2}\tilde{z}/|J(\tilde{\theta})^{1/2}\tilde{z}|$,
that is,
$\tilde{z}=|J(\tilde{\theta})^{1/2}\tilde{z}|J(\tilde{\theta})^{-1/2}\xi$, we
have

$\displaystyle\frac{\tilde{z}^{t}\hat{J}(\tilde{\theta})\tilde{z}}{\tilde{z}^{t}J(\tilde{\theta})\tilde{z}}$
$\displaystyle=\frac{\xi^{t}J(\tilde{\theta})^{-1/2}\hat{J}(\tilde{\theta})J(\tilde{\theta})^{-1/2}\xi}{\xi^{t}\xi}$
$\displaystyle=\xi^{t}J(\tilde{\theta})^{-1/2}\hat{J}(\tilde{\theta})J(\tilde{\theta})^{-1/2}\xi$
$\displaystyle\leq 1+||V(x^{n}|\tilde{\theta})||_{s}$

Hence, we have
$||T(x^{n}|\tilde{\theta})||_{s}\geq||T(x^{n}|\hat{\theta})||_{s}/4$.

For the case ii), we can show the same conclusion. This completes the proof.

Remark: This means that Assumption 10 holds with $\zeta=1/4$.

To see Assumption V holds is easy because of (79).

Finally, we evaluate $a=\min\\{1/2\lambda^{*},1\\}$ in Lemma V. Since
$|\hat{J}_{ij}(\theta)|$ is bounded by $4/\tau^{2}$ for
$\theta\in\Theta_{\tau}$ and since the smallest eigenvalue of $J(\theta)$ is
lower bounded by a certain positive constant, $\lambda^{*}$ is of order
$\tau^{-4}$. Hence, $a$ is lower bounded by $\tau^{4}$ times a certain
constant.

Now, we will give the proof of Theorem VI-D3.

Proof of Theorem VI-D3: We divide the strings to the following three
categories:

$\displaystyle A_{n}$
$\displaystyle=\\{x^{n}:\hat{\theta}\in\Theta_{\tau}\text{ and
}||V(x^{n}|\hat{\theta})||_{s}\leq\delta\\},$ $\displaystyle B_{n}$
$\displaystyle=\\{x^{n}:\hat{\theta}\in\Theta_{\tau}\text{ and
}||V(x^{n}|\hat{\theta})||_{s}>\delta\\},$ $\displaystyle C_{n}$
$\displaystyle=\\{x^{n}:\hat{\theta}\not\in\Theta_{\tau}\\}.$

Set $\tau=n^{-(1-p)}$, $\delta=n^{-1/2+\gamma}$, and
$\epsilon=n^{-1/2+\iota}$, assuming $1/2+\iota<p<1$, $0<\gamma<1/2$, and
$1-p<\gamma/2$, that is, $2(1-p)<\gamma<1/2$. Note that
$\epsilon/\tau=n^{-1/2+\iota+1-p}=n^{-(p-1/2-\iota)}\rightarrow 0$ as $n$ goes
to infinity under this setting. Let $\tilde{\epsilon}=\epsilon/\tau$ and
assume $n$ is large enough so that
$\tilde{\epsilon}=\epsilon/\tau\leq\lambda_{\rm min}/2\sqrt{d}$ holds. Let
$C_{1}=2\sqrt{d}/\lambda_{\rm min}$. Then, $\tilde{\epsilon}\leq 1/C_{1}$.

When $x^{n}$ belongs to $A_{n}$, the Laplace approximation for the integral
with respect to $\theta$ is correct enough. In fact by (79),

$\displaystyle z^{t}\hat{J}(\tilde{\theta},x^{n})z$ $\displaystyle\leq
e^{2\sqrt{d}|\tilde{\theta}-\hat{\theta}|/\tau}z^{t}\hat{J}(\hat{\theta},x^{n})z$
$\displaystyle\leq e^{2\sqrt{d}\epsilon/\lambda_{\rm
min}\tau}z^{t}\hat{J}(\hat{\theta},x^{n})z$
$\displaystyle=e^{C_{1}\tilde{\epsilon}}z^{t}\hat{J}(\hat{\theta},x^{n})z$

holds for all $\tilde{\theta}\in B_{\epsilon}(\hat{\theta})$. Hence for
$x^{n}\in A_{n}$, similarly as the proof of Lemma V, we have

$\displaystyle\log\frac{p(x^{n}|\hat{\theta})}{m_{\Theta}(x^{n})}$
$\displaystyle\leq\frac{d}{2}\log\frac{n}{2\pi}+\log\frac{|J(\hat{\theta})|^{1/2}}{w_{J}(\hat{\theta})\Phi(U_{\Theta,\epsilon,n}(\hat{\theta}))}$
$\displaystyle+\log\frac{e^{dC_{1}\tilde{\epsilon}/2}(1+\delta)^{d/2}}{1-\eta_{\epsilon}}.$

Here, since $B_{\epsilon}(\hat{\theta})\subset\Theta$ holds when $n$ is large,
$\Phi(U_{\Theta,\epsilon,n}(\hat{\theta}))$ converges to $1$ as $n$ goes to
infinity, the above means

$\displaystyle\log\frac{p(x^{n}|\hat{\theta})}{(1-2n^{-r})m_{\Theta}(x^{n})}$
$\displaystyle\leq\frac{d}{2}\log\frac{n}{2\pi}+\log C_{J}(\Theta)+o(1).$

Next, we consider the case that $x^{n}\in B_{n}$. By Lemma VI-D3, Assumption V
holds with $\zeta=1/4$. Then, similarly as the proof of Lemma V, we can show
(47) with
$\bar{m}(x^{n})=\int\\!\\!p_{e}(x^{n}|\theta,\beta)\bar{w}(\theta,\beta)d\theta
d\beta$, $\zeta=1/4$ and $\bar{h}_{K}=\bar{h}_{\Theta}<\infty$. Hence, we can
show the same inequality as (52) for $x^{n}\in B_{n}$. In this case, with a
certain $C>0$, we have

$an^{2\gamma}\geq C\tau^{4}n^{2\gamma}=Cn^{2\gamma-4(1-p)},$

which is polynomially large, since we set $1-p<\gamma/2$. This makes the
regret of $m_{n}$ go to negative infinity as $n$ goes to infinity.

Finally, we consider the case that $x^{n}\in C_{n}$, in which there exists $y$
such that $\hat{\theta}_{y}\leq\tau=n^{-(1-p)}$. Then, we can use the help
from the third term in (VI-D3) as follows. Note that the following holds from
(76).

$\frac{\int\\!\\!p(x^{n}|\theta)w_{(\alpha)}(\theta)d\theta}{p(x^{n}|\hat{\theta})}\geq\frac{{\int\prod_{i=0}^{d}\theta_{i}^{n\hat{\theta}_{i}}w_{(\alpha)}(\theta)d\theta}}{\prod_{i=0}^{d}{\hat{\theta}_{i}^{n\hat{\theta}_{i}}}}.$

Then, by Lemma 4 of [51], the right side is not less than

$\frac{1}{Rn^{{d/2}-({1/2}-\alpha)(1-p)}}$

for $x^{n}\in C_{n}$, where $R$ is a constant depending only on $d$. Let $r$
be smaller than $(1/2-\alpha)(1-p)$, then for large $n$ the third term of the
right side of (VI-D3) is larger than ${(2\pi)^{d/2}/(C_{J}(\Theta)n^{d/2})}.$
This provides an upper bound on regret of $m_{n}$ smaller than the maximin
value for all $x^{n}\in C_{n}$. This completes the proof.

###  VI-E Mixture with Fixed Weights

We consider the following model.

$p(x|\theta)=0.5g_{0}(x)+0.5g_{1}(x|\theta),$

where $q(x|\theta)$ is an exponential family with the natural parameter
$\theta$: $g_{1}(x|\theta)=\exp(\theta\cdot T(x))-\psi(\theta)$, and
$g_{0}(x)$ is a certain fixed probability density function. This is another
example of non-exponential families. Let $\eta$ denote the expectation
parameter for $g_{1}(x|\theta)$. For this case, we assume $T(x)$ is bounded
again.

We have

$\displaystyle\frac{\partial\log p(x|\theta)}{\partial\theta_{i}}$
$\displaystyle=\frac{0.5(T_{i}-\eta_{i})g_{1}(x|\theta)}{p(x|\theta)}$
$\displaystyle=(T_{i}-\eta_{i})r(x|\theta),$

where we have defined

$r(x|\theta)=\frac{0.5g_{1}(x|\theta)}{p(x|\theta)}.$

Note that $0\leq r(x|\theta)\leq 1$ and

$\int r(x|\theta)p(x|\theta)\nu(dx)=0.5$

hold. The score function for $x^{n}$ is

$\displaystyle\frac{\partial\log
p(x^{n}|\theta)}{\partial\theta_{i}}=\sum_{t=1}^{n}(T_{i}(x_{t})-\eta_{i})r(x_{t}|\theta),$

We have

$\displaystyle\frac{\partial r(x|\theta)}{\partial\theta_{i}}=$
$\displaystyle\frac{0.5(T_{i}-\eta_{i})g_{1}(x|\theta)}{p(x|\theta)}$
$\displaystyle-\frac{0.5g_{1}(x|\theta)0.5(T_{i}(x)-\eta_{i})g_{1}(x|\theta)}{(p(x|\theta))^{2}}$
$\displaystyle=$ $\displaystyle(T_{i}-\eta_{i})(r(x|\theta)-r(x|\theta)^{2})$
$\displaystyle=$ $\displaystyle(T_{i}-\eta_{i})r(x|\theta)(1-r(x|\theta))$
$\displaystyle=$ $\displaystyle(T_{i}-\eta_{i})q(x|\theta).$

where $q(x|\theta)=r(x|\theta)(1-r(x|\theta))$. Hence,

$\displaystyle\frac{\partial^{2}\log
p(x|\theta)}{\partial\theta_{j}\partial\theta_{i}}=$ $\displaystyle-
G_{ij}(\theta)r(x|\theta)$
$\displaystyle+(T_{i}-\eta_{i})(T_{j}-\eta_{j})q(x|\theta),$

by which, we have

$\displaystyle\hat{J}(\theta,x^{n})=$ $\displaystyle\,G_{ij}(\theta)\bar{r}$
(82) $\displaystyle-$
$\displaystyle\frac{1}{n}\sum_{t=1}^{n}(T_{i}(x_{t})-\eta_{i})(T_{j}(x_{t})-\eta_{j})q(x_{t}|\theta),$
(83)

where $\bar{r}=(1/n)\sum_{t=1}^{n}r(x_{t}|\theta)$. We also have

$J_{ij}(\theta)=\frac{G_{ij}(\theta)}{2}-\int(T_{i}-\eta_{i})(T_{j}-\eta_{j})q(x|\theta)p(x|\theta)\nu(dx).$

Hence, $\hat{J}(\theta,x^{n})-J(\theta)$ is bounded for any
$\theta\in\Theta^{\circ}$, which means that Assumption 7 holds for any $b>0$.
Further, since
$\int(T_{i}-\eta_{i})(T_{j}-\eta_{j})p(x|\theta)\nu(dx)=G_{ij}(\theta)$ and
$0\leq q(x|\theta)\leq 1/4$, $J(\theta)$ is positive definite for all
$\theta$.

Now we have

$\displaystyle\frac{\partial q(x|\theta)}{\partial\theta_{i}}$
$\displaystyle=(T_{i}-\eta_{i})q(x|\theta)(1-r(x|\theta))$
$\displaystyle-(T_{i}-\eta_{i})r(x|\theta)q(x|\theta)$
$\displaystyle=(T_{i}-\eta_{i})q(x|\theta)(1-2r(x|\theta)).$

Using the above, we have

$\displaystyle\frac{\partial^{3}\log
p(x|\theta)}{\partial\theta_{k}\partial\theta_{j}\partial\theta_{i}}$
$\displaystyle=$ $\displaystyle-\frac{\partial
G_{ij}(\theta)}{\partial\theta_{k}}r(x|\theta)-G_{ij}(\theta)(T_{k}-\eta_{k})q(x|\theta)$
$\displaystyle-G_{ik}(\theta)(T_{j}-\eta_{j})q(x|\theta)$
$\displaystyle-(T_{i}-\eta_{i})G_{jk}(\theta)q(x|\theta)$
$\displaystyle+(T_{i}-\eta_{i})(T_{j}-\eta_{j})(T_{k}-\eta_{k})q(x|\theta)(1-2r(x|\theta)).$

Hence, noting $T(x)$ is assumed to be bounded, $\hat{J}(\theta,x^{n})$ is
equicontinuous in $\theta\in\Theta$ for all $n$ and for all $x^{n}$.
Therefore, we can apply Theorem 5 to show the asymptotic minimax strategy.

###  VI-F Contaminated Gaussian Location Families

In this subsection, we treat a simple case of contamination Gaussian location
families, which is a basic model for robust estimation.

Let us define the model formally below. Let

$\displaystyle p(x|\theta)=(1-\nu)g_{0}(x|\theta)+\nu g_{1}(x|\theta),$ (84)

where

$\displaystyle g_{0}(x|\theta)$ $\displaystyle=N(\theta,I),$ $\displaystyle
g_{1}(x|\theta)$ $\displaystyle=N(\theta,s^{2}I)$

are Gaussian densities over $\mathbb{R}^{d}$, $I$ the unit matrix of order
$d$, $\nu$ a small positive number, and $s$ a number larger than $1$. Here,
$(1-\nu)g_{0}(x|\theta)$ is the main target for estimation and $\nu
g_{1}(x|\theta)$ represents a noise distribution. This $p(x|\theta)$ is an
example of non-exponential families, In [34], MDL estimation based on two-
stage codes for this model is discussed.

Note that our setting that $\nu$ and the forms of $g_{0}$ and $g_{1}$ are
known is the simplest one in robust statistics. See [29] for more general
settings.

Now we evaluate the score function and the empirical Fisher information. Let
$\partial_{i}$ denote $\partial/\partial\theta_{i}$ and $r=r(x|\theta)$
$=(1-\nu)g_{0}(x|\theta)/p(x|\theta)$. We have

$\displaystyle\partial_{i}\log p(x|\theta)$
$\displaystyle=\frac{\partial_{i}(1-\nu)g_{0}(x|\theta)+\partial_{i}\nu
g_{1}(x|\theta)}{p(x|\theta)}$
$\displaystyle=-r(\theta_{i}-x_{i})-\frac{(1-r)(\theta_{i}-x_{i})}{s^{2}}$
$\displaystyle=-(\theta_{i}-x_{i})w,$

where

$w=w(x|\theta)=r(x|\theta)+\frac{1-r(x|\theta)}{s^{2}}=\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}r(x|\theta)+\frac{1}{s^{2}}.$

Hence,

$\displaystyle\partial_{j}\partial_{i}\log p(x|\theta)$
$\displaystyle=-I_{ji}w-(\theta_{i}-x_{i})\partial_{j}w$
$\displaystyle=-I_{ij}w-(\theta_{i}-x_{i})\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}\partial_{j}r.$

For the last term, we have

$\displaystyle\partial_{j}r$
$\displaystyle=-\frac{\partial_{j}p(x|\theta)}{p(x|\theta)^{2}}(1-\nu)g_{0}(x|\theta)+\frac{\partial_{j}(1-\nu)g_{0}(x|\theta)}{p(x|\theta)}$
$\displaystyle=-r(x|\theta)\partial_{j}\log
p(x|\theta)-r(x|\theta)(\theta_{j}-x_{j})$
$\displaystyle=r(x|\theta)((\theta_{j}-x_{j})w-(\theta_{j}-x_{j}))$
$\displaystyle=r(x|\theta)(\theta_{j}-x_{j})(w-1)$
$\displaystyle=r(x|\theta)(\theta_{j}-x_{j})(1-r(x|\theta))\Bigl{(}\frac{1}{s^{2}}-1\Bigr{)}$
$\displaystyle=(\theta_{j}-x_{j})q\Bigl{(}\frac{1}{s^{2}}-1\Bigr{)},$ (85)

where $q=q(x|\theta)=r(x|\theta)(1-r(x|\theta))$. Hence, we have

$\displaystyle\partial_{j}\partial_{i}\log p(x|\theta)$
$\displaystyle=-wI_{ij}+(\theta_{i}-x_{i})(\theta_{j}-x_{j})\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}^{2}q,$

which yields

$\displaystyle\hat{J}_{ij}(\theta,x)$ (86)
$\displaystyle=wI_{ij}-\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}^{2}(\theta_{i}-x_{i})(\theta_{j}-x_{j})q.$

By this, we will evaluate the Fisher information. First note that $J(\theta)$
dose not depend on $\theta$. Since $Er=1$, we have $Ew=1$. Hence, our task is
to evaluate the expectation of the second term. Since

$r(x|\theta)(1-r(x|\theta))p(x|\theta)\leq\min\\{(1-\nu)g_{0}(x|\theta),\nu
g_{1}(x|\theta)\\}$

holds, we have

$\displaystyle\int\\!\\!(\theta_{i}-x_{i})(\theta_{j}-x_{j})q\,p(x|\theta)dx\leq\min\\{1-\nu,\nu
s^{2}\\}I_{ij}.$

Hence, the following holds.

$I\geq J(\theta)\geq\max\\{\nu,1-\nu s^{2}\\}I.$

The third part is positive definite and equals $I$ if and only if $\nu=0$.
Note that $I$ equals the Fisher information of
$g_{0}(x|\theta)=N(x|\theta,I)$.

The empirical Fisher information $\hat{J}_{1}(\theta)=\hat{J}(\theta,x)$ has
an interesting property. To see it, consider the $d=1$ case. Assume $x=0$
without loss of generality. Then, we have

$\displaystyle\hat{J}_{1}(\theta)=r+\frac{1-r}{s^{2}}-\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}^{2}\theta^{2}q.$
(87)

Assume $s$ is very large and $\nu$ is very small. Then, if $|\theta|<1$ and
$r(0|\theta)\fallingdotseq 1$, then $\hat{J}_{1}(\theta)$ nearly equals the
empirical Fisher information of $N(0|\theta,1)$, which is $1$. On the other
hand, let us consider the case that $r(0|\theta)\fallingdotseq 0$, which is
realized when $\theta^{2}$ is large. In particular, assume that $\theta^{2}$
is much larger than $\log(s/\nu)$, then

$\displaystyle\theta^{2}r(0|\theta)$
$\displaystyle\leq\frac{\theta^{2}(1-\nu)g_{0}(0|\theta)}{\nu
g_{1}(0|\theta)}$
$\displaystyle\leq\frac{s\theta^{2}}{\nu}\exp\Bigl{(}-\frac{\theta^{2}}{2}+\frac{\theta^{2}}{2s^{2}}\Bigr{)}\fallingdotseq
0.$

Hence, $\hat{J}(\theta,0)\fallingdotseq 1/s^{2}$, when $\theta^{2}$ is much
larger than $\log(s/\nu)$.

The above is reasonable observations and not surprising. More interestingly,
when $\theta$ takes an intermediate value, $\hat{J}_{1}(\theta)$ can be a
large negative value. Let us see it below.

Let $c$ be a solution to the equation $r(0|\theta)=1/2$, which is

$\frac{1-\nu}{\sqrt{2\pi}}\exp\Bigl{(}-\frac{c^{2}}{2}\Bigr{)}=\frac{\nu}{\sqrt{2\pi
s^{2}}}\exp\Bigl{(}-\frac{c^{2}}{2s^{2}}\Bigr{)}.$

This is modified to

$s^{2}=\frac{\nu^{2}}{(1-\nu)^{2}}\frac{}{}\exp\Bigl{(}c^{2}-\frac{c^{2}}{s^{2}}\Bigr{)}.$

Hence, we have

$c^{2}=\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}^{-1}\Bigl{(}\log
s^{2}+\log\frac{(1-\nu)^{2}}{\nu^{2}}\Bigr{)},$

which implies $c^{2}\geq\log s^{2}$, because we assume $\nu$ is small.
Therefore, the following holds.

$\hat{J}_{1}(\pm c)\leq\frac{1}{2}\Bigl{(}1+\frac{1}{s^{2}}\Bigr{)}-\frac{\log
s^{2}}{4}\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}^{2}.$

The right side is negative when $\log s^{2}\geq 4$. Further, its absolute
value can be arbitrarily large by letting $s$ be large.

Now, we can show that the MLE is not unique for the string $x^{2}$ with
$x_{1}=c$ and $x_{2}=-c$. When $s^{2}$ is large, $\hat{J}(0,x^{2})$ is
negative, which means that $\theta=0$ is not the maximizer of the log
likelihood, because $-\hat{J}(0)>0$ is the second derivative of the log
likelihood at $\theta=0$. Hence, the maximum is taken at a certain
$\tilde{\theta}\neq 0$. Then by symmetry, $-\tilde{\theta}$ also achieves the
maximum.

Next, we consider $\hat{J}(\theta,x^{n})$. From (86) we can obtain the
following representation.

$\displaystyle\hat{J}(\theta,x^{n})=\Bigl{(}\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}\bar{r}+\frac{1}{s^{2}}\Bigr{)}I-\Bigl{(}1-\frac{1}{s^{2}}\Bigr{)}^{2}\hat{\Sigma},$
(88)

where we have defined

$\displaystyle\bar{r}$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}r(x_{t}|\theta),$
$\displaystyle\tilde{\Sigma}$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}q(x_{t}|\theta)(x_{t}-\theta)(x_{t}-\theta)^{t}.$

Now, we concern whether (88) is equicontinuous or not for
$x^{n}\in{\mathcal{K}}$. By (85), the derivative of the first term with
respect to $\theta_{i}$ is proportional to $\theta_{i}-x_{i}$, which is
unbounded. It may seem to cause a problem, but it is not, since
$\theta_{i}-x_{i}$ is with a factor $q(x|\theta)$ which is of order
$\exp(-C|\theta-x|^{2})$. As a result, the derivative of the first term is
bounded. This holds for all the terms which contain the factor
$\theta_{i}-x_{i}$. Hence, the derivative of the empirical Fisher information
is bounded, which implies it is equicontinuous for all $x^{n}$ and for all $n$
as functions of $\theta$.

##  Appendix A On Assumptions for lower bounds of Theorem 1

Suppose that Assumption IV-A holds. This means that
$E_{\theta}\sup_{\theta^{\prime}\in
B_{r}(\theta)}|\hat{J}_{ij}(\theta^{\prime},x)|$ is finite for $r$ not more
than $r(\theta)$, for all $i,j$ in $\\{1,\ldots,d\\}$. Now
$J(\theta)^{-1/2}\hat{J}_{1}(\theta^{\prime},x)J(\theta)^{-1/2}$ is a linear
combination of the $\hat{J}_{ij}(\theta^{\prime},x)$. Consequently,

$\displaystyle E_{\theta}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\pm((J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x)J(\theta)^{-1/2})_{ij}-I_{ij})$
(89)

is finite for $\delta$ not more than $r(\theta)$. Also by Assumption IV-A,
$\hat{J}(\theta^{\prime},x)$ is continuous in $\theta^{\prime}$ for each $x$.
Accordingly, as $\delta$ decreases to $0$, the supremum in the above
expression convergences monotonically to
$\pm((J(\theta)^{-1/2}\hat{J}(\theta,x)J(\theta)^{-1/2})_{ij}-I_{ij})$ which
has zero expectation. Then by the monotone convergence theorem, the expected
supremum in (89) converges to $0$ as $\delta\rightarrow 0$ for each $\theta$
in $\Theta^{\circ}$.

The plus-minus $\pm$ means that the indicated property holds with each sign
choice. It is the flipped sign case $\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}(I_{ij}-((J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x)J(\theta)^{-1/2})_{ij})$
that especially matters for our development. Nevertheless, it is appropriate
to see that it can be handled with either sign. One might be tempted to take
an absolute value, but
$|(J(\theta)^{-1/2}\hat{J}(\theta,x)J(\theta)^{-1/2})_{ij}-I_{ij}|$ does not
have zero expectation.

On $K$, the assumption that $C_{J}(K)$ is finite means that the Jeffreys
measure is a finite measure on $K$. Accordingly, by Egorov’s Theorem [8, 9],
the convergent sequences (6), (7), and (89) are uniformly convergent to $0$ as
$\delta\rightarrow 0$, except for $\theta$ in sets of arbitrarily small
measure. In particular, for any $\epsilon>0$, there is a $\delta>0$ and a good
set $G\subset K$, such that for all $\theta$ in $G$ the quantities in (6) and
(7) are less than $\epsilon$, the expected suprema in (89) are less than
$\epsilon/(2d)$ and the Jeffreys measure of the complement of $G$, which is
$\int_{K\smallsetminus G}|J(\theta)|^{1/2}d\theta$, is less than
$\epsilon\,C_{J}(K)$.

Next consider
$(J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x^{n})J(\theta)^{-1/2})_{ij}$ for a
sample of size $n$. By the definition of the empirical Fisher information,
this is

$\frac{1}{n}\sum_{t=1}^{n}\bigl{(}J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x_{t})J(\theta)^{-1/2}\bigr{)}_{ij}.$

The law of large numbers informs us that it is near its expectation with high
probability. We use the expected supremum property to get uniformity over
$B_{\delta}(\theta)$. Indeed, the supremum of an average is less than the
average of the supremum. In particular, $\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\pm(I_{ij}-(J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x^{n})J(\theta)^{-1/2})_{ij}$
is not more than

$\frac{1}{n}\sum_{t=1}^{n}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\pm\bigr{(}I_{ij}-(J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x_{t})J(\theta)^{-1/2})_{ij}\bigr{)}.$

When the $x_{t}$ are independent from the distribution $P_{\theta}$, this is a
sample average having expectation bounded by $\epsilon/(2d)$. Accordingly, by
the law of large numbers, for each $i,j$, and for each sign choice, it is
within $\epsilon/d$ of $0$ except in an event of ($P_{\theta}$) probability
tending to $0$ as $n\rightarrow\infty$. Accordingly, taking the exception
event as the finite union of these tail events for $1\leq i,j\leq d$ and for
each sign, we have that $\max_{i,j}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}|(I_{ij}-(J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x^{n})J(\theta)^{-1/2})_{ij}|$
is not more than $\epsilon/d$ except in an event having a ($P_{\theta}$)
probability, say $\delta_{n}$, which tends to zero as $n\rightarrow\infty$.

Now the spectral norm of a $d$ by $d$ matrix is within a factor $d$ of the
maximum absolute value of its entries. Accordingly,

$\displaystyle\sup_{|\zeta|=1}\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\zeta^{t}\bigl{(}I-(J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x^{n})J(\theta)^{-1/2})\bigr{)}\zeta$
(90)

is less than $\epsilon$, except in the event of probability $\delta_{n}$. Any
unit vector $\zeta$ may be obtained as
$J(\theta)^{1/2}z/|\\!|J(\theta)^{1/2}z|\\!|$ for some non-zero vector $z$.
Accordingly, switching from $\zeta$ to $z$, this gives

$\sup_{\theta^{\prime}\in B_{\delta}(\theta)}\inf_{z\neq
0}\frac{z^{t}\hat{J}(\theta^{\prime},x^{n})z}{z^{t}J(\theta)z}\geq 1-\epsilon$

except in the event of vanishing $P_{\theta}$ probability, asymptotically.

##  Appendix B On Assumptions for lower bounds of Theorem 2

The analysis in the proof of Theorem 2 is similar. The extra assumptions of
continuity of the expected supremum function and continuity of the Fisher
information are used, along with Dini’s Theorem, to deduce that the
convergence to $0$ of the expected supremum as well as the convergences to $0$
of the expressions in (6) and (7), are in fact uniform convergences within the
whole presummed compact $K$ (with no need for an Egorov style exception set
$K\smallsetminus G$). In particular there is a $\delta>0$, sufficiently small,
such that the expected value of the supremum in expression (90) is less than
$\epsilon/2$, uniformly over $\theta$ in $K$.

Another distinction is the use of the assumption of the continuous and finite
expected square, to permit an appeal to Chebyshev’s inequality. The variance
of the supremum in expression (90) is not more than $v_{\theta}/n$, where
$v_{\theta}$ is the variance of the supremum when $n=1$. From Assumption
$1^{\prime}$ this variance is finite and continuous so it has a finite bound
$v_{K}$ on the compact domain $K$. Accordingly, by Chebyshev’s inequality, the
probability that expression (90) exceeds $\epsilon$ is not more than
$4v_{K}/(n\epsilon^{2})$, uniformly over $\theta$ in $K$. This converges to
zero faster than the required $1/\log n$. [A simlar sufficiently fast tail
probability conclusion can be arranged if using a $1+\alpha$ moment of the
empirical Fisher information for any $\alpha>0$].

##  Appendix C Asymptotic Normality and Uniform Tightness of the Distribution
of the MLE

First we restate and then prove Lemma 2 from Section IV, which is for general
i.i.d. families.

Under Assumptions IV-A, IV-A, IV-A,
$\sqrt{n}J(\theta)^{1/2}(\hat{\theta}-\theta)$ converges in distribution to a
mean zero normal random vector and there is a constant $c$ such that the
following inequality holds for any positive $b$,

$\displaystyle\max_{\theta\in
K}P_{\theta}\bigl{(}\sqrt{n}||J(\theta)^{1/2}(\hat{\theta}-\theta)||>b\sqrt{\log
n}\bigr{)}$ $\displaystyle\quad\leq\frac{c}{b^{2}\log
n}+o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

The constant $c$ equals $\max_{\theta\in K}{\rm
trace}(J(\theta)^{-1}I(\theta))$ which is the dimension $d$, the trace of an
identity matrix, when $I(\theta)=J(\theta)$.

Proof: Assume that $x^{n}$ is drawn from $p(\cdot|\theta)$. Let
$l_{x^{n}}(\theta)$ be the log likelihood function $\log p(x^{n}|\theta)$.
Then, the first order Taylor expansion of the score function $\nabla
l_{x^{n}}(\theta)$ at $\hat{\theta}$ shows

$\displaystyle\nabla
l_{x^{n}}(\theta)=\nabla\nabla^{t}l_{x^{n}}(\tilde{\theta})(\theta-\hat{\theta}),$

where $\nabla f(\theta)$ and $\nabla\nabla^{t}f(\theta)$ denote the gradient
and the Hessian of $f$, respectively, and $\tilde{\theta}$ is a point on the
line between $\theta$ and $\hat{\theta}$. From the definition of the empirical
Fisher information, this equation is

$\displaystyle\nabla
l_{x^{n}}(\theta)=n\hat{J}(\tilde{\theta},x^{n})(\hat{\theta}-\theta),$ (91)

which is equivalent to

$\displaystyle J(\theta)^{-1/2}\frac{1}{\sqrt{n}}\nabla
l_{x^{n}}(\theta)\quad$
$\displaystyle\quad=[J(\theta)^{-1/2}\hat{J}(\tilde{\theta},x^{n})J(\theta)^{-1/2}][\sqrt{n}J(\theta)^{1/2}(\hat{\theta}-\theta)].$

Let’s call the random vector on the left side $Z_{n}$. It is asymptotic normal
by the central limit theorem (for sums of i.i.d. random vectors with finite
covariance) and it has covariance
$EZ_{n}Z_{n}^{t}=J(\theta)^{-1/2}I(\theta)J(\theta)^{-1/2}$.

By Assumption $3^{\prime}$ the estimator $\hat{\theta}$ is in a $\delta$
neighborhood of $\theta$ with probability greater than $1-o(1/\log n)$
uniformly for $\theta\in K$. Then by (25), which is a consequence of
Assumption 1’, $J(\theta)^{-1/2}\hat{J}(\tilde{\theta},x^{n})J(\theta)^{-1/2}$
is close to $I$, indeed not less than $(1-\epsilon)I$, for all $\theta\in K$
with probability at least $1-o(1/\log n)$. (The inequality of matrices is in
the sense that the difference is a non-negative definite matrix.) Accordingly,
the random vector of interest defined by
$\xi_{n}=\xi_{n}(\theta)=\sqrt{n}J(\theta)^{1/2}(\hat{\theta}-\theta)$
satisfies $\xi_{n}=A_{n}Z_{n}$ where $A_{n}\leq(1-\epsilon)^{-1}I$. It follows
that $E\xi_{n}\xi_{n}^{t}\leq(1-\epsilon)^{-2}EZ_{n}Z_{n}^{t}$ and that
$E||\xi_{n}||^{2}\leq(1-\epsilon)^{-2}E||Z_{n}||^{2}$ which is
$(1-\epsilon)^{-2}{\rm trace}(J(\theta)^{-1}I(\theta))$, not more than
$(1-\epsilon)^{-2}c$. Thus by Chebyshev’s inequality

$\displaystyle\max_{\theta\in
K}P_{\theta}\bigl{(}\sqrt{n}||J(\theta)^{1/2}(\hat{\theta}-\theta)||>b\sqrt{\log
n}\bigr{)}$ $\displaystyle\quad\leq\frac{(1-\epsilon)^{-2}c}{b^{2}\log
n}+o\Bigl{(}\frac{1}{\log n}\Bigr{)}.$

This means that $\limsup_{n}(\log n)\max_{\theta\in
K}P_{\theta}(||\xi_{n}(\theta)||\geq b\sqrt{\log
n})\leq{(1-\epsilon)^{-2}c/b^{2}}$. Since this bound holds for all positive
$\epsilon$, it follows that this limsup is less than $c/b^{2}$, which is the
desired result. This completes the proof of Lemma 2

Remark on Uniform Tightness: Consider the family of approximately standardized
random variables
$\xi_{n}(\theta)=\sqrt{n}J(\theta)^{1/2}(\hat{\theta}-\theta)$. Convergence in
distribution provides a form of stochastic tightness, that is,
$P_{\theta}(||\xi_{n}(\theta)||>a)$ tends to zero as $a\rightarrow\infty$,
uniformly in $n$. Here we used slightly stronger assumptions to get that the
convergence is also uniformly valid for $\theta\in K$ and that moderately
sized tails with $a_{n}=b\sqrt{\log n}$ have tail probability bounded by a
small multiple of $1/\log n$.

##  Appendix D Consistency of the MLE

The present setting is for a model in which the $x_{1},\ldots,x_{n}$ given
$\theta$ are independent and identically distributed.

Here we state conditions that are sufficient for the consistency of the MLE
for each $\theta$. The subsequent section addresses uniform consistency for
$\theta$ in compacta.

For consistency, we use Assumptions D-D described below. The first assumption
concerns continuity.

_Continuity._ For almost every $x\in{\cal X}$ and for all $\theta\in\Theta$,
$p(x|\theta)$ is upper half continuous at $\theta$:

$\lim_{\delta\rightarrow
0}\sup_{\theta^{\prime}:|\theta-\theta^{\prime}|<\delta}p(x|\theta^{\prime})=p(x|\theta).$

Moreover, the relative entropy $D(\theta||\theta^{\prime})$ is a continuous
function of $\theta$ and $\theta^{\prime}$ in $\Theta$.

For each $\theta$ and $\theta^{\prime}$ in the interior of $\Theta$, there is
a $\delta>0$ such that the following holds

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime\prime}\in\Theta:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}\Bigr{)}<\infty.$

The above two assumptions are sufficient for consistency when the parameter
space $\Theta$ is compact. Accordingly, for bounded parameter spaces, it is
natural to include in the parameter space any boundary points that do
correspond to probability densities.

For non-compact parameter spaces, the following additional assumption is used
to handle those cases in which the densities lose mass as the parameter
approaches boundary points not in $\Theta$. For $B\geq 1$, we let $\Theta_{B}$
be an increasing sequence of compact subsets whose union is $\Theta$.

For one example, consider the family of exponential densities
$p(x|\theta)=\theta e^{-\theta x}$ for $x>0$. It has the natural parameter
space $\Theta=\\{\theta:\theta>0\\}$ and the sets

$\Theta_{B}=\\{\theta:1/B\leq\theta\leq B\\}$

are increasing compact sets whose union is $\Theta$. Moreover, as
$\theta^{\prime}\rightarrow 0$ or as $\theta^{\prime}\rightarrow\infty$ it has
$\lim p(x|\theta^{\prime})=0$ for each $x>0$.

When the parameter space is $\Theta=R^{d}$ we may take

$\Theta_{B}=\\{\theta:|\theta|\leq B\\}.$

Let an increasing sequence of compact subsets $\Theta_{B}$ be given whose
union is $\Theta$. For each $\theta\in\Theta^{\circ}$, there is a $B$
sufficiently large such that

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime}\in\Theta\setminus\Theta_{B}}\log\frac{p(x|\theta^{\prime})}{p(x|\theta)}\Bigr{)}<\infty.$

Moreover, there is a value $a>0$, such that, for any sequence $\theta_{B}$,
$B\geq 1$, with $\theta_{B}\in\Theta\setminus\Theta_{B}$, in the limit the
likelihood ratio satisfies
$\limsup_{B}p(x|\theta_{B})/p(x|\theta)\leq\exp\\{-a\\}$, for each $x\in{\cal
X}$.

We call this latter property the loss of mass for any sequences diverging from
the set. Often, as in the example above, the indicated limit property holds
trivially, with full loss of mass $\lim p(x|\theta_{B})=0$, if there be
sequences $\theta_{B}$ heading out of compacta in $\Theta$.

For compact $\Theta$, taking $\Theta_{B}=\Theta$, the set
$\Theta\setminus\Theta_{B}$ is empty and Assumption D is regarded as holding
vacuously, with the supremum of an empty set taken to be $-\infty$.

Under D, D, D, the maximum likelihood estimate is a consistent estimator of
$\theta$. We prove the following. For a family of densities
$S=\\{p(\cdot|\theta):\theta\in\Theta\\}$, suppose Assumptions D, D, and D
hold. Then, for each $\theta$ in $\Theta^{\circ}$, we have convergence to zero
in probability of the relative entropy between the densities at the maximum
likelihood estimate $\hat{\theta}(x^{n})$ and at $\theta$. That is,

$\lim_{n\rightarrow\infty}D(\theta||\hat{\theta})=0,\quad\hbox{in}\>\>P_{\theta}\>\>\hbox{probability.}$

Moreover, if $D(\theta||\theta^{\prime})$ is continuous in $\theta^{\prime}$,
and if $P_{\theta^{\prime}}=P_{\theta}$ only at $\theta^{\prime}=\theta$, then
also $\hat{\theta}(x^{n})$ converges to $\theta$ in probability. That is, for
every $\epsilon>0$.

$P_{\theta}(|\hat{\theta}(x^{n})-\theta|>\epsilon)=o(1).$

Proof: For positive $\xi$, let $U$ be a subset of $\Theta$ defined as
$U\stackrel{{\scriptstyle\mbox{\scriptsize\rm
def}}}{{=}}\\{\theta^{\prime}\in\Theta:D(\theta||\theta^{\prime})\geq\xi\\}$.
By the continuity of $D(\theta||\theta^{\prime})$ as a function of
$\theta^{\prime}$, when $\Theta$ is compact, so also is $U$. When $\Theta$ is
not compact, in place of $U$ we use $U\cap\Theta_{B}$ for which will discuss
the size of $B$ later below. By Assumption D, we have, for each
$\theta^{\prime}$ in $U$,

$\lim_{\delta\rightarrow
0}\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}=\log\frac{p(x|\theta^{\prime})}{p(x|\theta)}.$

Therefore, we have

$\lim_{\delta\rightarrow
0}E_{\theta}\Bigl{(}\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}\Bigr{)}=\,-\,D(\theta||\theta^{\prime}),$

by the monotone convergence theorem, since
$\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log(p(x|\theta^{\prime\prime})/p(x|\theta))$
decreases as $\delta$ decreases for each $x\in{\cal X}$ and since it has
finite expectation by Assumption D.

For each $\xi>0$ and each $\theta^{\prime}\in U$, let
$\delta(\theta^{\prime})=\delta(\theta^{\prime},\xi)>0$ be so small that

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta(\theta^{\prime})}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}\Bigr{)}\leq-D(\theta||\theta^{\prime})+\xi/2$

holds. Then, since $D(\theta||\theta^{\prime})\geq\xi$ in $U$, we have

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta(\theta^{\prime})}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}\Bigr{)}\leq-\xi/2.$

Now consider
$\frac{1}{n}\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta(\theta^{\prime})}\log\frac{p(x^{n}|\theta^{\prime\prime})}{p(x^{n}|\theta)}$
for samples of size $n$. Since we are presently treating models in which the
$x_{1}$ through $x_{n}$ are independent. It is

$\sup_{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|<\delta(\theta^{\prime})}\frac{1}{n}\sum_{i=1}^{n}\log\frac{p(x_{i}|\theta^{\prime\prime})}{p(x_{i}|\theta)}.$

Then since the supremum of the average is less than the average of the
supremum, we can apply the law of large numbers and deduce that it has a limit
in ($P_{\theta}$) probability not greater than $-\xi/2$, for each
$\theta^{\prime}$ in $U$. We will need to arrange an analogous property
holding uniformly over $\theta^{\prime}$ in $U$, and we will come back to that
matter momentarily.

For non-compact domains $\Theta$, consider the sequence
$\sup_{\theta^{\prime}\in\Theta\setminus\Theta_{B}}\log\frac{p(x|\theta^{\prime})}{p(x|\theta)}$.
It is decreasing in $B$ and it has limit less than or equal to $-a$ as
$B\rightarrow\infty$, by Assumption D. Then with $0\leq\xi\leq a$, by the
monotone convergence theorem, we can arrange that $B$ is sufficiently large
that

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime}\in\Theta\setminus\Theta_{B}}\log\frac{p(x|\theta^{\prime})}{p(x|\theta)}\Bigr{)}<-\xi/2.$

Accordingly, again using that a supremum of an average is less than the
average of a supremum, we can deduce that
$\frac{1}{n}\sup_{\theta^{\prime}\in\Theta\setminus\Theta_{B}}\log\frac{p(x^{n}|\theta^{\prime\prime})}{p(x^{n}|\theta)}$
has a limsup in probability not greater than $-\xi/2$.

To obtain that $D(\theta||\hat{\theta})$ is less than $\xi$ it is enough to
confirm that the likelihood at $\theta$ is higher than the supremum of the
likelihoods for all $\theta^{\prime}$ with
$D(\theta||\theta^{\prime})\geq\xi$. Indeed, this gives an instance of a
parameter value in the Kullback ball (namely at the center point $\theta$)
that has higher likelihood than at all points outside the Kullback ball.
Accordingly the maximum must be in that ball. So if suffices for Kullback
consistency to show that with high probability

$\sup_{\theta^{\prime}:D(\theta||\theta^{\prime})\geq\xi}\log\frac{p(x^{n}|\theta^{\prime})}{p(x^{n}|\theta)}<0.$

In the compact $\Theta$ case, this supremum is over all $\theta^{\prime}$ in
$U$. Now the compact $U$ is covered by the (infinite) union of all the
variable radius balls
$\\{\theta^{\prime\prime}:|\theta^{\prime\prime}-\theta^{\prime}|\leq\delta(\theta^{\prime})\\}$
for $\theta^{\prime}$ in $U$. For a compact set every cover has a finite
subcover. Thus, there exist a finite number of points
$\theta_{1},\theta_{2},...,\theta_{N}$ such that the family of sets ${\cal
U}=\\{U_{i}\\}$ ($i=1,2,...,N$) covers $\bar{U}$, where
$U_{i}\stackrel{{\scriptstyle\mbox{\scriptsize\rm
def}}}{{=}}\\{\theta:|\theta-\theta_{i}|<\delta(\theta_{i})\\}$.

Similarly, in the non-compact $\Theta$ case, we obtain such a cover of the
compact $U\cap\Theta_{B}$ and append the set
$U_{0}=\\{\theta^{\prime}\in\Theta\setminus\Theta_{B}:D(\theta||\theta^{\prime})\geq\xi\\}$
to obtain thereby $U_{0}\cup U_{1}\cup\ldots\cup U_{N}$ as a cover of
$\\{\theta^{\prime}\in\Theta:D(\theta||\theta^{\prime})\geq\xi\\}$.

Now, we have

$\displaystyle\sup_{\theta^{\prime}:D(\theta||\theta)>\xi}\left(\frac{1}{n}\log\frac{p(x^{n}|\theta^{\prime})}{p(x^{n}|\theta)}\right)$
$\displaystyle\leq$ $\displaystyle\max_{0\leq k\leq
N}\left(\frac{1}{n}\sup_{\theta^{\prime}\in
U_{k}}\log\frac{p(x^{n}|\theta^{\prime})}{p(x^{n}|\theta)}\right)$
$\displaystyle\leq$ $\displaystyle\max_{0\leq k\leq
N}\left(\frac{1}{n}\sum_{i=1}^{n}\sup_{\theta^{\prime}\in
U_{k}}\log\frac{p(x_{j}|\theta^{\prime})}{p(x_{j}|\theta)}\right).$

Now as we showed each of these finitely many averages
$\frac{1}{n}\sum_{i=1}^{n}\sup_{\theta^{\prime}\in
U_{k}}\log\frac{p(x_{j}|\theta^{\prime})}{p(x_{j}|\theta)}$ is less than $0$
except in an event $E_{k,n}$ of probability $P_{\theta}(E_{k,n})$ which tends
to zero as $n\rightarrow\infty$. Accordingly, the finite union of these
exception sets $E_{n}=\cup_{k=0}^{N}U_{k,n}$ has probability
$P_{\theta}(E_{n})$ tending to zero as well. Outside $E_{n}$, we have
$\sup_{\theta^{\prime}:D(\theta||\theta)>\xi}\log\frac{p(x^{n}|\theta^{\prime})}{p(x^{n}|\theta)}<0$.

So for each $\xi>0$, the maximum likelihood estimate is in the Kullback ball
of size $\xi$ except in an event of probability tending to zero as
$n\rightarrow\infty$. This means that $D(\theta||\hat{\theta})$ converges to
$0$ in probability.

Now for any $\epsilon>0$, with $D(\theta||\theta^{\prime})$ continuous in
$\theta^{\prime}$ and zero only at $\theta^{\prime}=\theta$, it follows that
in any compact $K\subseteq\Theta$ (such as $K=\Theta_{B}$)

$\inf_{\theta^{\prime}\in
K:|\theta^{\prime}-\theta|\geq\epsilon}D(\theta||\theta^{\prime})>0$

Moreover, for non-compact $\Theta$ the condition on the limit of
$p(x|\theta^{\prime})/p(x|\theta)$ as $\theta^{\prime}$ diverges from
compacta, prevents $D(\theta||\theta^{\prime})$ from tending to zero for such
sequences. Accordingly, the convergence of $D(\theta||\hat{\theta})$ to zero
(in probability) implies $|\hat{\theta}(x^{n})-\theta|\rightarrow 0$ (in
probability). This completes the proof of the Lemma.

_R_ emarks: The first consistency proof of this type is in Wald [47]. Our
conditions are similar, but slightly weaker in that we use suprema of log
density ratios (demonstrated close to relative entropies). In contrast Wald
use suprema of log densities together with finite entropy conditions.
Secondly, here we organized the proof to exhibit the primacy of the conclusion
of information consistency ($D(\theta||\hat{\theta})$ tending to zero in
probability) with the parameter consistency conclusion
$\hat{\theta}\rightarrow\theta$ of Wald as a consequence.

Extension to parameter spaces that are separable metric spaces is
straightforward, provided the finite balls of radius $B$ are compact (so that
covers have finite subcovers). Extension to almost sure convergence is also
straightforward. Also, the conclusion extends to the case that the governing
distribution $P$ is not in the family $\\{P_{\theta}:\theta\in\Theta\\}$, but
is an information limit of a sequence of members of the family (that is, there
exists $P_{\theta_{k}}$ with $D(P||P_{\theta_{k}})$ tending to $0$ as $k$
grows).

##  Appendix E Consistency Conditions and the Shtarkov Value

Recall that the minimax regret value is defined by
$r_{n}(K)=\min_{q}\sup_{x^{n}\in{\cal{X}}^{n}}\sup_{\theta\in K}\log
p(x^{n}|\theta)/q(x^{n})$, where the minimum is over $q$ which are non-
negative and integrate to not more than $1$ with respect to $\nu$. Per the
theory of Shtarkov [39], the exact minimax value is $r_{n}(K)=\log c_{n,K}$
achieved by the normalized maximum likelihood distribution
$q(x^{n})=\sup_{\theta\in K}p(x^{n}|\theta)/c_{n,K}$ where
$c_{n,K}=\int\sup_{\theta\in K}p(x^{n}|\theta)\eta(d\theta)$ is the Shtarkov
constant. As explained in the introduction, it is the properties of $r_{n}(K)$
that are of interest to us here. In particular, the use of Bayes mixture
approximations to the minimax distribution arises from aim of approximate
implementation as well as the aim of determining approximations of the
Shtarkov value suitable for use in Rissanen’s stochastic complexity
formulation of the minimum description length (MDL) principle.

In this appendix we show a relationship between the consistency conditions and
finiteness of the Shtarkov constant.

Let’s focus attention on the case that the parameter space is taken to be a
set $K$ (possibly a subset of the whole parameter space) for which $c_{n,K}$
is finite.

For independent random variables, if the total sample size $N=nm$ is a
multiple of a block size $m$, one has the option to organize the sequence
$x_{1},x_{2},\ldots,x_{N}$ as the sequence of independent blocks
$\underline{x}^{m}_{1},\underline{x}^{m}_{2},\ldots\underline{x}^{m}_{n}$,
each of size $m$, where

$\underline{x}^{m}_{i}=(x_{(i-1)m+1},x_{(i-1)m+2},\ldots,x_{im}).$

Accordingly, for $m\geq 1$, the Assumptions D and D generalize as follows.

_Assumption_ D[_m_]: For the specified blocksize $m$ and for each $\theta$ and
$\theta^{\prime}$ in the interior of $K$, there is a $\delta>0$ such that the
following holds

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime\prime}\in\Theta:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log\frac{p(x^{m}|\theta^{\prime\prime})}{p(x^{m}|\theta)}\Bigr{)}<\infty.$

_Assumption_ D[_m_]: Let an increasing sequence of compact subsets $K_{B}$ be
given whose union is $K$. For the specified $m$ and for each $\theta\in
K^{\circ}$, there is a $B$ sufficiently large such that

$E_{\theta}\Bigl{(}\sup_{\theta^{\prime}\in K\setminus
K_{B}}\log\frac{p(x^{m}|\theta^{\prime})}{p(x^{m}|\theta)}\Bigr{)}<\infty.$

Moreover, there is the loss of mass property for sequences diverging from $K$.
That is, there is a value $a>0$, such that, for any sequence $\theta_{B}$,
$B\geq 1$, with $\theta_{B}\in K\setminus K_{B}$, in the limit, the likelihood
ratio satisfies $\limsup_{B}p(x^{m}|\theta_{B})/p(x^{m}|\theta)<\exp\\{-a\\}$,
for each $x^{m}\in{\cal X}$.

With these assumptions we have the following consistency conclusion.

For a family of densities $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$, and a
blocksize $m$, suppose Assumptions D, D[_m_] and D[_m_]. Consider the sequence
of maximum likelihood estimates $\hat{\theta}(x^{N})$ with sample sizes $N=nm$
a multiple of $m$. Then, for each $\theta$ in $\Theta^{\circ}$, we have
convergence to zero in probability of the relative entropy between the
densities at the maximum likelihood estimate $\hat{\theta}$ and at $\theta$.
That is,

$\lim_{n\rightarrow\infty}D(\theta||\hat{\theta})=0,\quad\hbox{in}\>\>P_{\theta}\>\>\hbox{probability.}$

Moreover, if $D(\theta||\theta^{\prime})$ is continuous in $\theta^{\prime}$,
and if $P_{\theta^{\prime}}=P_{\theta}$ only at $\theta^{\prime}=\theta$, then
also $\hat{\theta}(x^{n})$ converges to $\theta$ in probability. That is, for
every $\epsilon>0$.

$P_{\theta}(|\hat{\theta}(x^{n})-\theta|>\epsilon)=o(1).$

Proof: Taking the sequence of sample sizes $nm$ which are a multiple of $m$,
the proof is essentially the same as in the $m=1$ case.

If the Shtarkov value $c_{1,K}$ at $m=1$ is finite, then it implies the
satisfaction of assumptions D and D, and hence (together with the continuity
assumption D and the loss of mass assumption if $K$ is not compact), a finite
Shtarkov value implies the full consistency of the MLE, per the conclusions of
Lemma D. Likewise, for $m\geq 1$, finiteness of the Shtarkov value $c_{m,K}$
implies the satisfaction of assumptions D[_m_] and D[_m_] and, hence (along
with the continuity assumption D and the loss of mass assumption if $K$ is not
compact), it implies the consistency of the MLE for the sequence of sample
sizes that are multiples of $m$, per the conclusions of Lemma E.

Proof: The expected suprema in D[_m_] and D[_m_] are

$E_{\theta}\Bigl{(}\log\frac{\sup_{\theta^{\prime\prime}\in K\cap
B_{\theta^{\prime},\delta}}p(x^{m}|\theta^{\prime\prime})}{p(x^{m}|\theta)}\Bigr{)}$

and

$E_{\theta}\Bigl{(}\log\frac{\sup_{\theta^{\prime}\in K\setminus
K_{B}}p(x^{m}|\theta^{\prime})}{p(x^{m}|\theta)}\Bigr{)}$

which by Jensen’s inequality have the upper bounds

$\log\int\sup_{\theta^{\prime\prime}\in K\cap
B_{\theta^{\prime},\delta}}p(x^{m}|\theta^{\prime\prime})\nu(dx^{m})$

and

$\log\int{\sup_{\theta^{\prime}\in K\setminus
K_{B}}p(x^{m}|\theta^{\prime})}\nu(dx^{m}),$

respectively. Thus (local) domination of the joint densities is sufficient for
(local) domination of the log likelihood ratios.

Next, we can further upperbound these by a global dominating quantity (when
finite)

$\log\int{\sup_{\theta^{\prime}\in K}p(x^{m}|\theta^{\prime})}\nu(dx^{m})$

which is $\log c_{m,K}$, the Shtarkov minimax regret. The indicated
consistency properties then follow when it is finite.

##  Appendix F Uniform Consistency of the MLE

We turn our attention to assumptions for uniform consistency, on compact
subsets of $\Theta$, as used in the development of Theorem 2.

Recall that we assumed continuity of the mean of the log density ratio
$D=D(\theta||\theta^{\prime})$ in assumption D. Here we will also assume
continuity of its variance

$V(\theta||\theta^{\prime})=E_{\theta}[(\log
p(x|\theta)/p(x|\theta^{\prime})-D)^{2}].$

$V(\theta||\theta^{\prime})$ is a continuous function of $\theta^{\prime}$ and
$\theta$ in $\Theta$.

Within each compact subset of $\Theta$, there exists a $\bar{\delta}>0$ such
that for $0<\delta\leq\bar{\delta}$ the following expressions are finite and
continuous as a function of $\theta$ and $\theta^{\prime}$

$E_{\theta}\Bigl{[}\sup_{\theta^{\prime\prime}\in\Theta:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}\Bigr{]}$

and

$E_{\theta}\Bigl{[}\Bigl{(}\sup_{\theta^{\prime\prime}\in\Theta:|\theta^{\prime\prime}-\theta^{\prime}|<\delta}\log\frac{p(x|\theta^{\prime\prime})}{p(x|\theta)}\Bigr{)}^{2}\Bigr{]}.$

The above assumption F, along with D and F, is sufficient to show uniform
consistency for $\theta$ within any compact subset when the parameter space on
which the likelihood is maximized is also compact.

There can also be interest to know whether uniform consistency within compact
subsets $K$ can hold when the parameter space $\Theta$ is not compact. For
that purpose we have the following assumption.

Let $K$ be a compact subset of $\Theta$. There exists a certain positive
number $B$ such that

$\sup_{\theta\in
K}E_{\theta}\Bigl{[}\Bigl{(}\sup_{\theta^{\prime}\in\Theta\setminus\Theta_{B}}\log\frac{p(x|\theta^{\prime})}{p(x|\theta)}\Bigr{)}^{2}\Bigr{]}<\infty$

and

$\sup_{\theta\in
K}E_{\theta}\sup_{\theta^{\prime}\in\Theta\setminus\Theta_{B}}\log\frac{p(x|\theta^{\prime})}{p(x|\theta)}<0$

hold.

We prove the following uniform consistency of maximum likelihood estimators.

Consider a family of densities $S=\\{p(\cdot|\theta):\theta\in\Theta\\}$.
Consider any global maximizer $\hat{\theta}(x^{n})$ of the likelihood over
$\theta$ in $\Theta$. When $\Theta$ is compact, suppose Assumptions D, F and
F. Then for each $\xi>0$

$\sup_{\theta\in\Theta}P_{\theta}(D(\theta||\hat{\theta})>\xi)=O(1/n).$

and likewise, for each $\epsilon>0$,

$\sup_{\theta\in\Theta}P_{\theta}(|\hat{\theta}(x^{n})-\theta|>\epsilon)=O(1/n).$

If $\Theta$ is not compact, suppose Assumptions D, F, F and F. Then, for any
compact subset $K$, we have

$\sup_{\theta\in K}P_{\theta}(D(\theta||\hat{\theta})>\xi)=O(1/n)$

and

$\sup_{\theta\in K}P_{\theta}(|\hat{\theta}(x^{n})-\theta|>\epsilon)=O(1/n).$

Proof: In the compact $\Theta$ case, let $\bar{\delta}>0$ be a choice such
that the square of the expected supremum in Assumption F is finite and and
continuous in $\theta^{\prime}$ and $\theta$. We could proceed as in the proof
of the previous lemma, arranging, for each $\xi>0$, positive
$\delta(\theta,\theta^{\prime})\leq\bar{\delta}$ sufficiently small to achieve
the negative expected supremum as explained there. But we can arrange matters
a little better, because we have convergence as $\delta$ goes to $0$ of
functions, here assumed to be continuous on the compact set, which are
converging to the continuous function $-D(\theta||\theta^{\prime})$. So by
Dini’s theorem it is a uniform convergence. Consequently, we can deduce that
for each $\xi>0$, there is a common choice of positive $\delta<\bar{\delta}$
with which the expected supremum is less than
$-D(\theta||\theta^{\prime})+\xi/2$ (and moreover, the variance of the
expected supremum is arbitrarily close to its continuous limit
$V(\theta||\theta^{\prime})$). From the common choice $\delta$ of the radii of
the balls, when we arrange the finite cover $U_{1},\ldots,U_{N}$, if desired,
we have control on the number of them. Then, as in the proof of the previous
lemma,

$\displaystyle\sup_{\theta^{\prime}:D(\theta||\theta)>\xi}\left(\frac{1}{n}\log\frac{p(x^{n}|\theta^{\prime})}{p(x^{n}|\theta)}\right)$
$\displaystyle\leq$ $\displaystyle\max_{1\leq k\leq
N}\left(\frac{1}{n}\sum_{i=1}^{n}\sup_{\theta^{\prime}\in
U_{k}}\log\frac{p(x_{j}|\theta^{\prime})}{p(x_{j}|\theta)}\right),$

where each of these suprema have expectation less than $-\xi/2$. Then by
Chebyshev’s inequality each of these averages is less than $0$ except in an
event of probability not more than $4v_{\delta}/(n\xi^{2})$, where
$v_{\delta}$ is the maximum over $\theta^{\prime}$ and $\theta$ of the
variance of the expected suprema (this maximum being finite since it is a
maximum over a compact set of a function assumed continuous). So we have,
crudely, the union bound on the exception event $4Nv_{\delta}/(n\xi^{2})$ of
order $1/n$. This proves the conclusion in the compact $\Theta$ case.

Maximization of the likelihood over non-compact $\Theta$ is handled with an
analogous incorporation of the Assumption F. This completes the proof.

_Remarks_ : Note that in the non-compact $\Theta$ setting, with Assumption F,
the domain for maximization of the likelihood is allowed to be larger than the
set $K$ of $\theta$ values for which we bound
$P_{\theta}\\{|\hat{\theta}(x^{n})-\theta||\geq\epsilon\\}$. That Assumption
may be dropped if the likelihood is maximized only within the compact $K$.

##  Appendix G On Assumptions in the Non-i.i.d. Setting

Stochastic processes for the joint densities $p(x^{n}|\theta)$, $n\geq 1$,
provide considerable generality, beyond the i.i.d. model setting, in which the
regret could potentially be analyzed. Two natural settings include Markov
models with time homogeneous transitions and stationary ergodic processes. The
core ingredients are the conditional densities $p(x_{t+1}|x_{t},\ldots
x_{1},\theta)$.

Such conditional densities provide the heart of what is needed for arithmetic
coding and predictive gambling procedures. Indeed, to facilitate
implementation, the rational for Bayes procedures that approximate the mimimax
regret is that these yield predictive densities
$q(x_{t+1}|x_{t},\ldots,x_{1})$ which can be computed (e.g. via posterior
Monte Carlo) as the posterior means of the $p(x_{t+1}|x_{t},\ldots
x_{1},\theta)$ using the posterior $w(\theta|x_{t},\ldots,x_{1})$ built from
the (suitably modified) Jeffreys prior.

For stationary processes, there is, for each $k\geq 1$, a function
$p(s_{k+1}|s_{k},\ldots,s_{1},\theta)$ on ${\cal{X}}^{k+1}$ such that the
conditional probability density for $X_{t+1}$, evaluated at $X_{t+1}=s_{k}$,
given $X_{t}=s_{k},\ldots,X_{t+1-k}=s_{1}$ and given $\theta$ is the same for
all $t\geq k$, equal to this $p(s_{k+1}|s_{k},\ldots,s_{1},\theta)$.

These stationary conditionals exist also for Markov processes that do not
necessarily start in the invariant distribution. More generally, for
asymptotically mean stationary processes (in the sense of Gray and Kieffer
[22]), associated to the process with densities $p(x^{n}|\theta)$ there is a
stationary process with densities ${\bar{p}}(x^{n}|\theta)$ with corresponding
stationary conditionals.

For simplicity, here we present results for irreducible Markov processes (of
arbitrary order $k$). And leave to briefer mention settings in which for large
$k$ these approximate more general asymptotically mean stationary processes
which have a stationary ergodic ${\bar{p}}(x^{n}|\theta),n\geq 1$.

We consider the following setting for the Markov model of order $k$. The model
of joint densities takes the form

$p(x^{n}|\theta)=p_{init}(x^{k})\prod_{t=k+1}^{n}p(x_{t}|x_{t-1},\ldots
x_{t-k},\theta),$

where the conditional (transition) density function is time-homogeneous as
mentioned above. It depends on the parameter $\theta$. It is assumed that
there is an invariant probability distribution $P^{*}_{X^{k}|\theta}$, which,
in general, would depend on the parameter. It may have a density
$p^{*}(x^{k}|\theta)$. It will assumed that the Markov model is irreducible,
so the invariant distribution is unique.

As for the initial density $p_{init}(x^{k})$, with additional complication, we
could consider the case that the initial is the invariant density
$p^{*}(x^{k}|\theta)$. But for simplicity here, let’s simply take the case
that $p_{init}(x^{k})$ is fixed (not depending on the parameter) and known.

Now the empirical Fisher information matrix takes the form

$\hat{J}_{ij}(\theta,x^{n})=-\frac{1}{n}\sum_{t=k+1}^{n}\frac{\partial^{2}}{\partial\theta^{i}\partial\theta^{j}}\log
p(x_{t}|x_{t-1},\ldots x_{t-k},\theta),$

where it will be assumed that $\log p(s_{k+1}|s^{k},\theta)$ is twice
continuously differentiable for every $s^{k+1}$ in ${\cal{X}}^{k+1}$. The
second derivatives in the expression above will also be denoted
$\partial_{i}\partial_{j}\log p(x_{t}|x_{t-1},\ldots x_{t-k},\theta)$.

In investigating the expectation of the empirical Fisher information, let
$J_{ij}(\theta|s^{k})$ denote the conditional expectation of minus the second
derivatives of the log of transition density, given an arbitrarily specified
vector of previous values $s^{k}$. Then the Fisher information matrix
$J_{ij,n}(\theta)=E_{\theta}[\hat{J}_{ij}(\theta,x^{n})]$ takes the form

$J_{ij,n}(\theta)=E_{{\bar{P}}_{n,\theta}}[J_{ij}(\theta|\cdot)]=\int
J_{ij}(\theta|s^{k}){\bar{p}}_{n}(s^{k}|\theta)\nu(s^{k})$

where ${\bar{P}}_{n,\theta}=(1/n)\sum_{t=k+1}^{n}P_{X_{t-k}^{t-1}|\theta}$ is
the average across $t$ of the distributions for
$X_{t-k}^{t-1}=(x_{t-k},\ldots,x_{t-1})$ for $t\geq k+1$ having joint density

${\bar{p}}_{n}(s^{k}|\theta)=\frac{1}{n}\sum_{t=k+1}^{n}p_{X_{t-k}^{t-1}}(s^{k}|\theta).$

Continuity of $J_{ij,n}(\theta)$ as a function of $\theta$ is inherited from
the continuity of $J_{ij}(\theta|s^{k})$, and of the distributions
$P_{X_{t-k}^{t-1}|\theta}$. These distributions $P_{X_{t-k}^{t-1}|\theta}$
with density functions $p_{X_{t-k}^{t-1}}(s^{k}|\theta)$ are induced by the
transitions starting from the specified initial distribution $P_{init}$ for
the first $k$.

In general the distribution ${\bar{P}}_{n,\theta}$ converges (weakly) to the
invariant $P^{*}_{\theta}$ distribution on ${\cal{X}}^{k}$.

Let’s assume that $J_{ij}(\theta|s^{k})$ is a bounded function of $s^{k}$ in
${\cal{X}}^{k}$ for each $\theta$ (which allows that the expectation with
respect to the any initial distribution is finite). With
$J_{ij}(\theta|s^{k})$ is bounded and continuous for $s^{k}$ in
${\cal{X}}^{k}$ for each $\theta$, from the convergence of
${\bar{P}}_{n,\theta}$ to the invariant $P^{*}_{\theta}$, it follows that the
Fisher information $J_{ij,n}(\theta)$ converges to the limit $J_{ij}(\theta)$
as $n\rightarrow\infty$, where the limiting Fisher information matrix

$J_{ij}(\theta)=E_{P^{*}_{\theta}}[J_{ij}(\theta|\cdot)]$

is the expectation using the invariant distribution.

Moreover, by the ergodic theorem (for asymptotically mean stationary processes
[22]), if $\partial_{i}\partial_{j}\log p(x_{t}|x_{t-1},\ldots
x_{t-k},\theta)$ has finite expected absolute value, with respect to the
stationary $P_{\theta}^{*}$, it follows that the empirical Fisher information
$\hat{J}_{ij}(\theta,x^{n})$ converges to $J_{ij}(\theta)$ in $P_{\theta}$
probability. The following assumption allows the extension of that conclusion
via local domination.

The stochastic process is $k$th order Markov with a time homogeneous one-step-
ahead transition density that is twice continuously differentiable for
$\theta$ in $\Theta^{\circ}$ and has a unique invariant distribution. The
conditional Fisher information $J_{ij}(\theta|\cdot)$ is assumed bounded as a
function ${\cal{X}}^{k}$ for each $\theta$ in $\Theta$, and continuous as a
function of $\theta$ for each $s^{k}$. Moreover, for every
$\theta\in\Theta^{\circ}$ there is an $r=r(\theta)$ such that, for every $i$,
$j$,

$\displaystyle E^{*}_{\theta}\Biggl{[}\sup_{\theta^{\prime}\in
B_{r}(\theta)}|\partial_{i}\partial_{j}\log p(x_{k+1}|x_{k},\ldots
x_{1},\theta^{\prime})|\Biggr{]}$ (92)

is finite, where the expectation is taken with respect to the stationary
distribution. The Fisher information $J_{n}(\theta)$ and its limit $J(\theta)$
are assumed to be continuous as a function of $\theta$ in $\Theta$. Moreover,
$J(\theta)$ is strictly positive definite.

Accordingly, as in Appendix A, given any $\epsilon$, there exists
$\delta(\theta)$ sufficiently small that the expected supremum in Assumption G
is less than any prescribed positive value, and likewise for the expected
supremum when the matrix of second derivatives of $\log p(x_{k+1}|x_{k},\ldots
x_{1},\theta^{\prime})$ is hit on the left and right by $J(\theta)^{-1/2}$.
Moreover, using that a supremum of averages is less than the average of
suprema, and appealing to the ergodic Theorem, we find again that, for each
$i,j$, and for each sign choice,

$\sup_{\theta^{\prime}\in
B_{\delta}(\theta)}\pm(I_{ij}-(J(\theta)^{-1/2}\hat{J}(\theta^{\prime},x^{n})J(\theta)^{-1/2})_{ij})$

is within $\epsilon/d$ of $0$ except in an event of ($P_{\theta}$) probability
tending to $0$ as $n\rightarrow\infty$.

In compact sets, as we have previously indicated (via Dini’s Theorem),
convergence of continuous functions to a continuous limit is uniformly
convergent. Accordingly, the convergence of $J_{n}(\theta)$ to $J(\theta)$ is
a uniform convergence in $K$. Accordingly, the collection of $J_{n}(\theta)$
for large $n$ is equicontinuous, uniformly in $K$, and they share a positive
lower bound on their minimum eigenvalue. Moreover
$\int_{K}|J_{n}(\theta)|^{1/2}d\theta$ converges to
$\int_{K}|J(\theta)|^{1/2}$.

For consistency, one proceeds similarly, using the relative entropy rate. The
relative entropy rate $D(\theta||\theta^{\prime})$ defined by
$\lim_{n}(1/n)D(P_{X^{n}|\theta}||P_{X^{n}|\theta^{\prime}}$, in the Markov
case, is equal to

$D(\theta||\theta^{\prime})=E_{P^{*}_{X^{k}|\theta}}E_{X_{k+1}|X^{k},\theta}\Bigl{[}\log\frac{p(X_{k+1}|X^{k},\theta)}{p(X_{k+1}|X^{k},\theta^{\prime})}\Bigr{]}.$

For the Markov model, the relative entropy rate $D(\theta||\theta^{\prime})$
is assumed to be continuous as a function of $\theta^{\prime}$ and $\theta$,
and to satisfy the identifiability property that it is zero only at
$\theta^{\prime}=\theta$. Moreover, local domination of log-likelihood ratios
is assumed for each $\theta$ and $\theta^{\prime}$ in a compact $K$. Namely
for each $\theta$ and $\theta^{\prime}$ there is an
$r=r(\theta,\theta^{\prime})$ such that

$E^{*}_{\theta}\left[\sup_{\theta^{\prime\prime}\in K\cap
B_{r}(\theta^{\prime})}\log\frac{p(X_{k+1}|X^{k},\theta^{\prime\prime})}{p(X_{k+1}|X^{k},\theta)}\right]$

is finite and continuous as a function of $\theta$ and $\theta^{\prime}$ in
$K$.

These Assumptions G and G for Markov models are sufficient for the conditions
of Theorem IV-B for the lower bound conclusion for the regret for stochastic
processes, for compact parameter sets.

Further details are omitted since they closely parallel the previous analysis
from the i.i.d. setting.

One may wonder about further generalization beyond the Markov model setting.
For consistency, the core matter is the convergence of (1/n) log density
ratios to a relative entropy (an asymptotic equipartion property (AEP)). One
setting beyond Markov, is when target stationary ergodic processes $P^{*}$ are
approximated by possibly variable order Markov models $P_{\theta}$. For this
setting one can appeal to the moderately general AEP of [11], [21], and [1].
Presummably, shifting back to a time $0$ reference, the domination condition
would be of the form of an assumption of finiteness of

$E^{*}_{\theta}\Bigl{[}\sup_{\theta^{\prime\prime}\in K\cap
B_{r}(\theta^{\prime})}\log\frac{p(X_{0}|\theta^{\prime\prime},X_{-1},X_{-2},\ldots,X_{-k})}{p^{*}(X_{0}|X_{-1},X_{-2},\ldots)}\Bigr{]}.$

where perhaps the Markov order $k=k(\theta^{\prime})$ would depend on
$\theta$. To deal more generally for families of non-Markov stationary ergodic
processes, there were early attempts in [35], and counterexamples for pairs of
stationary (but not ergodic) processes in [32]. Nevertheless the question of
formulation of suitably general conditions for an AEP for pairs of stationary
ergodic processes $P_{\theta}$ and $P_{\theta}^{\prime}$ is largely open.
Until such is obtained, the matter of consistency of maximum likelihood in
non-Markov models requires that it be addressed on a case-by-case basis.

##  Appendix H Lower Bound on Gaussian Measure (Proposition V)

Recall that $\Phi$ denotes the measure of the $d$-dimensional standard normal
distribution and $N_{r}(0)=\\{z:|z|\leq r\\}$. The following holds. For all
$n>0$ and $\epsilon>0$,

$\Phi(N_{\sqrt{n}\epsilon}(0))\geq
1-\exp\Bigl{(}-\frac{n\epsilon^{2}}{2}\bigl{(}1-\frac{d}{n\epsilon^{2}}\log\frac{n\epsilon^{2}}{d}\bigr{)}+\frac{d}{2}\Bigr{)},$

which is larger than

$1-\exp\Bigl{(}-\frac{n\epsilon^{2}}{4}+\frac{d}{2}\Bigr{)},$

when $n\epsilon^{2}/d\geq 2$.

Proof: Note that

$\Phi(N_{\sqrt{n}\epsilon}(0))=\Pr\Bigl{\\{}\sum_{i=1}^{d}X_{i}^{2}\leq
n\epsilon^{2}\Bigr{\\}},$

where each $X_{i}$ is an independent standard normal random variable. The
density function of normal distribution with mean $0$ and variance
$\sigma^{2}$ is

$\displaystyle\frac{1}{(2\pi\sigma^{2})^{1/2}}\exp\Bigl{(}\frac{-x^{2}}{2\sigma^{2}}\Bigr{)}$
$\displaystyle=\exp\Bigl{(}\frac{-x^{2}}{2\sigma^{2}}-\frac{1}{2}\log(2\pi\sigma^{2})\Bigr{)}$
$\displaystyle=\exp(ux^{2}-\psi(u)),$

where $u=-1/(2\sigma^{2})$ and
$\psi(u)=(1/2)\log(2\pi\sigma^{2})=(1/2)\log(-\pi/u)$. Let
$q(x|u)=\exp(ux^{2}-\psi(u))$, which forms an exponential family, for which
the natural parameter is $u=-1/(2\sigma^{2})$. Let
$v=E_{u}(x^{2})=\sigma^{2}$. Then $v$ is the expectation parameter
coresponding to $u$. We have

$q(x^{d}|u)=\exp(d(u||x||^{2}/d-\psi(u))),$

where $x^{d}=(x_{1},\dots,x_{d})$ and $||x||^{2}$ denotes the square of
$x^{d}$’s Euclidian norm. Note that the maximum likelihood estimate of
$v=\sigma^{2}$ given $x^{d}$ is $\hat{\sigma^{2}}=||x||^{2}/d$. Then by the
large deviation inequality (Lemma VI-A), we have

$\Pr\Bigl{\\{}\sum_{i=1}^{d}X_{i}^{2}\geq
n\epsilon^{2}\Bigr{\\}}\leq\exp(-dD(n\epsilon^{2}/d||1)),$

where $D(v||v^{\prime})$ denotes the Kullback-Leibler divergence from $q(x|u)$
to $q(x|u^{\prime})$ ($v^{\prime}$ is the expectation parameter corresponding
to $u^{\prime}$). Here, we have

$\displaystyle D(v||v^{\prime})$
$\displaystyle=(u-u^{\prime})v-\psi(u)+\psi(u^{\prime})$
$\displaystyle=-\frac{1}{2}+\frac{1}{2}\frac{v}{v^{\prime}}+\frac{1}{2}\log\frac{v^{\prime}}{v}$
$\displaystyle=\frac{1}{2}\Bigl{(}-1+\frac{v}{v^{\prime}}-\log\frac{v}{v^{\prime}}\Bigr{)}.$

Hence we have

$\displaystyle dD(n\epsilon^{2}/d||1)$
$\displaystyle=\frac{d}{2}\Bigl{(}-1+\frac{n\epsilon^{2}}{d}-\log\frac{n\epsilon^{2}}{d}\Bigr{)}$
$\displaystyle=-\frac{d}{2}+\frac{n\epsilon^{2}}{2}\bigl{(}1-\frac{d}{n\epsilon^{2}}\log\frac{n\epsilon^{2}}{d}\bigr{)},$

which is not less than

$-\frac{d}{2}+\frac{n\epsilon^{2}}{2}\bigl{(}1-\frac{\log
2}{2}\bigr{)}\geq-\frac{d}{2}+\frac{n\epsilon^{2}}{4},$

when $n\epsilon^{2}/d\geq 2$. This completes the proof.

##  Appendix I Normalization Constant of The Ideal Priors

Let $K$ be an arbitrary compact set in $\Theta^{\circ}$. Suppose Assumption V
holds and let $̱\lambda$ denote a lower bound on the smallest eigenvalue of
$J_{n,\theta}$ among $n\in\mathbb{N}$ and $\theta\in K$. Let

$K_{\epsilon}=\\{\theta:B_{\epsilon}(\theta)\subset K\\},$

Then for $\epsilon$ such that $n\epsilon^{2}/d\geq 2$ and
$\epsilon^{2}\alpha^{2}\leq\mbox{\@text@baccent{$\lambda$}}$, we have

$C_{J,n}(K)\leq
C_{K,\epsilon,n}^{(\alpha)}\leq\frac{C_{J,n}(K)}{1-e^{-n\epsilon^{2}/4+d/2}}+\frac{C_{J,n}(K\setminus
K_{\epsilon\alpha})}{\rho_{n}^{(\alpha)}(\epsilon)},$

where

$C_{J,n}(A)=\int_{A}|J_{n,\theta}|^{1/2}d\theta.$

Proof: Assume $\theta\in K_{\epsilon\alpha}$. Then, by
$\epsilon^{2}\alpha^{2}\leq\mbox{\@text@baccent{$\lambda$}}$,
$N_{\sqrt{n}\epsilon}(0)\subset(\sqrt{n}/\alpha)(J_{n,\theta})^{1/2}(K-\theta)$
is satisfied, which means

$\displaystyle\Phi(U_{K,\epsilon,n}^{(\alpha)}(\theta))$
$\displaystyle=\Phi(N_{\sqrt{n}\epsilon}(0))$

holds for $\theta\in K_{\epsilon\alpha}$. Hence by Proposition V and the
assumption $n\epsilon^{2}/d\geq 2$, the following holds.

$\displaystyle\inf_{\theta\in
K_{\epsilon\alpha}}\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))\geq
1-e^{-n\epsilon^{2}/4+d/2}.$

Using this inequality, we have

$\displaystyle\int_{K}\frac{|J_{n,\theta}|^{1/2}}{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))}d\theta$
$\displaystyle\leq\int_{K_{\epsilon/\alpha}}\frac{|J_{n,\theta}|^{1/2}}{1-e^{-n\epsilon^{2}/4+d/2}}d\theta+\int_{K\setminus
K_{\epsilon\alpha}}\frac{|J_{n,\theta}|^{1/2}}{\rho_{n}^{(\alpha)}(\epsilon)}d\theta$
$\displaystyle\leq\frac{C_{J,n}(K)}{1-e^{-n\epsilon^{2}/4+d/2}}+\frac{C_{J,n}(K\setminus
K_{\epsilon\alpha})}{\rho_{n}^{(\alpha)}(\epsilon)}.$

This completes the proof of the Lemma.

##  Appendix J Lower Bounds on $\rho^{(\alpha)}_{n}(\epsilon)$

For a subset $A$ of $\mathbb{R}^{d}$, let ${\rm diam}(A)$ and ${\rm vol}(A)$
denote the diameter of $A$ and the volume of $A$, respectively.

Assume that $K$ is compact, convex, and the closure of an open set in
$\Re^{d}$. Then, for all $\epsilon$ such that ${\rm
vol}(N_{\epsilon}(0))\leq{\rm vol}(J^{1/2}_{n,\theta}K)/2$, the following
holds.

$\rho^{(\alpha)}_{n}(\epsilon,\theta)\geq\frac{{\rm
vol}(J^{1/2}_{n,\theta}K)}{2({\rm
diam}(J^{1/2}_{n,\theta}K))^{d}V_{d}}\Phi(N_{\sqrt{n}\epsilon}(0)).$

Proof: Let $L=J_{n,\theta}^{1/2}K$. Then, we have

$\displaystyle\rho_{n}^{(\alpha)}(\epsilon,\theta)$
$\displaystyle=\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))$
$\displaystyle=\Phi(N_{\sqrt{n}\epsilon}(0)\cap(\sqrt{n}/\alpha)(L-J_{n,\theta}^{1/2}\theta))$
$\displaystyle=\Phi\Bigl{(}(\sqrt{n}/\alpha)\bigl{(}N_{\epsilon\alpha}(0)\cap(L-J_{n,\theta}^{1/2}\theta)\bigr{)}\Bigr{)}.$

Define for $\eta\in L$ and for $\epsilon>0$,

$\displaystyle A(\eta)$
$\displaystyle=\\{u\in\Re^{d}:|u|=1,\exists\kappa>0,\;\eta+\kappa u\in
L^{\circ}\\},$ $\displaystyle C(\eta,\epsilon)$
$\displaystyle=\\{u\in\Re^{d}:|u|=1,\;\eta+\epsilon u\in L^{\circ}\\},$

and

$\tilde{C}(\eta,\epsilon)=\\{v\in\Re^{d}:|v|=\epsilon,\;\eta+v\in
L^{\circ}\\}.$

By definition, we have

$A(\eta)\subset\bigcup_{\epsilon>0}C(\eta,\epsilon).$

By the convexity of $L$,

$A(\eta)\supset C(\eta,\epsilon_{1})\supset C(\eta,\epsilon_{2})$

holds for $0<\epsilon_{1}\leq\epsilon_{2}$. Hence,
$A(\eta)=\bigcup_{\epsilon>0}C(\eta,\epsilon)$ holds.

Note that $\tilde{C}(\eta,\epsilon)$ is an open subset of the surface of
$N_{\epsilon}(0)$, since it is the intersection of $L^{\circ}-\eta$ (an open
set) and the surface of $N_{\epsilon}(0)$. Hence it is measurable in the
surface of $N_{\epsilon}(0)$, which means $C(\eta,\epsilon)$ is also
measurable.

Let $r(\eta,\epsilon)$ denote the ratio of the $d-1$ dimensional volume of
$C(\eta,\epsilon)$ to that of the surface of $N_{1}(0)$
($d\pi^{d/2}/\Gamma(d/2+1)$). Since $C(\eta,\epsilon)$ does not decrease as
$\epsilon$ decreases, $r(\eta,\epsilon)$ does not decrease as $\epsilon$
decreases.

For $\eta\in L$, define

${\rm cone}(\eta,\kappa)=\\{\eta+\xi u:u\in C(\eta,\kappa),\xi\geq 0\\}.$

If $C(\eta,\kappa)$ is connected, this is an unbounded cone with the vertex
$\eta$. If not, it is a union of unbounded cones. Note that

$\displaystyle N_{\epsilon}(\eta)\cap L\supset N_{\kappa}(\eta)\cap{\rm
cone}(\eta,\kappa)$ (93)

holds for all $\kappa\in(0,\epsilon]$. This is shown as follows. Let $\eta+v$
be an element of ${\rm cone}(\eta,\kappa)$ with $|v|\leq\kappa$. Then,
$v/|v|\in C(\eta,\kappa)$ holds by the definition of $C(\eta,\kappa)$. This
means that $\eta+\kappa v/|v|\in L^{\circ}$. Since $\kappa/|v|\geq 1$,
$\eta+v$ is on the line segment between $\eta\in L$ and $\eta+\kappa v/|v|\in
L^{\circ}$. Hence $\eta+v\in L^{\circ}$ holds. Since
$|v|\leq\kappa\leq\epsilon$, (93) holds.

Because of (93), for any nonnegative integrand, the integral over
$(\sqrt{n}/\alpha)(N_{\epsilon\alpha}(0)\cap(L-\eta))$ is lower bounded by
that over $(\sqrt{n}/\alpha)(N_{\epsilon\alpha}(0)\cap({\rm
cone}(\eta,\epsilon\alpha)-\eta))$. Then due to the symmetry of $\Phi$, we
have for each $\theta\in K$,

$\rho^{(\alpha)}_{n}(\epsilon,\theta)\geq
r(\eta,\epsilon\alpha)\Phi(N_{\sqrt{n}\epsilon}(0)),$

where $\eta=J_{n,\theta}^{1/2}\theta$.

Finally, we will show that $\inf_{\eta\in L}r(\eta,\epsilon\alpha)$ is lower
bounded by the positive constant determined by ${\rm vol}(L)$ and ${\rm
diam}(L)$. Let $\epsilon_{0}$ so small that ${\rm
vol}(N_{\epsilon_{0}}(0))\leq{\rm vol}(L)/2$ and assume that
$\epsilon\alpha\leq\epsilon_{0}$. Let $\Delta$ denote ${\rm diam}(L)$. Recall
that $C(\eta,\epsilon\alpha)\supset C(\eta,\epsilon_{0})\supset
C(\eta,\kappa)$ holds for all $\kappa\geq\epsilon_{0}$ and for all $\epsilon$
such that $\epsilon\alpha\leq\epsilon_{0}$. Since

$\frac{\eta^{\prime}-\eta}{|\eta^{\prime}-\eta|}\in C(\eta,\kappa)$

holds for all $\eta^{\prime}\in L^{\circ}$ with $|\eta^{\prime}-\eta|=\kappa$,
the set $L^{\circ}\setminus N_{\epsilon_{0}}(\eta)$ is included in ${\rm
cone}(\eta,\epsilon_{0})$. Note that $L$ is included in $N_{\Delta}(\eta)$.
Then, we see that $L^{\circ}\setminus N_{\epsilon_{0}}(\eta)$ is included in
${\rm cone}(\eta,\epsilon_{0})\cap N_{\Delta}(\eta)$. Comparing the volumes of
both sets, we have

${\rm vol}(L)-{\rm vol}(N_{\epsilon_{0}}(\eta))\leq
V_{d}\Delta^{d}r(\eta,\epsilon_{0}).$

Since the left side is not less than ${\rm vol}(L)-{\rm vol}(L)/2={\rm
vol}(L)/2$, we have

$r(\eta,\epsilon\alpha)\geq\frac{{\rm vol}(L)}{2({\rm diam}(L))^{d}V_{d}}$

holds for all $\epsilon$ such that $\epsilon\alpha\in(0,\epsilon_{0})$. The
proof is completed.

##  Appendix K Continuity of $\Phi(U_{K,\epsilon,n}^{(\alpha)})$

Let $\lambda_{n}$ denote the maximum of the largest eigenvalue of
$J_{n}(\theta)$ among $\theta\in K$. For a certain $\epsilon>0$, for all
$r\leq\epsilon$, for all $\theta^{\prime}\in B_{r}(\theta)\cap K$, and for all
$\theta\in K$,

$\displaystyle\frac{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta^{\prime}))}{\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))}$
$\displaystyle\leq$ $\displaystyle
1+\frac{\sqrt{n\lambda_{n}}r}{\rho_{n}(\epsilon,\theta)\alpha}+\frac{C_{d}\,{\rm
diam}(K)\sqrt{n\lambda_{n}}\max\\{g_{\theta,r},0\\}}{\rho_{n}(\epsilon,\theta)\alpha}$

holds, where $C_{d}=2^{1-d/2}\Gamma(d/2)$ and

$g_{\theta,r}=\max_{\theta^{\prime}\in B_{r}(\theta)\cap
K}||J_{n}(\theta)^{-1/2}J_{n}(\theta^{\prime})^{1/2}||_{s}-1.$

Proof: First assume that $J_{n}(\theta)$ does not depend on $\theta$. Let
$J_{n}$ denote the value. Note that

$\displaystyle U^{(\alpha)}_{K,\epsilon,n}(\theta^{\prime})\setminus
U^{(\alpha)}_{K,\epsilon,n}(\theta)$
$\displaystyle=N_{\sqrt{n}\epsilon}(0)\cap(\sqrt{n}/\alpha)J_{n}^{1/2}((K-\theta^{\prime})\setminus(K-\theta))$
$\displaystyle=N_{\sqrt{n}\epsilon}(0)\cap(\sqrt{n}/\alpha)((L-\eta^{\prime})\setminus(L-\eta)),$

holds, where $L=J_{n}^{1/2}K$, $\eta=J_{n}^{1/2}\theta$, and
$\eta^{\prime}=J_{n}^{1/2}\theta^{\prime}$. Then, we have

$\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta^{\prime})\setminus
U^{(\alpha)}_{K,\epsilon,n}(\theta))\leq\Phi((\sqrt{n}/\alpha)((L-\eta^{\prime})\setminus(L-\eta))).$

Recall that $\Phi$ is the $d$ variate standard Gaussian measure. Note that
$L-\eta^{\prime}$ is given by displacing $L-\eta$ by $\eta-\eta^{\prime}$.
Hence, a point $\tilde{\eta}$ in $L-\eta$ has a representation as a scalar
amount in the direction $\eta^{\prime}-\eta$ together with $d-1$ amounts in
directions orthogonal to $\eta^{\prime}-\eta$. The displacement from $L-\eta$
to $L-\eta^{\prime}$ only affects that scalar translation by the amount
$|\eta^{\prime}-\eta|$. Hence, we have

$\displaystyle\Phi$
$\displaystyle\Bigl{(}(\sqrt{n}/\alpha)\bigl{(}(L-\eta^{\prime})\setminus(L-\eta)\bigr{)}\Bigr{)}$
$\displaystyle\leq\Pr\\{|y|\leq(\sqrt{n}/\alpha)|\eta^{\prime}-\eta|/2\\}$
$\displaystyle\leq(\sqrt{n}/\alpha)|\eta^{\prime}-\eta|,$

where $y$ denotes the (univariate) standard Gaussian variable. Since
$|\theta^{\prime}-\theta|\leq r\leq\epsilon$ and since the eigenvalues of
$J_{n}(\theta)$ are bounded by $\lambda_{n}$,

$\Phi\Bigl{(}(\sqrt{n}/\alpha)\bigl{(}(L-\eta^{\prime})\setminus(L-\eta)\bigr{)}\Bigr{)}\leq\frac{\sqrt{n\lambda_{n}}r}{\alpha}.$

Recalling that
$\Phi(U^{(\alpha)}_{K,\epsilon,n}(\theta))\geq\rho_{n}(\epsilon,\theta)$, we
have the claim of Lemma.

Next, consider the general $J_{n}(\theta)$ case. We have

$\displaystyle J_{n}(\theta^{\prime})^{1/2}$
$\displaystyle(K-\theta^{\prime})\setminus J_{n}(\theta)^{1/2}(K-\theta)$
$\displaystyle\subset$ $\displaystyle
J_{n}(\theta)^{1/2}(K-\theta^{\prime})\setminus J_{n}(\theta)^{1/2}(K-\theta)$
$\displaystyle\cup J_{n}(\theta^{\prime})^{1/2}(K-\theta^{\prime})\setminus
J_{n}(\theta)^{1/2}(K-\theta^{\prime}).$

The quantity produced by the first component of the union in the last
expression is bounded as in the same way as the constant $J_{n}$ case. As for
the second component, we have

$\displaystyle J_{n}(\theta^{\prime})^{1/2}(K-\theta^{\prime})\setminus
J_{n}(\theta)^{1/2}(K-\theta^{\prime})$
$\displaystyle=J_{n}(\theta)^{1/2}\Bigl{(}\bigl{(}J_{n}(\theta)^{-1/2}J_{n}(\theta^{\prime})^{1/2}(K-\theta^{\prime})\bigr{)}\setminus(K-\theta^{\prime})\Bigr{)}$
$\displaystyle\subset
J_{n}(\theta)^{1/2}\Bigr{(}\bigl{(}(1+g_{\theta,r})(K-\theta^{\prime})\bigr{)}\setminus(K-\theta^{\prime})\Bigr{)}$
$\displaystyle=(1+g_{\theta,r})J_{n}(\theta)^{1/2}(K-\theta^{\prime})\setminus
J_{n}(\theta)^{1/2}(K-\theta^{\prime}).$

Let $L^{\prime}=J_{n}(\theta)(K-\theta^{\prime})$, then we have

$\displaystyle J_{n}(\theta^{\prime})^{1/2}(K-\theta^{\prime})\setminus
J_{n}(\theta)^{1/2}(K-\theta^{\prime})$
$\displaystyle\subset(1+g_{\theta,r})L^{\prime}\setminus L^{\prime}.$

Hereafter, assume $g_{\theta,r}>1$. Otherwise, the analysis below is not
necessary, because $(1+g_{\theta,r})L^{\prime}\setminus L^{\prime}$ is the
empty set in that case.

Note that $L^{\prime}$, which is compact, includes the origin. Assume now that
the origin is included in ${L^{\prime}}^{\circ}$, that is, $\theta^{\prime}\in
K^{\circ}$. Since $L^{\prime}$ is convex, the set
$(1+g_{\theta,r})L^{\prime}\setminus L^{\prime}$ is a shell outside
$L^{\prime}$ as follows.

$\displaystyle(1+g_{\theta,r})L^{\prime}\setminus L^{\prime}$ $\displaystyle=$
$\displaystyle\\{yu:u\in\partial L^{\prime},1<y\leq 1+g_{\theta,r}\\}$ (94)
$\displaystyle=$ $\displaystyle\\{y_{u}u/|u|:u\in\partial
L^{\prime},|u|<y_{u}\leq|u|(1+g_{\theta,r})\\},$

where $\partial L^{\prime}=L^{\prime}-{L^{\prime}}^{\circ}$. Note that
$\\{u/|u|:u\in\partial L^{\prime}\\}$ is the unit sphere, when the origin is
in the interior of $L^{\prime}$. The equality (94) itself holds even if the
origin is not included in the interior of $L^{\prime}$. Hence, we do not need
the assumption $\theta^{\prime}\in K^{\circ}$ for the argument below.

Now, we can evaluate

$\displaystyle\Phi\Bigl{(}(\sqrt{n}/\alpha)\bigl{(}J_{n}(\theta^{\prime})^{1/2}(K-\theta^{\prime})\setminus
J_{n}(\theta)^{1/2}(K-\theta^{\prime})\bigr{)}\Bigr{)}$ $\displaystyle\leq$
$\displaystyle\Phi\Bigl{(}(\sqrt{n}/\alpha)\bigl{(}(1+g_{\theta,r})L^{\prime}\setminus
L^{\prime}\bigr{)}\Bigr{)}$

Let $\xi$ be a $d$-variate standard Gaussian variable. Then, we transform it
to $(v,y)=(\xi/|\xi|,|\xi|)$. Here, $v$ and $y$ are independent of each other,
the marginal density of $v$ is uniform on the surface of the unit sphere, and
that of $y$ is

$C_{d}\,y^{d-1}\exp\Bigl{(}-\frac{y^{2}}{2}\Bigr{)}\leq
C_{d}(d-1)^{(d-1)/2}e^{-(d-1)/2},$

where $C_{d}=2^{(1-d)/2}/\Gamma(d/2)$ is the normalization constant and the
equality of the above holds if and only if $y=\sqrt{d-1}$. Since $|u|$
($u\in\partial L^{\prime}$) is upper bounded by ${\rm diam}(L^{\prime})$, we
have the following, where $y_{0}=\sqrt{n}|u|/\alpha$ and
$y_{1}=\sqrt{n}|u|(1+g_{\theta,r})/\alpha$.

$\displaystyle\Phi\Bigl{(}(\sqrt{n}/\alpha)\bigl{(}(1+g_{\theta,r})L^{\prime}\setminus
L^{\prime}\bigr{)}\Bigr{)}$ $\displaystyle\leq\max_{u\in\partial
L^{\prime}}\Pr\\{y_{0}<y\leq y_{1}\\}$ $\displaystyle\leq\max_{u\in\partial
L^{\prime}}C_{d}\int_{y_{0}}^{y_{1}}y^{d-1}\exp\Bigl{(}-\frac{y^{2}}{2}\Bigr{)}dy$
$\displaystyle\leq\max_{u\in\partial
L^{\prime}}C_{d}\int_{y_{0}}^{y_{1}}(d-1)^{(d-1)/2}e^{-(d-1)/2}dy$
$\displaystyle\leq C_{d}\,{\rm diam}(L^{\prime})\sqrt{n}g_{\theta,r}/\alpha$
$\displaystyle=C_{d}{\rm diam}(K)\sqrt{n\lambda_{n}}g_{\theta,r}/\alpha.$

This completes the proof.

##  Appendix L Some Inequality for Models with Hidden Variables (Lemma VI-D3)

Recall that we defined the model with hidden variable in (64) as

$p(x|\theta)=\int\\!\\!\kappa(x|y)q(y|\theta)\nu_{y}(dy),$

where $q(y|\theta)$ is the density of an exponential family. We have the
following, where $G(\theta)$ is the Fisher information of $q(y|\theta)$. Given
a data string $x^{n}$, let $\hat{\theta}$ denote the MLE for a model with
hidden variables $p(x^{n}|\theta)$ defined by (64). Then, the following holds
for all $x^{n}\in\mathcal{X}^{n}$.

$\displaystyle\forall\theta\in\Theta,\>\>\frac{1}{n}\log\frac{p(x^{n}|\hat{\theta})}{p(x^{n}|\theta)}$
$\displaystyle\leq D(q(\cdot|\hat{\theta})||q(\cdot|\theta)),$ (95)
$\displaystyle\forall\theta\in\Theta,\>\>\hat{J}(\theta,x^{n})$
$\displaystyle\leq G(\theta).$ (96)

In particular, when $q(y|\theta)$ is the multinomial model, the following
holds

$\displaystyle\frac{p(x^{n}|\hat{\theta})}{p(x^{n}|\theta)}\leq\exp(nD(q(\cdot|\hat{\theta})||q(\cdot|\theta)))=\prod_{y\in\mathcal{Y}}\frac{\hat{\eta}_{y}^{n\hat{\eta}_{y}}}{\eta_{y}^{n\hat{\eta}_{y}}},$
(97)

where $\eta_{y}=q(y|\theta)$ and $\hat{\eta}_{y}=q(y|\hat{\theta})$.

Proof: Note that

$\displaystyle q(x^{n}|\theta)$
$\displaystyle=\prod_{t=1}^{n}\int\kappa(x_{t}|y_{t})p(y_{t}|\theta)\nu_{y}(dy_{t})$
$\displaystyle=\int\prod_{t}\kappa(x_{t}|y_{t})p(y_{t}|\theta)\nu_{y}(dy^{n})$
$\displaystyle=\int\kappa(x^{n}|y^{n})p(y^{n}|\theta)\nu_{y}(dy^{n}).$

We have

$\displaystyle\frac{q(x^{n}|\theta)}{q(x^{n}|\theta^{\prime})}$
$\displaystyle=\frac{\int\kappa(x^{n}|y^{n})p(y^{n}|\theta)\nu_{y}(dy^{n})}{\int\kappa(x^{n}|y^{n})p(y^{n}|\theta^{\prime})\nu_{y}(dy^{n})}$
$\displaystyle=\int\frac{p(y^{n}|\theta)}{p(y^{n}|\theta^{\prime})}\frac{\kappa(x^{n}|y^{n})p(y^{n}|\theta^{\prime})\nu_{y}(dy^{n})}{\int\kappa(x^{n}|z^{n})p(z^{n}|\theta^{\prime})\nu_{y}(dz^{n})}.$

Define $q(y^{n}|x^{n},\theta^{\prime})$ by

$q(y^{n}|x^{n},\theta^{\prime})=\frac{\kappa(x^{n}|y^{n})p(y^{n}|\theta^{\prime})}{\int\kappa(x^{n}|z^{n})p(z^{n}|\theta^{\prime})\nu_{y}(dz^{n})},$

which is the posterior distribution of $y^{n}$ given $x^{n}$ provided $x^{n}$
is drawn from $q(x^{n}|\theta^{\prime})$.

Using it, we can write

$\frac{q(x^{n}|\theta)}{q(x^{n}|\theta^{\prime})}=\int
q(y^{n}|x^{n},\theta^{\prime})\frac{p(y^{n}|\theta)}{p(y^{n}|\theta^{\prime})}\nu_{y}(dy^{n}).$

Then by Jensen’s inequality, we have

$\displaystyle\frac{1}{n}\log\frac{q(x^{n}|\theta)}{q(x^{n}|\theta^{\prime})}$
(98) $\displaystyle\geq\frac{1}{n}\int
q(y^{n}|x^{n},\theta^{\prime})\log\frac{p(y^{n}|\theta)}{p(y^{n}|\theta^{\prime})}\nu_{y}(dy^{n}).$

Let $f(\theta,\theta^{\prime})$ denote the left side, and
$g(\theta,\theta^{\prime})$ the right side. Then, we have

$\displaystyle\forall\theta,\theta^{\prime}\in\Theta,\>\>f(\theta,\theta^{\prime})-g(\theta,\theta^{\prime})\geq
0,$ (99)

where equality holds when $\theta=\theta^{\prime}$. Hence, Hessian of the left
side is semi positive-definite. That is, the matrix whose $ij$ entry is

$\displaystyle\frac{\partial^{2}\log
f(\theta,\theta^{\prime})}{\partial\theta_{i}\partial\theta_{j}}-\frac{\partial^{2}\log
g(\theta,\theta^{\prime})}{\partial\theta_{i}\partial\theta_{j}}$ (100)

is semi positive definite. Note that

$\displaystyle
g(\theta,\theta^{\prime})=\theta\bar{\eta}^{t}-\psi(\theta)-(\theta^{\prime}\bar{\eta}^{t}-\psi(\theta^{\prime})),$
(101)

where

$\bar{\eta}=\frac{1}{n}\int
q(y^{n}|x^{n},\theta^{\prime})\sum_{t=1}^{n}y_{t}\nu_{y}(dy^{n}).$

From (101), we have

$-\frac{\partial^{2}\log
g(\theta,\theta^{\prime})}{\partial\theta_{i}\partial\theta_{j}}=\frac{\partial^{2}\psi(\theta)}{\partial\theta_{i}\partial\theta_{j}}=G_{ij}(\theta).$

Hence, semi positive-definiteness of (100) implies

$\forall\theta\in\Theta,\>\>\hat{J}(\theta,x^{n})\leq G(\theta),$

Plugging in $\hat{\theta}$ to $\theta^{\prime}$ in (99) and noting
$f(\theta,\hat{\theta})\leq 0$, we have

$\displaystyle\forall\theta\in\Theta,\>\>0\geq f(\theta,\hat{\theta})\geq
g(\theta,\hat{\theta}),$ (102)

where both inequality hold as equality, when $\theta=\hat{\theta}$. That is,

$g(\theta,\hat{\theta})\leq g(\hat{\theta},\hat{\theta})=0.$

Together with (101) the following holds

$\displaystyle
g(\theta,\hat{\theta})=\theta\bar{\eta}^{t}-\psi(\theta)-(\hat{\theta}\bar{\eta}^{t}-\psi(\hat{\theta}))$
(103)
$\displaystyle\leq\hat{\theta}\bar{\eta}^{t}-\psi(\hat{\theta})-(\hat{\theta}\bar{\eta}^{t}-\psi(\hat{\theta}))=0,$
(104)

which implies $\bar{\eta}=\hat{\eta}$. Here $\hat{\eta}$ denotes the coo
responding value of expectation parameter $\eta$ to $\hat{\theta}$.

Note that

$g(\theta,\hat{\theta})=-D(p(\cdot|\hat{\theta})||p(\cdot|\theta)),$

where $D(p(\cdot|\hat{\theta})||p(\cdot|\theta))$ is the Kullback divergence
from $p(y|\hat{\theta})$ to $p(y|\theta)$ defined as

$D(p(\cdot|\hat{\theta})||p(\cdot|\theta))=\int
p(y|\hat{\theta})\log\frac{p(y|\hat{\theta})}{p(y|\theta)}\nu_{y}(dy).$

Hence from (98), we have

$\displaystyle\frac{1}{n}\log\frac{q(x^{n}|\hat{\theta})}{q(x^{n}|\theta)}\leq
D(\hat{\theta}||\theta).$ (105)

This completes the proof.

## Acknowledgement

The authors thank Hiroshi Nagaoka, who gave valuable advises for the part of
the models with hidden variables.

## References

  * [1] P. H. Algoet and T. M. Cover, “Asymptotic Optimality and Asymptotic Equipartition Properties of Log-Optimum Investment,” The Annals of Probability, Vol. 16, No. 2, pp. 876-898, Apr. 1988.
  * [2] S. Amari, Differential-geometrical methods in statistics (2nd pr.), Lecture Notes in Statistics, Vol.28, Springer-Verlag, 1990.
  * [3] S. Amari and H. Nagaoka, Methods of Information Geometry, AMS & Oxford University Press, 2000.
  * [4] A. R. Barron, Logically Smooth Density Estimation, Ph.D. dissertation, Dept. Elec. Eng., Stanford Univ., 1985.
  * [5] A. R. Barron, J. Rissanen and B. Yu, “The minimum description length principle in coding and modeling,” IEEE trans. Inform. Theory, Vol. 44 No. 6, pp. 2743 - 2760, 1998.
  * [6] A. R. Barron, T. Roos, and K. Watanabe. “Bayesian Properties of Normalized Maximum Likelihood and its Fast Computation,” Proc. IEEE International Symposium on Information Theory. Honolulu, HI, June 2014. pp.1667-1671.
  * [7] A. R. Barron and J. Takeuchi, “Mixture models achieving optimal coding regret,” Proc. of 1998 Inform. Theory Workshop, 1998\.
  * [8] R. G. Bartle, Elements of Integration, Publisher: John Wiley & Sons Inc, 1966.
  * [9] R. G. Bartle, “An Extension of Egorov’s Theorem,” The American Mathematical Monthly, 87:8, 628-633, 1980.
  * [10] J. Bernardo, “Reference posterior distributions for Bayesian inference,” J. Roy. Statist. Soc. B. 41\. pp. 113-147, 1979.
  * [11] A. R. Barron, “The strong ergodic theorem for densities: generalized Shannon-McMillan-Breiman theorem,” Annals of Probability, Vol. 13, pp. 1292-1303, 1985.
  * [12] L. Brown, Fundamentals of statistical exponential families, Institute of Mathematical Statistics, 1986.
  * [13] B. Clarke and A. R. Barron, “Information-theoretic asymptotics of Bayes methods,” IEEE trans. on IT, vol. 36. no. 3, pp. 453-471, 1990.
  * [14] B. Clarke and A. R. Barron, “Jeffreys prior is asymptotically least favorable under entropy risk,” J. Statistical Planning and Inference, 41:37-60, 1994.
  * [15] H. Cramèr, Mathematical methods of statistics, Princeton University Press, 1946.
  * [16] I. Csiszàr, “Sanov property, generalized I-projection and a conditional limit theorem,” Ann. of probability, vol. 12, No. 3, pp. 768-793, 1984.
  * [17] L. Davisson and A. Leon-Garcia, “A source matching approach to finding minimax codes,” IEEE Trans. Inform. Theory, vol. 26, pp. 166-174, March 1980.
  * [18] M. Feder, N. Merhav and M. Gutman, “Universal prediction of individual sequences,” IEEE trans. Inform. Theory, vol. 38, pp. 1258-1268, 1992.
  * [19] D. P. Foster, “Prediction in the worst case,” Ann. of Statist.,  vol. 19, pp. 1084-1090, 1991.
  * [20] Y. Freund, “Predicting a binary sequence almost as well as the optimal biased coin,” Proc. of the 9th Annual Workshp on Computational Learning Theory, pp. 89-98, Morgan Kaufmann, 1996.
  * [21] R. M. Gray, Probability, random processes, and ergodic properties, Springer, 1988.
  * [22] R. M. Gray and J. C. Kieffer, “Asymptotically Mean Stationary Measures.” Ann. Probab. 8 (5) 962 - 973, October, 1980.
  * [23] J. A. Hartigan, “Invariant prior distributions,” Ann. Math. Statist., vol. 35, pp. 836-845, 1964.
  * [24] J. A. Hartigan, “The asymptotically unbiased density,” Ann. Math. Statist., vol. 36, pp. 1137-1152, 1965.
  * [25] D. Haussler, “A general minimax result for relative entropy,” IEEE trans. Inform. Theory, vol. 43, no. 4, pp. 1276-1280, 1997.
  * [26] D. Haussler and A. R. Barron, “How well do Bayes methods work for on-line prediction of {$\pm 1\\}$ values,” Proceedings 1992 NEC Symposium on Computation and Cognition, Chapter 4.
  * [27] D. Haussler, J. Kivinen and M. K. Warmuth, “Tight worst-case loss bounds for prediction with expert advice,” IEEE trans. Inform. Theory, vol. 44, 1998.
  * [28] R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge: Cambridge Univ. Press. 1990.
  * [29] P. J. Huber, Robust Statistics, Wiley & Sons, Hoboken, NJ, USA, 2004.
  * [30] I. Ibragimov and R. Hasminski, Statistical estimation; Asymptotic theory, Springer, New York, 1981.
  * [31] H. Jeffreys, Theory of probability, 3rd ed. , Univ. of California Press, Berkeley, Cal, 1961.
  * [32] J. C. Kieffer, “A Counterexample to Perez’s Generalization of the Shannon-McMillan Theorem,” Ann. Probab. 1(2): 362-364, April, 1973.
  * [33] L. Le Cam, Asymptotic Methods in Statistical Decision Theory (Springer Series in Statistics), Springer New York, 1986.
  * [34] K. Miyamoto and J. Takeuchi, “On MDL Estimation for Simple Contaminated Gaussian Location Families,” in Proc. of the 2020 International Symposium on Information Theory and Its Applications (ISITA 2020), Octeber 2020.
  * [35] A. Perez. “Extensions of Shannon-McMillan’s limit theorem to more general stochastic processes processes,” In Third Prague Conf. on Inform. Theory, Decision Functions,and Random Processes, pp. 545.574, Prague and New York, 1964. Publishing House Czech. Akad. Sci. and Academic Press.
  * [36] D. Pollard, Online notes, http://web.archive.org/web/20160524113206/http://www.stat.yale.edu/~pollard/Books/Asymptopia/, viewed on March 1, 2024.
  * [37] J. Rissanen, “Fisher information and stochastic complexity,” IEEE trans. Inform. Theory, vol. 40, pp. 40-47, 1996.
  * [38] W. R. Rudin, Principles of Mathematical Analysis, Third Edition, McGraw–Hill, 1976.
  * [39] Yu M. Shtarkov, “Universal sequential coding of single messages,” Problems of Information Transmission, vol. 23, pp. 3-17, July 1988.
  * [40] J. Takeuchi and A. R. Barron, “Asymptotically minimax regret by Bayes mixtures,” Proc. of 1998 IEEE ISIT, p. 1998.
  * [41] J. Takeuchi and A. R. Barron, “Asymptotically minimax regret for models with hidden variables,” Proc. of 2014 IEEE International Symposium on Information Theory, pp. 3037-3041, Honolulu, HI, USA, June 29 - July 4, 2014.
  * [42] J. Takeuchi and A. R. Barron, “Stochastic Complexity for Tree Models,” Proc. of 2014 IEEE Information Theory Workshop, pp. 223-227, Hobart, Tasmania, Australia, November 2-5, 2014.
  * [43] J. Takeuchi and A. R. Barron. Device, method, and medium for predicting a probability of an occurrence of data. US Patent Publication 6892164 B2. Also US6766280. Filed August 26, 2002. Granted. Published July 20, 2004 and May 10, 2005.
  * [44] J. Takeuchi, T. Kawabata, and A. R. Barron, “Properties of Jeffreys Mixture for Markov Sources,” of IEEE Transactions on Information Theory, Vol. 59, No. 1, pp. 438-457, January 2013.
  * [45] J. Takeuchi and H. Nagaoka, “Information Geometry of The Family of Markov Kernels Defined by A Context Tree,” in Proc. of 2017 IEEE Information Theory Workshop, Kaohsiung, Taiwan, November 6-10, 2017.
  * [46] V. Vovk, “Aggregating starategies,” Proc. 3rd Annual Workshop on Computational Learning Theory, Morgan, Kaufmann, pp. 371-383, 1990.
  * [47] A. Wald, “Note on the Consistency of the Maximum Likelihood Estimate,” The Annals of Mathematical Statistics, Vol. 20, No. 4, pp. 595-601, Dec., 1949.
  * [48] F. Willems, Y. Shtarkov and T. Tjalkens, “The context tree weighting method: basic properties,” IEEE trans. Inform. Theory, vol. 41. no. 3, pp. 653-664, 1995.
  * [49] M. J. Weinberger, J. Rissanen, and M. Feder, “A universal finite memory source,” IEEE trans. Inform. Theory, Vol. 41. No. 3, pp. 643-652, 1995.
  * [50] Q. Xie and A. R. Barron, “Minimax redundancy for the class of memoryless sources,” IEEE trans. Inform. Theory, vol. 43, no. 2, pp. 646-657, 1997.
  * [51] Q. Xie and A. R. Barron, “Asymptotic minimax regret for data compression, gambling and prediction,” IEEE trans. Inform. Theory, vol. 46, no. 2, pp. 431-445, 2000.
  * [52] J. Takeuchi, Computational learning theory of probabilistic knowledge representations (in Japanese), Doctoral dissertation, Faculty of Engineering, Univ. of Tokyo, 1995.
  * [53] J. Takeuchi and S. Amari, “The $\alpha$-parallel prior and its properties (in Japanese),” Technical Report of IEICE, 1996\.