$m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}$ terms cancel. Therefore, we are left
with

$\displaystyle{n}_{i}^{1/2}(\hat{\bm{\beta}}+\hat{\bm{b}}_{i}-\dot{\bm{\beta}}-\dot{\bm{b}}_{i})$
$\displaystyle=n_{i}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i})^{-1}n_{i}^{-1/2}\\{\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})\\}$
$\displaystyle+O_{p}(m^{-1/2})+O_{p}(n_{L}^{-1/2})+O_{p}(m^{-1}n_{U}^{1/2})$
$\displaystyle=n_{i}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i})^{-1}n_{i}^{-1/2}\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})+o_{p}(1).$

The required result follows from the Dominated Convergence Theorem.

###  S2.7 Result for Difference Between the Prediction Gaps of Two Clusters

Assume Conditions (C1)-(C5) are satisfied, $mn_{L}^{-2}\rightarrow 0$,
$mn_{U}^{-1/2}\rightarrow\infty$, and
$n_{i}n_{i^{\prime}}^{-1}\rightarrow\gamma\in(0,\infty)$. Then as
$m,n_{L}\rightarrow\infty$ and unconditional on the random effects
$\dot{\bm{b}}$, for each $i\neq i^{\prime}\in\\{1,\ldots,m\\}$ we have

$\displaystyle{n}_{i}^{1/2}\\{(\hat{\bm{b}}_{i}-\dot{\bm{b}}_{i})-(\hat{\bm{b}}_{i^{\prime}}-\dot{\bm{b}}_{i^{\prime}})\\}$
$\displaystyle\overset{D}{\rightarrow}\text{mixN}(\bm{0},\dot{\bm{K}}_{i},F_{\dot{\bm{b}}_{i}})*\,\text{mixN}(\bm{0},\gamma\dot{\bm{K}}_{i^{\prime}},F_{\dot{\bm{b}}_{i^{\prime}}}).$

Proof: Theorem 4 implies that, given $mn_{L}^{-2}\rightarrow 0$,
$mn_{U}^{-1/2}\rightarrow\infty$, and
$n_{i}n_{i^{\prime}}^{-1}\rightarrow\gamma\in(0,\infty)$, we have

$\displaystyle{n}_{i}^{1/2}(\hat{\bm{b}}_{i}-\dot{\bm{b}}_{i}-\hat{\bm{b}}_{i^{\prime}}+\dot{\bm{b}}_{i^{\prime}})$
$\displaystyle=(n_{i}^{-1}\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i})^{-1}n_{i}^{-1/2}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})$
$\displaystyle+\gamma^{1/2}(n_{i^{\prime}}^{-1}\bm{X}_{i^{\prime}}^{\top}\dot{\bm{W}}_{i^{\prime}}\bm{X}_{i^{\prime}})^{-1}n_{i^{\prime}}^{-1/2}\bm{X}_{i^{\prime}}^{\top}(\bm{y}_{i^{\prime}}-\dot{\bm{\mu}}_{i^{\prime}})$
$\displaystyle+O_{p}(m^{-1/2})+O_{p}(n_{L}^{-1/2})+O_{p}(m^{-1}n_{U}^{1/2}),$

and the result follows by the independence of $\dot{\bm{b}}_{i}$ and
$\dot{\bm{b}}_{i^{\prime}}$.

##  S3 Remainder Term in the Taylor Expansion

In this section, we show that in the Taylor expansion (S2.2), the remainder
term
$-\frac{1}{2}\\{\nabla^{2}Q(\dot{\bm{\theta}})\\}^{-1}\bm{R}(\tilde{\bm{\theta}})$
is of smaller order component-wise than
$-\\{\nabla^{2}Q(\dot{\bm{\theta}})\\}^{-1}\nabla Q(\dot{\bm{\theta}})$. To
deal with this remainder term, we have the following from equation (S2.2)

$\displaystyle\hat{\bm{\theta}}-\dot{\bm{\theta}}=\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})+\frac{1}{2}\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})$
$\displaystyle\Rightarrow\,$
$\displaystyle\hat{\bm{\theta}}-\dot{\bm{\theta}}-\frac{1}{2}\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})=\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ $\displaystyle\Rightarrow\,$
$\displaystyle(\bm{I}_{(m+1)p}-\bm{\Lambda})(\hat{\bm{\theta}}-\dot{\bm{\theta}})=\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ $\displaystyle\Rightarrow\,$
$\displaystyle\hat{\bm{\theta}}-\dot{\bm{\theta}}=(\bm{I}_{(m+1)p}-\bm{\Lambda})^{-1}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ $\displaystyle=\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})+\left(\sum_{s=1}^{\infty}\bm{\Lambda}^{s}\right)\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}}),$

where the last line is derived from repeated application of the Woodbury
identity, and $\bm{\Lambda}$ is the appropriate $(m+1)p\times(m+1)p$ matrix
defined in detail later on. The convergence of the geometric sum and thus
invertibility of $(\bm{I}_{(m+1)p}-\bm{\Lambda})$ is shown in Lemma 4. We will
show, using the consistency result
$\|\hat{\bm{\theta}}-\dot{\bm{\theta}}\|_{\infty}=o_{p}(1)$, that
$\sum_{s=1}^{\infty}\bm{\Lambda}^{s}\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ is
of smaller order component-wise than $\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$.
This is equivalent to $0.5\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})$ being
smaller order component-wise than $\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ in
(S2.2).

Let $\bm{T}_{1}$ denote the first $p$ components of
$\bm{R}(\tilde{\bm{\theta}})$, $\bm{T}_{2}$ its remaining $mp$ components, and
$\bm{T}_{2i}$ denote the $\\{(i-1)p+1\\}$-th to $(ip)$-th components of
$\bm{T}_{2}$. We first prove a result needed for later developments.

######  Lemma 3.

Assume Conditions (C1) and (C3) are satisfied. Then irrespective of whether
$\dot{\bm{b}}$ is conditioned on, it holds that
$\bm{R}(\tilde{\bm{\theta}})_{[1:p]}=\sum_{i=1}^{m}\bm{R}(\tilde{\bm{\theta}})_{[ip+1:(i+1)p]}.$

###### Proof.

Recall the Taylor expansion $\nabla Q(\hat{\bm{\theta}})=\bm{0}=\nabla
Q(\dot{\bm{\theta}})+\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})+\bm{R}(\tilde{\bm{\theta}})$.
Then

$\displaystyle\bm{0}_{p\times 1}$ $\displaystyle=\nabla
Q(\hat{\bm{\theta}})_{[1:p]}$ $\displaystyle=\\{\nabla
Q(\dot{\bm{\theta}})+\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})+\bm{R}(\tilde{\bm{\theta}})\\}_{[1:p]}$
$\displaystyle=\sum_{i=1}^{m}\nabla Q(\hat{\bm{\theta}})_{[ip+1:(i+1)p]}$
$\displaystyle=\sum_{i=1}^{m}\\{\nabla
Q(\dot{\bm{\theta}})+\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})+\bm{R}(\tilde{\bm{\theta}})\\}_{[ip+1:(i+1)p]}.$

Since $\bm{Z}_{i}=\bm{X}_{i}$ for all $i=1,\ldots,m$ under our simplifying
assumption, and $\sum_{i=1}^{m}\hat{\bm{b}}_{i}=\bm{0}$, then we obtain

$\displaystyle\\{\nabla
Q(\dot{\bm{\theta}})+\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})+\bm{R}(\tilde{\bm{\theta}})\\}_{[1:p]}$
$\displaystyle=\sum_{i=1}^{m}\\{\nabla
Q(\dot{\bm{\theta}})+\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})+\bm{R}(\tilde{\bm{\theta}})\\}_{[ip+1:(i+1)p]}.$

Therefore, we have
$\bm{T}_{1}=\bm{R}(\tilde{\bm{\theta}})_{[1:p]}=\sum_{i=1}^{m}\bm{R}(\tilde{\bm{\theta}})_{[ip+1:(i+1)p]}=\sum_{i=1}^{m}\bm{T}_{2i}$,
which follows from the fact that $\sum_{i=1}^{m}\nabla
Q(\dot{\bm{\theta}})_{[ip+1:(i+1)p]}=\nabla
Q(\dot{\bm{\theta}})_{[1:p]}-\sum_{i=1}^{m}\hat{\bm{G}}^{-1}\dot{\bm{b}}_{i}$
and
$\sum_{i=1}^{m}\\{\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\}_{[ip+1:(i+1)p]}=\\{\nabla^{2}Q(\dot{\bm{\theta}})(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\}_{[1:p]}+\sum_{i=1}^{m}\hat{\bm{G}}^{-1}\dot{\bm{b}}_{i}-\sum_{i=1}^{m}\hat{\bm{G}}^{-1}\hat{\bm{b}}_{i}$.
∎

Next, let $\bm{S}(\bm{\theta})=\nabla Q(\bm{\theta})$,
$\tilde{\bm{W}}^{\prime}=\dot{\phi}^{-1}\text{diag}\\{a^{\prime\prime\prime}(\tilde{\eta}_{11}),\ldots,a^{\prime\prime\prime}(\tilde{\eta}_{1n_{1}}),\ldots,a^{\prime\prime\prime}(\tilde{\eta}_{mn_{m}})\\}$.
Then the remainder term can be written as

$\displaystyle\bm{R}(\tilde{\bm{\theta}})=\left[\begin{matrix}(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[1]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\\
\vdots\\\
(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[(m+1)p]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\\
\end{matrix}\right].$

Now, for $1\leq j\leq p$, we have
$\bm{S}_{[j]}(\bm{\theta})=\dot{\phi}^{-1}\bm{X}_{[,j]}^{\top}\\{\bm{y}-\bm{\mu}(\bm{\theta})\\}=\dot{\phi}^{-1}\sum_{i=1}^{m}\sum_{l=1}^{n_{i}}x_{il[j]}\\{y_{il}-a^{\prime}(\eta_{il})\\}$,
noting this is a scalar. Thus

$\displaystyle\frac{\partial}{\partial\bm{\theta}}\bm{S}_{[j]}(\bm{\theta})=-\dot{\phi}^{-1}\sum_{i=1}^{m}\sum_{l=1}^{n_{i}}\left[\begin{matrix}\bm{x}_{il}\\\
\frac{\partial}{\partial\bm{b}}\eta_{il}\end{matrix}\right]a^{\prime\prime}(\eta_{il})x_{il[j]}=-\left[\begin{matrix}\bm{X}^{\top}\bm{W}\bm{X}_{[,j]}\\\
\bm{Z}^{\top}\bm{W}\bm{X}_{[,j]}\end{matrix}\right],$

which is an $(m+1)p$-vector. Hence the $(m+1)p\times(m+1)p$ matrix can be
written as

$\displaystyle\frac{\partial^{2}\bm{S}_{[j]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}$
$\displaystyle=-\dot{\phi}^{-1}\sum_{i=1}^{m}\sum_{l=1}^{n_{i}}\left[\begin{matrix}\bm{x}_{il}\\\
\frac{\partial}{\partial\bm{b}}\eta_{il}\end{matrix}\right]a^{\prime\prime\prime}(\tilde{\eta}_{il})x_{il[j]}\left[\begin{matrix}\bm{x}_{il}\\\
\frac{\partial}{\partial\bm{b}}\eta_{il}\end{matrix}\right]^{\top}$
$\displaystyle=-\left[\begin{matrix}\bm{X}^{\top}\text{diag}(\bm{X}_{[,j]})\tilde{\bm{W}}^{\prime}\bm{X}&\bm{X}^{\top}\text{diag}(\bm{X}_{[,j]})\tilde{\bm{W}}^{\prime}\bm{Z}\\\
\bm{Z}^{\top}\text{diag}(\bm{X}_{[,j]})\tilde{\bm{W}}^{\prime}\bm{X}&\bm{Z}^{\top}\text{diag}(\bm{X}_{[,j]})\tilde{\bm{W}}^{\prime}\bm{Z}\end{matrix}\right],\quad
1\leq j\leq p.$

Similarly, for $1\leq k\leq mp$,
$\bm{S}_{[p+k]}(\bm{\theta})=\dot{\phi}^{-1}\bm{Z}_{[,k]}^{\top}\\{\bm{y}-\bm{\mu}(\bm{\theta})\\}-\\{(\bm{I}_{m}\otimes\hat{\bm{G}})\bm{b}\\}_{[k]}$,
such that

$\displaystyle\frac{\partial}{\partial\bm{\theta}}\bm{S}_{[p+k]}(\bm{\theta})=-\left[\begin{matrix}\bm{X}^{\top}\bm{W}\bm{Z}_{[,k]}\\\
\bm{Z}^{\top}\bm{W}\bm{Z}_{[,k]}+\frac{\partial}{\partial\bm{b}}\\{(\bm{I}_{m}\otimes\hat{\bm{G}})\bm{b}\\}_{[k]}\end{matrix}\right],$

where
$\partial/\partial\bm{b}\\{(\bm{I}_{m}\otimes\hat{\bm{G}})\bm{b}\\}_{[k]}$ is
not a function of $\bm{\theta}$. Thus

$\displaystyle\frac{\partial^{2}\bm{S}_{[p+k]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}=-\left[\begin{matrix}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}&\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{Z}\\\
\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}&\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{Z}\end{matrix}\right],\quad
1\leq k\leq mp.$

Next, recall that
$\bm{B}_{2}(\bm{B}_{3}+\bm{B}_{4})^{-1}=[\bm{I}_{p}-\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{1}\dot{\bm{W}}_{1}\bm{X}_{1}+\hat{\bm{G}}^{-1})^{-1},\ldots,\bm{I}_{p}-\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{m}\dot{\bm{W}}_{m}\bm{X}_{m}+\hat{\bm{G}}^{-1})^{-1}]$.
By Lemma 1 and the blockwise inversion formula for $\bm{B}^{-1}$, the first
$p$ components of $\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})$ are given by

$\displaystyle\left[\begin{matrix}\bm{C}^{-1}&-\bm{C}^{-1}\bm{B}_{2}(\bm{B}_{3}+\bm{B}_{4})^{-1}\end{matrix}\right]\bm{R}(\tilde{\bm{\theta}})$
$\displaystyle=\bm{C}^{-1}\left[\begin{matrix}\bm{I}_{p}&-[\bm{I}_{p}-\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{1}\dot{\bm{W}}_{1}\bm{X}_{1}+\hat{\bm{G}}^{-1})^{-1},\ldots,\bm{I}_{p}-\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{m}\dot{\bm{W}}_{m}\bm{X}_{m}+\hat{\bm{G}}^{-1})^{-1}]\end{matrix}\right]\bm{R}(\tilde{\bm{\theta}})$
$\displaystyle=\bm{C}^{-1}\left\\{\bm{T}_{1}-\sum_{i=1}^{m}\bm{T}_{2i}+\sum_{i=1}^{m}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{T}_{2i}\right\\}.$
(S3.1)

Similarly, the last $mp$ components of
$\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})$ are

$\displaystyle\left[\begin{matrix}-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\bm{C}^{-1}&(\bm{B}_{3}+\bm{B}_{4})^{-1}+(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\bm{C}^{-1}\bm{B}_{2}(\bm{B}_{3}+\bm{B}_{4})^{-1}\end{matrix}\right]\bm{R}(\tilde{\bm{\theta}})$
$\displaystyle=-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\left[\begin{matrix}\bm{C}^{-1}&-\bm{C}^{-1}\bm{B}_{2}(\bm{B}_{3}+\bm{B}_{4})^{-1}\end{matrix}\right]\bm{R}(\tilde{\bm{\theta}})+(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{T}_{2}.$
(S3.2)

Hence the first $p$ components of $\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})$ are
given by

$\displaystyle\bm{F}_{1}=\bm{C}^{-1}\sum_{i=1}^{m}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{T}_{2i},$

and the last $mp$ components of $\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})$ are
given by

$\displaystyle\bm{F}_{2}=-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\bm{F}_{1}+(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{T}_{2}.$

Next, we have

$\displaystyle\bm{T}_{2}$
$\displaystyle=\left[\begin{matrix}(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[p+1]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\\
\vdots\\\
(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[(m+1)p]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\end{matrix}\right]=\left[\begin{matrix}(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[p+1]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}\\\
\vdots\\\
(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[(m+1)p]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}\end{matrix}\right](\hat{\bm{\theta}}-\dot{\bm{\theta}})\triangleq\bm{F}_{3}(\hat{\bm{\theta}}-\dot{\bm{\theta}})$

and

$\displaystyle\bm{T}_{2i}$
$\displaystyle=\left[\begin{matrix}(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[(i-1)p+1]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\\
\vdots\\\
(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[ip]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\end{matrix}\right]=\left[\begin{matrix}(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[(i-1)p+1]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}\\\
\vdots\\\
(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\frac{\partial^{2}\bm{S}_{[ip]}(\tilde{\bm{\theta}})}{\partial\bm{\theta}\partial\bm{\theta}^{\top}}\end{matrix}\right](\hat{\bm{\theta}}-\dot{\bm{\theta}})\triangleq\bm{F}_{3i}(\hat{\bm{\theta}}-\dot{\bm{\theta}}).$

Here, $\bm{F}_{3}$ is a $mp\times(m+1)p$ matrix and $\bm{F}_{3i}$ is
$p\times(m+1)p$. Notice that
$\bm{F}_{3}=[\bm{F}_{31}^{\top},\ldots,\bm{F}_{3n}^{\top}]^{\top}$.
Furthermore,

$\displaystyle\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})=\left[\begin{matrix}\bm{F}_{1}\\\
\bm{F}_{2}\end{matrix}\right]=\left[\begin{matrix}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{T}_{2i}\\\
-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\bm{F}_{1}+(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{T}_{2}\end{matrix}\right]$
$\displaystyle=\left[\begin{matrix}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\\\
-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}(\hat{\bm{\theta}}-\dot{\bm{\theta}})+(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{F}_{3}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\end{matrix}\right]$
$\displaystyle=\left[\begin{matrix}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}+(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{F}_{3}\end{matrix}\right](\hat{\bm{\theta}}-\dot{\bm{\theta}})$
$\displaystyle=2\bm{\Lambda}(\hat{\bm{\theta}}-\dot{\bm{\theta}}).$

The $k$th row of $\bm{F}_{3i}$ for $1\leq k\leq p$ is given by

$\displaystyle-(\hat{\bm{\theta}}-\dot{\bm{\theta}})^{\top}\left[\begin{matrix}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{X}&\bm{X}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{Z}\\\
\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{X}&\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{Z}\end{matrix}\right]$
$\displaystyle=-\delta_{m,n_{L}}^{-1}\big{[}\delta_{m,n_{L}}(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{X}+\delta_{m,n_{L}}(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{X},$
$\displaystyle\delta_{m,n_{L}}(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{Z}+\delta_{m,n_{L}}(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{Z}\big{]},$
(S3.3)

where $\delta_{m,n_{L}}$ is a positive unbounded monotonically increasing
sequence such that
$\delta_{m,n_{L}}\|\hat{\bm{\theta}}-\dot{\bm{\theta}}\|_{\infty}=O_{p}(1)$.
The consistency results proved in Section S1 ensure that such a
$\delta_{m,n_{L}}$ must exist; this is true for both the conditional and
unconditional regimes.

Observe that only the $\\{(\sum_{l=0}^{i-1}n_{l})+1\\}$th to
$(\sum_{l=0}^{i}n_{l})$th components of $\bm{Z}_{[,(i-1)p+k]}$ are non-zero,
where we define $n_{0}:=0$. This means that, for any $1\leq k\leq p$, only the
$\\{(i-1)p+1\\}$th to $(ip)$th columns of both
$\bm{X}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{Z}$
and
$\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,(i-1)p+k]})\tilde{\bm{W}}^{\prime}\bm{Z}$
will be non-zero. In other words, other than the first $p$ columns, only the
$(ip+1)$th to $\\{(i+1)p\\}$th columns of $\bm{F}_{3i}$ are non-zero. Thus
$\bm{F}_{3}$, disregarding its first $p$ columns, is an $mp\times mp$ block-
diagonal matrix.

The non-zero components of $\delta_{m,n_{L}}\bm{F}_{3}$ and
$\delta_{m,n_{L}}\bm{F}_{3i}$ are all $O_{p}(n_{U})$ component-wise, again
because at most $n_{i}$ components of $\bm{Z}_{[,(i-1)p+k]}$ are non-zero. For
ease of notation and understanding, we now represent all terms using their
orders only. Since $\bm{C}^{-1}=O_{p}(m^{-1})$ and
$\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}=O_{p}(n_{i}^{-1})$,
from the above discussion we have that
$\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}$
is a $p\times(m+1)p$ matrix of the form
$\delta_{m,n_{L}}^{-1}[O_{p}(1),O_{p}(m^{-1}),\ldots,O_{p}(m^{-1})]$. Next,
$(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}=[\bm{I}_{p}+O_{p}(n_{1}^{-1}),\ldots,\bm{I}_{p}+O_{p}(n_{m}^{-1})]^{\top}$
and $(\bm{B}_{3}+\bm{B}_{4})^{-1}$ is a block-diagonal $O_{p}(n_{L}^{-1})$
matrix component-wise. Therefore, we find that $\bm{\Lambda}$ is of the form

$\displaystyle
0.5\left[\begin{matrix}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
-(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{B}_{2}^{\top}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\end{matrix}\right]+0.5\left[\begin{matrix}\bm{0}_{p\times(m+1)p}\\\
(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{F}_{3}\end{matrix}\right]$
$\displaystyle\triangleq\bm{\Lambda}_{1}+\bm{\Lambda}_{2}$
$\displaystyle=\frac{1}{\delta_{m,n_{L}}}\left[\begin{matrix}O_{p}(1)&O_{p}(m^{-1})&\cdots&O_{p}(m^{-1})\\\
\vdots&\vdots&\vdots&\vdots\\\
O_{p}(1)&O_{p}(m^{-1})&\cdots&O_{p}(m^{-1})\end{matrix}\right]+\frac{1}{\delta_{m,n_{L}}}\left[\begin{matrix}&&\bm{0}_{p\times(m+1)p}\\\
O_{p}(1)&O_{p}(1)&\bm{0}&\cdots&\bm{0}\\\
O_{p}(1)&\bm{0}&O_{p}(1)&\cdots&\bm{0}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
O_{p}(1)&\bm{0}&\cdots&\bm{0}&O_{p}(1)\end{matrix}\right]$
$\displaystyle=\frac{1}{\delta_{m,n_{L}}}\left[\begin{matrix}O_{p}(1)&O_{p}(m^{-1})&O_{p}(m^{-1})&\cdots&O_{p}(m^{-1})\\\
O_{p}(1)&O_{p}(1)&O_{p}(m^{-1})&\cdots&O_{p}(m^{-1})\\\
O_{p}(1)&O_{p}(m^{-1})&O_{p}(1)&\cdots&O_{p}(m^{-1})\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
O_{p}(1)&O_{p}(m^{-1})&\cdots&O_{p}(m^{-1})&O_{p}(1)\end{matrix}\right].$
(S3.4)

Writing $\bm{\Lambda}=\delta_{m,n_{L}}^{-1}\bm{\Lambda}_{\delta}$, we see that
the component-wise order of $\bm{\Lambda}_{\delta}$ remains the same no matter
how many times it is multiplied by itself. Furthermore, each row of
$\bm{\Lambda}_{\delta}^{s}$ is $O_{p}(1)$ for only a finite number of
components, and $O_{p}(m^{-1})$ for the others. We will use these facts to
examine the behaviour of $\sum_{s=1}^{\infty}\bm{\Lambda}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})=\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$, and we will do so separately for the conditional and
unconditional regimes. Before proceeding, we first confirm the convergence of
$\sum_{s=1}^{\infty}\bm{\Lambda}^{s}$.

######  Lemma 4.

Assume Conditions (C1)-(C5) are satisfied. Then with probability tending to
one as $m,n_{L}\rightarrow\infty$, the geometric sum
$\sum_{s=1}^{\infty}\bm{\Lambda}^{s}$ converges.

###### Proof.

To prove the result we will show that, with probability tending to one as
$m,n_{L}\rightarrow\infty$, $\|\bm{\Lambda}\|<1$ for some sub-multiplicative
matrix norm $\|\cdot\|$. In particular, we will consider the maximum absolute
row sum of $\bm{\Lambda}$, denoted by $\|\cdot\|_{\infty}$ i.e., the operator
norm induced by the vector infinity norm.

From (S3.4), we have
$\|\bm{\Lambda}\|_{\infty}\leq\|\bm{\Lambda}_{1}\|_{\infty}+\|\bm{\Lambda}_{2}\|_{\infty}$.
We first examine $\|\bm{\Lambda}_{1}\|_{\infty}$. We may break up
$\bm{\Lambda}_{1}$ into

$\displaystyle
0.5\left[\begin{matrix}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
-\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
-\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
\vdots\end{matrix}\right]+$ $\displaystyle
0.5\left[\begin{matrix}\bm{0}_{p}\\\
(\bm{X}^{\top}_{1}\dot{\bm{W}}_{1}\bm{X}_{1}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
(\bm{X}^{\top}_{2}\dot{\bm{W}}_{2}\bm{X}_{2}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\\\
\vdots\\\
(\bm{X}^{\top}_{m}\dot{\bm{W}}_{m}\bm{X}_{m}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1}\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\end{matrix}\right]$
$\displaystyle\triangleq\bm{\Lambda}_{3}+\bm{\Lambda}_{4}\bm{\Lambda}_{5},$

where $\bm{\Lambda}_{4}=\text{bdiag}(\bm{0}_{p\times
p},(\bm{X}^{\top}_{1}\dot{\bm{W}}_{1}\bm{X}_{1}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1},\ldots,(\bm{X}^{\top}_{m}\dot{\bm{W}}_{m}\bm{X}_{m}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1})$,
and
$\bm{\Lambda}_{5}=(0,\bm{1}_{m}^{\top})^{\top}\otimes\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}$.
We can also write
$\bm{\Lambda}_{3}=-0.5(\bm{1}_{m}^{*}\otimes\bm{I}_{p})\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}$
and use the (component-wise) order results as used in (S3.4) to see that
$\|\bm{\Lambda}_{3}\|_{\infty}\leq\|-0.5(\bm{1}_{m}^{*}\otimes\bm{I}_{p})\|_{\infty}\|\sum_{i=1}^{m}\bm{C}^{-1}\hat{\bm{G}}^{-1}(\bm{X}^{\top}_{i}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\bm{F}_{3i}\|_{\infty}=o_{p}(1)$.
Next, we have
$\|\bm{\Lambda}_{4}\bm{\Lambda}_{5}\|_{\infty}\leq\|\bm{\Lambda}_{4}\|_{\infty}\|\bm{\Lambda}_{5}\|_{\infty}$.
We know $\|\bm{\Lambda}_{5}\|_{\infty}=o_{p}(1)$, and under conditions
(C1)-(C2), we have $\|\bm{\Lambda}_{4}\|_{\infty}=O_{p}(1)$. Thus we obtain
$\|\bm{\Lambda}_{1}\|_{\infty}=o_{p}(1)$.

Turning to $\bm{\Lambda}_{2}$, we examine each row of
$(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{F}_{3}$. First,
$\|(\bm{B}_{3}+\bm{B}_{4})^{-1}\bm{F}_{3}\|_{\infty}\leq\|(\bm{B}_{3}+\bm{B}_{4})^{-1}\|_{\infty}\|\bm{F}_{3}\|_{\infty}$
and by conditions (C1)-(C2), we have
$\|(\bm{B}_{3}+\bm{B}_{4})^{-1}\|_{\infty}=O_{p}(n_{L}^{-1})$. Now, without
loss of generality consider the first row of $\bm{F}_{3}$. This is given by

$\displaystyle-\Bigg{[}(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}+(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X},$
$\displaystyle(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{Z}+(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{Z}\Bigg{]}$
$\displaystyle=-\Bigg{[}(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}+(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X},$
$\displaystyle(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}+(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X},\bm{0}_{(m-1)p}^{\top}\Bigg{]},$

since $\text{diag}(\bm{Z}_{[,1]})$ selects for the first cluster. Let
$\bar{\bm{1}}_{p}$ be a $p$-vector whose entries consist of the (component-
wise) signs of
$(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}+(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}$.
Then the absolute row sum of the first row of $\bm{F}_{3}$ is given by

$\displaystyle
2|\\{(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}+(\hat{\bm{b}}-\dot{\bm{b}})^{\top}\bm{Z}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\bar{\bm{1}}_{p}|$
$\displaystyle=$ $\displaystyle
2|\\{(\hat{\bm{\beta}}-\dot{\bm{\beta}})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}+(\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\bar{\bm{1}}_{p}|$
$\displaystyle=$ $\displaystyle
2|\\{(\hat{\bm{\beta}}-\dot{\bm{\beta}}+\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1})^{\top}\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\bar{\bm{1}}_{p}|$
$\displaystyle\leq$ $\displaystyle
2p\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}(\hat{\bm{\beta}}-\dot{\bm{\beta}}+\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1})\\}\|_{\infty}$
$\displaystyle\leq$ $\displaystyle
2p\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}\|\hat{\bm{\beta}}-\dot{\bm{\beta}}+\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}\|_{\infty}$
$\displaystyle\leq$ $\displaystyle
2p\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,1]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}(\|\hat{\bm{\beta}}-\dot{\bm{\beta}}\|_{\infty}+\|\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}\|_{\infty})$
$\displaystyle\leq$ $\displaystyle
2p\underset{k\in\\{1,\ldots,mp\\}}{\max}\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}(\|\hat{\bm{\beta}}-\dot{\bm{\beta}}\|_{\infty}+\|\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}\|_{\infty})$
$\displaystyle=$ $\displaystyle
2p\underset{k\in\\{1,\ldots,mp\\}}{\max}\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}\|\hat{\bm{\beta}}-\dot{\bm{\beta}}\|_{\infty}$
$\displaystyle+2p\underset{k\in\\{1,\ldots,mp\\}}{\max}\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}\|\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}\|_{\infty}$
$\displaystyle\triangleq\alpha+\alpha_{1}\triangleq\omega_{1},$

where the second equality follows from $\text{diag}(\bm{Z}_{[,1]})$ selecting
for only the first cluster, and $\bm{X}_{i}=\bm{Z}_{i}$. The first inequality
is due to Hölder’s inequality. Again, using Conditions (C1)-(C2) we have
$\underset{k\in\\{1,\ldots,mp\\}}{\max}\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}=O_{p}(n_{U})$.

Now, $p$ is a constant and the absolute row sum of any row of $\bm{F}_{3}$ can
be bounded analogously in the above way, the only difference being that for
the $k$th row, then the quantity $(\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1})$ changes
to the prediction gap for the cluster that $\text{diag}(\bm{Z}_{[,k]})$
selects for. This means that the absolute row sums for the first $p$ rows of
$\bm{F}_{3}$ are bounded by $\omega_{1}$, the next $p$ rows by $\omega_{2}$,
and so on. Hence, to ensure $\|\bm{\Lambda}_{2}\|_{\infty}=o_{p}(1)$ it
suffices to ensure that
$\|\bm{\omega}\otimes\bm{1}_{p}\|_{\infty}=\|\bm{\omega}\|_{\infty}=o_{p}(n_{L})$,
where $\bm{\omega}=(\omega_{1},\ldots,\omega_{m})^{\top}$.

To show this, define $\bm{\alpha}=(\alpha_{1},\ldots,\alpha_{m})^{\top}$. Then
$\|\bm{\omega}\|_{\infty}\leq\|\alpha\bm{1}_{m}\|_{\infty}+\|\bm{\alpha}\|_{\infty}$.
By Conditions (C1)-(C2), we have
$\|\alpha\bm{1}_{m}\|_{\infty}=\alpha=O_{p}(n_{U})\times
o_{p}(1)=o_{p}(n_{U})=o_{p}(n_{L})$. We also have

$\displaystyle\|\bm{\alpha}\|_{\infty}$
$\displaystyle=2p\underset{k\in\\{1,\ldots,mp\\}}{\max}\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}\underset{i\in\\{1,\ldots,m\\}}{\max}\|\hat{\bm{b}}_{i}-\dot{\bm{b}}_{i}\|_{\infty}$
$\displaystyle=2p\underset{k\in\\{1,\ldots,mp\\}}{\max}\|\\{\bm{X}^{\top}\text{diag}(\bm{Z}_{[,k]})\tilde{\bm{W}}^{\prime}\bm{X}\\}\|_{\infty}\|\hat{\bm{b}}-\dot{\bm{b}}\|_{\infty}$
$\displaystyle=O_{p}(n_{U})\times o_{p}(1)=o_{p}(n_{U})=o_{p}(n_{L}),$

where the last line follows from conditions (C1)-(C2), and the fact that
$\|\hat{\bm{\theta}}-\dot{\bm{\theta}}\|_{\infty}=o_{p}(1)$. The result
follows since $\|\bm{\Lambda}\|_{\infty}$ is therefore of order $o_{p}(1)$,
and for any $\epsilon>0$ we have $\|\bm{\Lambda}\|_{\infty}<\epsilon$ with
probability tending to one as $m,n_{L}\rightarrow\infty$. The argument above
holds for both the conditional and unconditional regime, and the required
result follows. ∎

###  S3.1 Conditional Regime

In the conditional regime, we assume without loss of generality that
$\sum_{i=1}^{m}\dot{\bm{b}}_{i}=\bm{0}_{p}$, recalling that we can always
reparametrise the random effects to satisfy this. From previous derivations,
we know that when $mn_{L}^{-1}\rightarrow 0$, the quantity $\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ is of order $O_{p}(N^{-1/2})$ for the first $p$
components and $O_{p}(n_{L}^{-1/2})$ for the last $mp$ components. By the two
properties of $\bm{\Lambda}_{\delta}^{s}$ noted above, we therefore know that
$\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ is at most
$O_{p}(n_{L}^{-1/2})$ component-wise for any $s$. Hence
$\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})=\delta_{m,n_{L}}^{-1}O_{p}(n_{L}^{-1/2})=o_{p}(n_{L}^{-1/2})$
for sufficiently large $m,n_{L}$ by the properties of a geometric sum. This is
sufficient to show that the last $mp$ components of
$\sum_{s=1}^{\infty}\bm{\Lambda}^{s}\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$
are of smaller order component-wise than $\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$, so that the result for the prediction gap holds. In
particular, we thus know that $\hat{\bm{b}}-\dot{\bm{b}}=O_{p}(n_{L}^{-1/2})$.
Furthermore, we also know that the convergence rate of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ is at least of order
$O_{p}(n_{L}^{-1/2})$. As a result, we can choose
$\delta_{m,n_{L}}=n_{L}^{1/2}$ without affecting the component-wise order
properties of $\bm{\Lambda}_{\delta}$. Applying
$\delta_{m,n_{L}}=n_{L}^{1/2}$, we thus have that
$\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ is at most of order $O_{p}(n_{L}^{-1})$ component-wise.
This is smaller than $O_{p}(N^{-1/2})$ when $mn_{L}^{-1}\rightarrow 0$, and
the required result follows.

###  S3.2 Unconditional Regime

For the unconditional regime, we consider two cases: when
$mn_{L}^{-1}\rightarrow 0$, and when $mn_{U}^{-1}\rightarrow\infty$ but
$mn_{L}^{-2}\rightarrow 0$.

First, consider the case when $mn_{L}^{-1}\rightarrow 0$. From previous
derivations, we know that when $mn_{L}^{-1}\rightarrow 0$, the quantity
$\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ is of order $O_{p}(m^{-1/2})$ for the
first $p$ components and $O_{p}(m^{-1/2})$ for the last $mp$ components. By
the two properties of $\bm{\Lambda}_{\delta}^{s}$ noted above, we therefore
know that $\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ is
at most $O_{p}(m^{-1/2})$ component-wise for any $s$. Hence
$\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})=\delta_{m,n_{L}}^{-1}O_{p}(m^{-1/2})=o_{p}(m^{-1/2})$ for
sufficiently large $m,n_{L}$, by the properties of a geometric sum. The
required result follows from this. Furthermore, this implies we may set
$\delta_{m,n_{L}}=m^{1/2}$ without affecting the component-wise order
properties of $\bm{\Lambda}_{\delta}$. Applying $\delta_{m,n_{L}}=m^{1/2}$, we
thus have that
$\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ is at most of order $O_{p}(m^{-1})$ component-wise.

Next, consider the case when $mn_{U}^{-1}\rightarrow\infty$ and
$mn_{L}^{-2}\rightarrow 0$. From previous derivations, we know in this setting
it holds that $\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ is of order
$O_{p}(m^{-1/2})$ for the first $p$ components and $O_{p}(n_{L}^{-1/2})$ for
the last $mp$ components. By the two properties of $\bm{\Lambda}_{\delta}^{s}$
noted above, we therefore obtain that
$\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$ is at most
$O_{p}(n_{L}^{-1/2})$ component-wise for any $s$. Hence
$\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})=\delta_{m,n_{L}}^{-1}O_{p}(n_{L}^{-1/2})=o_{p}(n_{L}^{-1/2})$
for sufficiently large $m,n_{L}$, by the properties of a geometric sum. This
is sufficient to show that the last $mp$ components of
$\sum_{s=1}^{\infty}\bm{\Lambda}^{s}\bm{B}^{-1}\nabla Q(\dot{\bm{\theta}})$
are of smaller order component-wise than $\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$, so that the result for the prediction gap holds. In
particular, we thus know that $\hat{\bm{b}}-\dot{\bm{b}}=O_{p}(n_{L}^{-1/2})$.
Furthermore, we also know that the convergence rate of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ is at least $O_{p}(n_{L}^{-1/2})$. As a
result, we can set $\delta_{m,n_{L}}=n_{L}^{1/2}$ without affecting the
component-wise order properties of $\bm{\Lambda}_{\delta}$. Applying
$\delta_{m,n_{L}}=n_{L}^{1/2}$, we thus have that
$\sum_{s=1}^{\infty}\delta_{m,n_{L}}^{-s}\bm{\Lambda}_{\delta}^{s}\bm{B}^{-1}\nabla
Q(\dot{\bm{\theta}})$ is at most of order $O_{p}(n_{L}^{-1})$ component-wise.
This is smaller than $O_{p}(m^{-1/2})$ when $mn_{U}^{-1}\rightarrow\infty$,
$mn_{L}^{-2}\rightarrow 0$ and the result follows.

##  S4 Unpartnered Fixed Effects

###  S4.1 Generalised Linear Models

In the special case when $\dot{\bm{G}}=\bm{0}_{p\times p}$, i.e., all fixed
effects are unpartnered in the true data generating process, the GLMM reduces
to a GLM. We may then obtain a result based on a special case of our results
in the conditional case, when all the true random effects are equal to zero.
The result is as follows.

######  Corollary A1.

Assume Conditions (C1) - (C5) are satisfied and $mn_{L}^{-1}\rightarrow 0$.
Then as $m,n_{L}\rightarrow\infty$ and when the true vector of random effects
$\dot{\bm{b}}=\bm{0}_{mp}$, it holds that
$\bm{A}\bm{D}(\hat{\bm{\theta}}-\dot{\bm{\theta}})\overset{D}{\rightarrow}N(\bm{0},\bm{\Omega})$.

###  S4.2 Linear Mixed Models

Suppose for $i=1,\ldots,m$ and $j=1,\ldots,n_{i}$ we observe data from the
model
$y_{ij}=\bm{x}_{ij}^{\top}\bm{\beta}+\bm{z}_{ij}^{\top}\bm{b}_{i}+\bm{x}_{ij}^{(O)\top}\bm{\beta}^{(O)}+\epsilon_{ij}$,
where $\bm{x}_{ij}=\bm{z}_{ij}$ for all $(i,j)$,
$\bm{b}_{i}\overset{i.i.d.}{\sim}N(\bm{0},\hat{\bm{G}})$ and
$\epsilon_{ij}\overset{i.i.d.}{\sim}N(0,\phi)$. Note that this is part of the
exponential family. Partition
$\bm{\beta}=(\bm{\beta}^{(P)\top},\bm{\beta}^{(U)\top})^{\top}$, corresponding
to the $p_{P}$ partnered and $p_{U}$ unpartnered fixed effects
($p_{P}+p_{U}=p$). That is, if we partition
$\bm{b}_{i}=(\bm{b}_{i}^{(P)\top},\bm{b}^{(U)\top}_{i})^{\top}$, then
$\bm{b}^{(U)}_{i}=\bm{0}_{p_{U}}$ for all $i$, and the corresponding elements
in $\dot{\bm{G}}$ are zero. Let
$\bm{\theta}^{\times}=(\bm{\beta}^{\top},\bm{b}_{1}^{(P)\top},\ldots,\bm{b}_{m}^{(P)\top},\bm{b}^{(U)\top}_{1},\ldots,\bm{b}^{(U)\top}_{m},\bm{\beta}^{(O)\top})^{\top}$,
$\bm{\theta}^{-}=(\bm{\beta}^{\top},\bm{b}^{\top},\bm{\beta}^{(O)\top})^{\top}$,
$\bm{D}^{\times}=\text{diag}(m^{1/2}\bm{1}_{p_{P}},N^{1/2}\bm{1}_{p_{U}},m^{1/2}\bm{1}_{mp_{P}},n_{1}^{1/2}\bm{1}_{p_{U}},\ldots,n_{m}^{1/2}\bm{1}_{p_{U}},N^{1/2}\bm{1}_{p_{O}})$,
and
$\bm{D}^{-}=\text{diag}(m^{1/2}\bm{1}_{p_{P}},N^{1/2}\bm{1}_{p_{U}},n_{1}^{1/2}\bm{1}_{p},\ldots,n_{m}^{1/2}\bm{1}_{p},N^{1/2}\bm{1}_{p_{O}})$.
Also let
$\bm{X}_{i}^{(O)}=[\bm{x}_{i1}^{(O)},\ldots,\bm{x}_{in_{i}}^{(O)}]^{\top}$ and
$\bm{X}^{(O)}=[\bm{X}_{1}^{(O)\top},\ldots,\bm{X}_{m}^{(O)\top}]^{\top}$. The
$p_{O}$ orthogonal fixed effects $\bm{x}_{ij}^{(O)}$ satisfy
$\bm{X}^{(O)\top}\bm{Z}=\bm{0}_{p_{O}\times mp}$, for example orthogonal
polynomials of $\bm{x}_{ij}$. This implies
$\bm{X}_{i}^{(O)\top}\bm{X}_{i}=\bm{0}_{p_{O}\times p}$ for all $i$. For a
$q\times\\{(m+1)p+p_{O}\\}$ matrix $\bm{A}^{*}$ with the finite selection
property, we have the following.

######  Corollary A2.

Assume Conditions (C1) - (C4) are satisfied. Then as
$m,n_{L}\rightarrow\infty$ and unconditional on the random effects
$\dot{\bm{b}}$, it holds that

  1. 1.

$\bm{A}^{*}\bm{D}^{\times}(\hat{\bm{\theta}}^{\times}-\dot{\bm{\theta}}^{\times})\overset{D}{\rightarrow}N(\bm{0},\bm{\Omega}_{a})$
if $mn_{L}^{-1}\rightarrow 0$, and

  2. 2.

$\bm{A}^{*}\bm{D}^{-}(\hat{\bm{\theta}}^{-}-\dot{\bm{\theta}}^{-})\overset{D}{\rightarrow}N(\bm{0},\bm{\Omega}_{b})$
if $mn_{U}^{-1}\rightarrow\infty$,

where

$\displaystyle\bm{\Omega}_{a}$
$\displaystyle=\underset{m,n_{L}\rightarrow\infty}{\lim}\bm{A}^{*}\left[\begin{matrix}\dot{\bm{G}}_{[1:p_{P},1:p_{P}]}&\bm{0}_{p_{P}\times
p_{U}}&\bm{1}_{m}^{\top}\otimes\dot{\bm{G}}_{[1:p_{P},1:p_{P}]}&\bm{0}_{p_{P}\times
mp_{U}}&\bm{0}_{p_{P}\times p_{O}}\\\ \bm{0}_{p_{U}\times
p_{P}}&\bm{\Omega}_{1}&\bm{0}_{p_{U}\times mp_{P}}&\bm{0}_{p_{U}\times
mp_{U}}&\bm{0}_{p_{U}\times p_{O}}\\\
\bm{1}_{m}\otimes\dot{\bm{G}}_{[1:p_{P},1:p_{P}]}&\bm{0}_{mp_{P}\times
p_{U}}&\bm{1}_{m\times
m}\otimes\dot{\bm{G}}_{[1:p_{P},1:p_{P}]}&\bm{0}_{mp_{P}\times
mp_{U}}&\bm{0}_{mp_{P}\times p_{O}}\\\ \bm{0}_{mp_{U}\times
p_{P}}&\bm{0}_{mp_{U}\times p_{U}}&\bm{0}_{mp_{U}\times
mp_{P}}&\bm{\Omega}_{2}&\bm{0}_{mp_{U}\times p_{O}}\\\ \bm{0}_{p_{O}\times
p_{P}}&\bm{0}_{p_{O}\times p_{U}}&\bm{0}_{p_{O}\times
mp_{P}}&\bm{0}_{p_{O}\times mp_{U}}&\bm{\Omega}_{3}\\\
\end{matrix}\right]\bm{A}^{*\top}$ $\displaystyle\bm{\Omega}_{b}$
$\displaystyle=\underset{m,n_{L}\rightarrow\infty}{\lim}\bm{A}^{*}\left[\begin{matrix}\dot{\bm{G}}_{[1:p_{P},1:p_{P}]}&\bm{0}_{p_{P}\times
p_{U}}&\bm{0}_{p_{P}\times mp}&\bm{0}_{p_{P}\times p_{O}}\\\
\bm{0}_{p_{U}\times p_{P}}&\bm{\Omega}_{1}&\bm{0}_{p_{U}\times
mp}&\bm{0}_{p_{U}\times p_{O}}\\\ \bm{0}_{mp\times p_{P}}&\bm{0}_{mp\times
p_{U}}&\bm{\Omega}_{4}&\bm{0}_{mp\times p_{O}}\\\ \bm{0}_{p_{O}\times
p_{P}}&\bm{0}_{p_{O}\times p_{U}}&\bm{0}_{p_{O}\times mp}&\bm{\Omega}_{3}\\\
\end{matrix}\right]\bm{A}^{*\top}$ $\displaystyle\bm{\Omega}_{1}$
$\displaystyle=\left\\{\frac{\dot{\phi}}{m}\sum_{i=1}^{m}\frac{n}{n_{i}}\left(\frac{\bm{X}^{\top}_{i}\bm{X}_{i}}{n_{i}}\right)^{-1}\right\\}_{[(p-p_{U}+1):p,(p-p_{U}+1):p]}$
$\displaystyle\bm{\Omega}_{2}$
$\displaystyle=\text{bdiag}\left[\left\\{\dot{\phi}\left(\frac{\bm{X}^{\top}_{1}\bm{X}_{1}}{n_{1}}\right)^{-1}\right\\}_{[(p-p_{U}+1):p,(p-p_{U}+1):p]},\ldots,\left\\{\dot{\phi}\left(\frac{\bm{X}^{\top}_{m}\bm{X}_{m}}{n_{m}}\right)^{-1}\right\\}_{[(p-p_{U}+1):p,(p-p_{U}+1):p]}\right]$
$\displaystyle\bm{\Omega}_{3}$
$\displaystyle=\dot{\phi}\left(\frac{\bm{X}^{(O)\top}\bm{X}^{(O)}}{N}\right)^{-1}$
$\displaystyle\bm{\Omega}_{4}$
$\displaystyle=\text{bdiag}\left[\left\\{\dot{\phi}\left(\frac{\bm{X}^{\top}_{1}\bm{X}_{1}}{n_{1}}\right)^{-1}\right\\},\ldots,\left\\{\dot{\phi}\left(\frac{\bm{X}^{\top}_{m}\bm{X}_{m}}{n_{m}}\right)^{-1}\right\\}\right].$

###### Proof.

We use the same approach as previous proofs and examine the Taylor expansion
(S2.1). In this case, we have the expressions

$\displaystyle\nabla Q(\dot{\bm{\theta}})$
$\displaystyle=\left[\begin{matrix}\dot{\phi}^{-1}\bm{X}^{\top}(\bm{y}-\dot{\bm{\mu}})\\\
\dot{\phi}^{-1}\bm{Z}^{\top}(\bm{y}-\dot{\bm{\mu}})-(\bm{I}_{m}\otimes\hat{\bm{G}}^{-1})\dot{\bm{b}}\\\
\dot{\phi}^{-1}\bm{X}^{(O)\top}(\bm{y}-\dot{\bm{\mu}})\end{matrix}\right],$
$\displaystyle\bm{B}(\dot{\bm{\theta}})$
$\displaystyle=-\nabla^{2}Q(\dot{\bm{\theta}})=\left[\begin{matrix}\bm{X}^{\top}\dot{\bm{W}}\bm{X}&\bm{X}^{\top}\dot{\bm{W}}\bm{Z}&\bm{X}^{\top}\dot{\bm{W}}\bm{X}^{(O)}\\\
\bm{Z}^{\top}\dot{\bm{W}}\bm{X}&\bm{Z}^{\top}\dot{\bm{W}}\bm{Z}+\bm{I}_{m}\otimes\hat{\bm{G}}^{-1}&\bm{Z}^{\top}\dot{\bm{W}}\bm{X}^{(O)}\\\
\bm{X}^{(O)\top}\dot{\bm{W}}\bm{X}&\bm{X}^{(O)\top}\dot{\bm{W}}\bm{Z}&\bm{X}^{(O)\top}\dot{\bm{W}}\bm{X}^{(O)}\end{matrix}\right]$
$\displaystyle=\dot{\phi}^{-1}\left[\begin{matrix}\bm{X}^{\top}\bm{X}&\bm{X}^{\top}\bm{Z}&\bm{0}_{p\times
p_{O}}\\\
\bm{Z}^{\top}\bm{X}&\bm{Z}^{\top}\bm{Z}+\bm{I}_{m}\otimes\hat{\bm{G}}^{-1}&\bm{0}_{mp\times
p_{O}}\\\ \bm{0}_{p_{O}\times p}&\bm{0}_{p_{O}\times
mp}&\bm{X}^{(O)\top}\bm{X}^{(O)}\end{matrix}\right],$

where the last equality follows from the fact that
$\dot{\bm{W}}=\dot{\phi}^{-1}\bm{I}_{N}$ and
$\bm{X}^{(O)\top}\bm{Z}=\bm{0}_{p_{O}\times mp}$. Since
$\bm{B}(\dot{\bm{\theta}})$ is block diagonal, we thus know that expressions
(S2.9) and (S2.10) still hold. Recall

$\displaystyle\hat{\bm{\beta}}-\dot{\bm{\beta}}$
$\displaystyle=m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i})^{-1}\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})+m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}$
$\displaystyle-m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1}\dot{\bm{b}}_{i}+\frac{1}{2}\\{\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})\\}_{[1:p]}$
$\displaystyle+O_{p}(n_{L}^{-1})\Bigg{\\{}m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})+m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}$
$\displaystyle-m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i}+\hat{\bm{G}}^{-1})^{-1}\hat{\bm{G}}^{-1}\dot{\bm{b}}_{i}\Bigg{\\}}+m^{-1}\sum_{i=1}^{m}O_{p}(n_{L}^{-2})\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})$

and

$\displaystyle\hat{\bm{b}}-\dot{\bm{b}}$ $\displaystyle=-\bm{1}_{m}\otimes
m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}+\bm{B}_{3}^{-1}\\{\dot{\phi}^{-1}\bm{Z}^{\top}(\bm{y}-\dot{\bm{\mu}})\\}$
$\displaystyle+O_{p}(N^{-1/2})+O_{p}(n_{L}^{-1})+\frac{1}{2}\\{\bm{B}^{-1}\bm{R}(\tilde{\bm{\theta}})\\}_{[p+1:(m+1)p]}.$

In the LMM case, the remainder term in the Taylor expansion is zero. Thus the
dominating term on the right hand side for
$\hat{\bm{\beta}}^{(U)}-\dot{\bm{\beta}}^{(U)}$ are the last $p_{U}$
components of
$m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i})^{-1}\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})$,
since the last $p_{U}$ components of $m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}$
are zero. Noting that
$\bm{y}_{i}-\dot{\bm{\mu}}_{i}=(\epsilon_{i1},\ldots,\epsilon_{in_{i}})^{\top}=:\bm{\epsilon}_{i}$,
the result for the unpartnered fixed effects follows after normalising by
$N^{1/2}$.

Next, again from the Taylor expansion we have from the block-diagonal
structure of $\bm{B}(\dot{\bm{\theta}})$ that
$\hat{\bm{\beta}}^{(O)}-\dot{\bm{\beta}}^{(O)}=(\bm{X}^{(O)\top}\bm{X}^{(O)})^{-1}\bm{X}^{(O)\top}(\bm{y}-\dot{\bm{\mu}})$
and the result follows after normalising by $N^{1/2}$ since
$\bm{y}-\dot{\bm{\mu}}=(\epsilon_{11},\ldots,\epsilon_{mn_{m}})^{\top}=:\bm{\epsilon}$.

Finally, the result for the unpartnered random effects follows from the fact
that the last $p_{U}$ components of $m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}$ are
zero so that the dominating term on the right hand side is
$(\bm{X}_{i}^{\top}\bm{X}_{i})^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})$,
and normalising by $n_{i}$.

The proofs for the partnered fixed and random effects are analogous to the
proofs of Theorems 2 and 4, based on examining the leading term in the Taylor
expansion.

For the joint behaviour of the estimator, we examine the joint behaviour of
the leading terms in the Taylor Expansion. Note that $\bm{\epsilon}$ is
multivariate normal with covariance matrix $\dot{\phi}\bm{I}_{N}$,
$\dot{\bm{b}}$ is multivariate normal with covariance matrix
$\bm{I}_{m}\otimes\dot{\bm{G}}$, $\bm{\epsilon}$ and $\dot{\bm{b}}$ are
independent, and all the leading terms in the Taylor expansion are linear
functions of $\bm{\epsilon}$ and $\dot{\bm{b}}$. To determine the joint
behaviour of the estimator it is thus sufficient to derive the limiting
covariance between the normalised leading terms, as we see (from the leading
terms) that the estimator itself is also (asymptotically) multivariate normal.
For example,

$\displaystyle\text{Cov}\left\\{N^{1/2}m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\bm{X}_{i})^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i}),N^{1/2}(\bm{X}^{(O)\top}\bm{X}^{(O)})^{-1}\bm{X}^{(O)\top}(\bm{y}-\dot{\bm{\mu}})\right\\}$
$\displaystyle=n\dot{\phi}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\bm{X}_{i})^{-1}\bm{X}_{i}^{\top}\bm{X}^{(O)}_{i}(\bm{X}^{(O)\top}\bm{X}^{(O)})^{-1}$
$\displaystyle=\bm{0}_{p\times p_{O}}$

due to the mutual independence of the $\epsilon_{ij}$ and orthogonality
condition of $\bm{X}^{(O)}$. The pairwise limiting covariances between the
leading terms can all be derived in a similar way and the result follows.
Notice here that quantities with different convergence rates are always
asymptotically uncorrelated and independent in this case.

∎

Note that the results hold by the Lindeberg-Feller Central Limit Theorem even
if the true distribution of $\epsilon_{ij}$ is not normal, as long as it is
mean zero with finite variance. Also note that condition (C5) is no longer
required, and that there is no restriction on the relative rates of $m$ and
$n_{L}$, since there is no remainder term to deal with. Our result is
consistent with the results derived in [50, 51] who also derive a $N^{1/2}$
convergence rate for unpartnered fixed effects that are time-varying.

In practice, we do not know if a fixed effect is truly partnered with a random
effect or not, and therefore the correct asymptotic distribution and
convergence rate is also unknown. In this case, an appropriate finite sample
approximation, given consistent estimators $\tilde{\bm{G}}$ and $\tilde{\phi}$
of $\dot{\bm{G}}$ and $\dot{\phi}$ respectively, is

$\displaystyle\hat{\bm{\beta}}-\dot{\bm{\beta}}\sim
N\left\\{\bm{0},m^{-1}\tilde{\bm{G}}+N^{-1}\frac{\tilde{\phi}}{m}\sum_{i=1}^{m}\frac{n}{n_{i}}\left(\frac{\bm{X}^{\top}_{i}\bm{X}_{i}}{n_{i}}\right)^{-1}\right\\},$

which is based on the distribution of
$m^{-1}\sum_{i=1}^{m}(\bm{X}_{i}^{\top}\dot{\bm{W}}_{i}\bm{X}_{i})^{-1}\dot{\phi}^{-1}\bm{X}_{i}^{\top}(\bm{y}_{i}-\dot{\bm{\mu}}_{i})+m^{-1}\sum_{i=1}^{m}\dot{\bm{b}}_{i}$,
noting that the two terms are independent.

##  S5 Additional Simulation Results

###  S5.1 Main Results for the Conditional Regime

Figures 4, 5 and 6 display the empirical coverage probabilities and results
from applying the Shapiro-Wilk test, respectively, under the conditional
regime and for the 25 combinations of $(m,n)$. Although our coverage intervals
often undercovered or overcovered for small cluster sizes e.g., $n=25$,
especially for the Bernoulli case, they all moved toward nominal coverage as
$n$ becomes larger than $m$. This is consistent with Theorem 1. The fact the
empirical coverage probabilities were slow in tending towards the nominal 95%
level was also not overly surprising, as the third derivative term in the
corresponding Taylor expansion is $O_{p}(m^{1/2}n_{L}^{-1/2})$. The Shapiro-
Wilk tests overall did not indicate any evidence of deviations away from
normality when $m<n$, although there were occasionally a few $p$-values less
than 0.05. Overall, these results strongly support the use of Theorem 1 for
inference under the conditional regime.

Figure 4: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the conditional regime
with Poisson responses. Figure 5: Empirical coverage probability of 95%
coverage intervals for the five fixed and random effects estimates, obtained
under the conditional regime with Bernoulli responses.

Figure 6: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the conditional
regime.

Figure 7: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the conditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother.

###  S5.2 Frobenius Norm

Table 1: Empirical mean Frobenius norm of the difference between estimated and
true random effects covariance matrix.

| Poisson | Bernoulli |
---|---|---|---
| $m$ | $n=25$ | $n=50$ | $n=100$ | $n=200$ | $n=400$ |  | $n=25$ | $n=50$ | $n=100$ | $n=200$ | $n=400$
$\hat{\bm{G}}=m^{-1}\sum_{i=1}^{m}\hat{\bm{b}}_{i}$ | $25$ | 1.06 | 1.06 | 1.06 | 1.05 | 1.06 |  | 1.76 | 1.47 | 1.24 | 1.12 | 1.09
$50$ | 0.77 | 0.75 | 0.75 | 0.76 | 0.75 |  | 1.79 | 1.40 | 1.03 | 0.83 | 0.77
$100$ | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 |  | 1.80 | 1.38 | 0.89 | 0.63 | 0.56
$200$ | 0.39 | 0.38 | 0.38 | 0.38 | 0.38 |  | 1.80 | 1.35 | 0.82 | 0.51 | 0.41
$400$ | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 |  | 1.81 | 1.35 | 0.78 | 0.43 | 0.32
$\hat{\bm{G}}=0.25\bm{I}_{2}$ | $25$ | 1.02 | 1.01 | 1.03 | 1.05 | 1.04 |  | 1.90 | 1.71 | 1.47 | 1.23 | 1.04
$50$ | 0.73 | 0.73 | 0.74 | 0.74 | 0.76 |  | 1.90 | 1.70 | 1.44 | 1.15 | 0.91
$100$ | 0.56 | 0.53 | 0.52 | 0.53 | 0.54 |  | 1.90 | 1.69 | 1.42 | 1.11 | 0.84
$200$ | 0.44 | 0.39 | 0.37 | 0.38 | 0.38 |  | 1.90 | 1.68 | 1.41 | 1.09 | 0.79
$400$ | 0.38 | 0.29 | 0.27 | 0.27 | 0.27 |  | 1.89 | 1.68 | 1.40 | 1.08 | 0.77
$\hat{\bm{G}}=0.5\bm{I}_{2}$ | $25$ | 1.02 | 1.03 | 1.04 | 1.05 | 1.05 |  | 1.61 | 1.39 | 1.16 | 1.01 | 0.96
$50$ | 0.74 | 0.75 | 0.75 | 0.75 | 0.74 |  | 1.61 | 1.34 | 1.07 | 0.86 | 0.75
$100$ | 0.53 | 0.52 | 0.54 | 0.54 | 0.54 |  | 1.60 | 1.32 | 1.03 | 0.77 | 0.61
$200$ | 0.39 | 0.38 | 0.38 | 0.38 | 0.38 |  | 1.59 | 1.31 | 1.01 | 0.73 | 0.52
$400$ | 0.30 | 0.27 | 0.27 | 0.27 | 0.27 |  | 1.59 | 1.30 | 0.99 | 0.70 | 0.47
$\hat{\bm{G}}=\bm{I}_{2}$ | $25$ | 1.06 | 1.05 | 1.04 | 1.04 | 1.06 |  | 1.21 | 1.06 | 0.98 | 0.97 | 1.00
$50$ | 0.74 | 0.75 | 0.75 | 0.75 | 0.76 |  | 1.17 | 0.93 | 0.78 | 0.73 | 0.71
$100$ | 0.53 | 0.53 | 0.54 | 0.53 | 0.54 |  | 1.13 | 0.86 | 0.65 | 0.56 | 0.53
$200$ | 0.38 | 0.38 | 0.38 | 0.38 | 0.38 |  | 1.12 | 0.82 | 0.58 | 0.44 | 0.39
$400$ | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 |  | 1.10 | 0.80 | 0.55 | 0.38 | 0.30
$\hat{\bm{G}}=2\bm{I}_{2}$ | $25$ | 1.06 | 1.06 | 1.06 | 1.05 | 1.06 |  | 0.84 | 0.98 | 1.03 | 1.04 | 1.05
$50$ | 0.75 | 0.74 | 0.75 | 0.76 | 0.75 |  | 0.71 | 0.71 | 0.74 | 0.74 | 0.75
$100$ | 0.54 | 0.54 | 0.54 | 0.53 | 0.53 |  | 0.56 | 0.51 | 0.53 | 0.53 | 0.54
$200$ | 0.38 | 0.38 | 0.38 | 0.38 | 0.38 |  | 0.47 | 0.38 | 0.37 | 0.38 | 0.38
$400$ | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 |  | 0.42 | 0.29 | 0.27 | 0.27 | 0.27
$\hat{\bm{G}}=4\bm{I}_{2}$ | $25$ | 1.06 | 1.06 | 1.06 | 1.06 | 1.06 |  | 1.33 | 1.42 | 1.25 | 1.16 | 1.11
$50$ | 0.77 | 0.76 | 0.76 | 0.75 | 0.76 |  | 1.18 | 1.07 | 0.93 | 0.83 | 0.80
$100$ | 0.55 | 0.54 | 0.54 | 0.54 | 0.54 |  | 0.97 | 0.86 | 0.70 | 0.61 | 0.57
$200$ | 0.39 | 0.38 | 0.38 | 0.38 | 0.38 |  | 0.86 | 0.72 | 0.55 | 0.45 | 0.41
$400$ | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 |  | 0.80 | 0.65 | 0.46 | 0.34 | 0.30

###  S5.3 ${G}$ = 0.25 ${I}_{2}$

Using a large $\hat{\bm{G}}$ of $4\bm{I}_{2}$ had the least impact on the
results, while a small $\hat{\bm{G}}$, e.g., $0.25\bm{I}_{2}$ had more of a
noticeable impact at small sample sizes. This is not surprising since the
latter corresponds to more shrinkage, such that larger sample sizes are needed
before asymptotic results apply.

Figure 8: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the unconditional
regime with Poisson responses. Figure 9: Empirical coverage probability of 95%
coverage intervals for the five fixed and random effects estimates, obtained
under the unconditional regime with Bernoulli responses.

Figure 10: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the
unconditional regime.

Figure 11: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother. Figure 12: Empirical coverage
probability of 95% coverage intervals for the five fixed and random effects
estimates, obtained under the conditional regime with Poisson responses.
Figure 13: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the conditional regime
with Bernoulli responses.

Figure 14: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the conditional
regime.

Figure 15: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother.

###  S5.4 ${G}$ = 0.50 ${I}_{2}$

Figure 16: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the unconditional
regime with Poisson responses. Figure 17: Empirical coverage probability of
95% coverage intervals for the five fixed and random effects estimates,
obtained under the unconditional regime with Bernoulli responses.

Figure 18: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the
unconditional regime.

Figure 19: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother. Figure 20: Empirical coverage
probability of 95% coverage intervals for the five fixed and random effects
estimates, obtained under the conditional regime with Poisson responses.
Figure 21: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the conditional regime
with Bernoulli responses.

Figure 22: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the conditional
regime.

Figure 23: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother.

###  S5.5 ${G}$ = ${I}_{2}$

Figure 24: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the unconditional
regime with Poisson responses. Figure 25: Empirical coverage probability of
95% coverage intervals for the five fixed and random effects estimates,
obtained under the unconditional regime with Bernoulli responses.

Figure 26: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the
unconditional regime.

Figure 27: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother. Figure 28: Empirical coverage
probability of 95% coverage intervals for the five fixed and random effects
estimates, obtained under the conditional regime with Poisson responses.
Figure 29: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the conditional regime
with Bernoulli responses.

Figure 30: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the conditional
regime.

Figure 31: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother.

###  S5.6 ${G}$ = 2 ${I}_{2}$

Figure 32: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the unconditional
regime with Poisson responses. Figure 33: Empirical coverage probability of
95% coverage intervals for the five fixed and random effects estimates,
obtained under the unconditional regime with Bernoulli responses.

Figure 34: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the
unconditional regime.

Figure 35: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother. Figure 36: Empirical coverage
probability of 95% coverage intervals for the five fixed and random effects
estimates, obtained under the conditional regime with Poisson responses.
Figure 37: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the conditional regime
with Bernoulli responses.

Figure 38: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the conditional
regime.

Figure 39: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother.

###  S5.7 ${G}$ = 4 ${I}_{2}$

Figure 40: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the unconditional
regime with Poisson responses. Figure 41: Empirical coverage probability of
95% coverage intervals for the five fixed and random effects estimates,
obtained under the unconditional regime with Bernoulli responses.

Figure 42: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the
unconditional regime.

Figure 43: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother. Figure 44: Empirical coverage
probability of 95% coverage intervals for the five fixed and random effects
estimates, obtained under the conditional regime with Poisson responses.
Figure 45: Empirical coverage probability of 95% coverage intervals for the
five fixed and random effects estimates, obtained under the conditional regime
with Bernoulli responses.

Figure 46: $p$-values from Shapiro-Wilk tests applied to the fixed and random
effects estimates obtained using maximum PQL estimation, under the conditional
regime.

Figure 47: Histograms for the third components of
$\hat{\bm{\beta}}-\dot{\bm{\beta}}$ (left panels) and
$\hat{\bm{b}}_{1}-\dot{\bm{b}}_{1}$ (right panels), under the unconditional
regime. Vertical facets represent the cluster sizes, while horizontal facets
represent the number of clusters. The dotted blue line indicates zero, and the
red curve is a kernel density smoother.


# Derivation of the generalized Zurek’s bound from a detailed fluctuation
theorem

Jihai Zhu  School of Physics, Peking University, Beijing 100871, China

###### Abstract

The minimal heat that must be released to the reservoir when a single input
$x$ is mapped to a single output $y$ is considered. It was previously argued
by Zurek in an informal style that the minimal heat should be $K(x|y)$.
Recently, Kolchinsky has rigorously proved a generalized Zurek’s bound in the
Hamiltonian "two-point measurement" scheme, which implies a trade-off between
heat, noise and protocol complexity in a computation from $x$ to $y$. Here we
propose another proof of the generalized Zurek’s bound from a detailed
fluctuation theorem, showing that the generalized Zurek’s bound holds in any
system that satisfies a DFT. Several applications of the bound are also
discussed.

##  I Introduction

It is noticed that there is a fundamental relationship between thermodynamics
and information since the birth of Maxwell’s
demonbennettDemonsEnginesSecond1987a . Today, when talking about this
relationship, people often refer to Landauer’s principle, which says that when
some amount of information of the system is erased, a corresponding amount of
heat must be released to the
reservoirbennettThermodynamicsComputationReview1982 :

$\frac{\beta}{\ln{2}}\langle Q\rangle\geq S(p_{X})-S(p_{Y}),$ (1)

where $p_{X}$ is the input ensemble, $p_{Y}$ is the output ensemble,
$S(p)=-\sum_{i}p_{i}\log p_{i}$ is the Shannon entropy in bits, $\beta$ is the
inverse temperature of the heat reservoir, and $\langle Q\rangle$ is the
average amount of heat released to the heat reservoir during the process. For
the simplicity of notations, hereafter we set $\frac{\beta}{\ln{2}}\equiv 1$.
Thus Landauer’s principle can be written as:

$\langle Q\rangle\geq S(p_{X})-S(p_{Y}).$ (2)

It should be noted that what Landauer’s principle considers is not a map from
a single input $x$ to a single output $y$, but a map from an input ensemble
$p_{X}$ to an output ensemble $p_{Y}$. It is thus natural to ask whether there
exists a lower bound of cost of mapping a single input $x$ to a single output
$y$.

As the first attempt in answering the question,
ZurekzurekAlgorithmicRandomnessPhysical1989  proposed that the minimal cost
was given by the Kolmogorov relative complexity $K(x|y)$. In spite of its
simplicity, this bound is incomplete, because we can argue by intuition that
this minimal cost must depend on the specific protocol $\mathcal{P}$ that
accomplishes the mapping: for example, one can easily imagine a protocol that
deterministically maps a particular binary sequence of 1GB zeros-and-ones into
1GB zeros without any heat release. Therefore, the proper question should be:

Given a protocol $\mathcal{P}$ which accomplishes a (stochastic) mapping on a
state space $\mathcal{X}$, is there a minimal amount of heat that must be
released to the reservoir when a single input $x\in\mathcal{X}$ is mapped to a
single output $y\in\mathcal{X}$?

As an answer to the above question,
KolchinskykolchinskyGeneralizedZurekBound2023  has recently derived a so-
called "generalized Zurek’s bound", that is:

$Q(x\to y)\overset{+}{\geq}K(x|y,\mathcal{P})-\log\frac{1}{P(y|x)},$ (3)

where $\mathcal{P}$ is the protocol, $Q(x\to y)$ is average heat released to
the reservoir during a mapping from $x$ to $y$, and $P(y|x)$ is the
probability of receiving $y$ as the output when $x$ is the input of the
protocol $\mathcal{P}$(Fig.1). We write a $+$ or $\times$ sign on top of an
(in)equality sign to mean that the (in)equality holds to a constant additive
or multiplicative term. In Appendix A we show that this constant term is
actually negligible in practice. Kolchinsky’s derivation of (3) is rigorous,
and is based on the Hamiltonian "two-point measurement" scheme.

In this paper, we further generalize Kolchinsky’s result to any system that
satisfies a detailed fluctuation theorem(DFT), as the "two-point measurement"
scheme satisfies DFT while not all quantum processes featured with DFT can be
represented in the "two-point measurement"
schememicadeiQuantumFluctuationTheorems2020 . We first lay out some notations
and techniques of algorithmic information theory(AIT) and stochastic
thermodynamics that are used in this paper. After that, we derive the bound
(3) with the assumption that the system satisfies DFT. At last, we discuss two
applications of the bound.

Figure 1: A system coupled with a heat reservoir evolves from state $x$ to
state $y$ under a driving protocol. The system may travel through different
trajectories in different attempts. Each trajectroy is endowed with a specific
amount of heat released to the reservoir. $Q$ is the average amount of heat
release over all trajectories from $x$ to $y$.

##  II Preliminaries

###  II.1 Algorithmic information theory

We briefly sketch the notations and results of algorithmic information
theory(AIT) that are used in this paper. For a more complete introduction,
readers can refer to liKolmogorovComplexityIts1990 ,
caludeInformationRandomnessAlgorithmic2002  and
grunwaldShannonInformationKolmogorov2004 .

AIT is a theory on the "complexity" of objects (sequences, numbers, functions,
etc.). By the term "complexity" of an object $x$, or $K(x)$ as is the usual
notation, we mean the minimal resource required to "describe" $x$, which is
often pinned down as (the length of) the shortest program $p$, when set as
input for a (prefix-free) universal Turing machine $U$, generates $x$ as the
output, that is:

$K(x)\equiv\min\\{l(p):U(p)=x\\}.$ (4)

As can be seen from above, $K(x)$ is dependent on the artificially chosen
universal Turing machine $U$. However, this subjectivity can be saved by
noticing that there exists an interpreter program $int(U,U^{\prime})$ between
any two universal Turing machines $U$ and $U^{\prime}$, thus any program on
$U^{\prime}$ can be run on $U$ by adding $int(U,U^{\prime})$ before the
program. To be specific:

$K_{U}(x)-K_{U^{\prime}}(x)\leq l(int(U,U^{\prime})),$ (5)

and vice versa, so that

$K_{U}(x)\overset{+}{=}K_{U^{\prime}}(x),$ (6)

and there’s nothing lost in writing $K(x)$ instead of $K_{U}(x)$.

The Kolmogorov relative complexity $K(x|y)$ is similarly defined as (the
length of) the shortest program $p$, when set as input for a (prefix-free)
universal Turing machine $U$ coupled with a parameter tape writing $y$, which
can be checked any time during the computation, generates $x$ as the output.
To be specific:

$K(x|y)\equiv\min\\{l(p):U(p,y)=x\\}.$ (7)

The following statements of Kolmogorov complexity hold:

  1. 1.

For every $x$, $y$ and $z$,

$K(x|z)\overset{+}{\leq}K(x,y|z)\overset{+}{\leq}K(x|y,z)+K(y|z).$ (8)

  2. 2.

Given a set $A$ with $|A|$ elements, for most $x\in A$,
$K(x|A)\overset{+}{=}\log|A|$.

  3. 3.

For every (computable) probability measure $P(x)$ (that is, $\sum_{x}p(x)=1$),
$S_{sh}(P)\overset{+}{=}\sum_{x}P(x)K(x|P)$, where $S_{sh}(P)$ is the Shannon
entropy of $P$.

  4. 4.

For every (computable) relative probability semimeasure $P(x|y)$ (that is,
$\sum_{x}P(x|y)\leq 1$ for every $y$), the coding theorem implies the
inequality that

$K(x|y,P)\overset{+}{\leq}\log\frac{1}{P(x|y)}.$ (9)

###  II.2 Stochastic thermodynamics

Stochastic thermodynamics is an emergent field that uses stochastic equations
to study mesoscopic, nonequilibrium systems. Here we summary the notations and
definitions used in this paper. More succinct introductions can be found in
seifertStochasticThermodynamicsPrinciples2018  and
shiraishiIntroductionStochasticThermodynamics2023 .

We consider a system with state space $\mathcal{X}$ coupled to a heat
reservoir at reverse temperature $\beta$. There may be manipulations and/or
drivings acting on the system. We assume the system undergoes a time-
inhomogeneous Markov chain, and the jump rate from state $x$ to state
$x^{\prime}$ at time $t$ is $k_{x^{\prime}x}(\lambda(t))$, where $\lambda(t)$
is the manipulation protocol acting on the system. As time passes from $t_{0}$
to $t_{n+1}$, the system may experience $n$ times of jumps from $x_{i}$ to
$x_{i+1}$ at time $t_{i}(i=1,2,\cdots,n)$ and travel a trajectory $x(t)$:

$x(t)=x_{i}\quad\mbox{for}\quad t_{i}\leq t\leq t_{i+1}.$ (10)

Since the stochasticity of the system comes from its coupling with the heat
reservoir, every time a jump occurs, there is heat released from the system to
the reservoir. As is customary
shiraishiIntroductionStochasticThermodynamics2023 , the heat released to the
reservoir during a jump from $x$ to $x^{\prime}$ is assigned to be:

$q_{x^{\prime}x}\equiv\log\frac{k_{x^{\prime}x}}{k_{xx^{\prime}}},$ (11)

and the total heat released during a trajectory $x(t)$ is:

$q(\bm{x})=\sum_{i=1}^{n}\log\frac{k_{x_{i}x_{i-1}}(t_{i})}{k_{x_{i-1}x_{i}}(t_{i})},$
(12)

On the other hand, the probability density $P_{\bm{x}}(\bm{\lambda})$ for a
trajectory $\bm{x}$ to occur with the forward protocol $\bm{\lambda}$ can be
expressed as:

$P_{\bm{x}}(\bm{\lambda})=p_{x_{0}}(t_{0})P_{\bm{x}|x_{0}}(\bm{\lambda}),$
(13)

where $p_{x_{0}}(t_{0})$ is the probability of the system being in state
$x_{0}$ at the beginning of the trajectory, and
$P_{\bm{x}|x_{0}}(\bm{\lambda})$ is the relative probability density, which is
given by:

$P_{\bm{x}|x_{0}}(\bm{\lambda})=\prod_{i=1}^{n}k_{x_{i}x_{i-1}}(t_{i})2^{-\sum_{i=1}^{n}\int_{t_{i-1}}^{t_{i}}e_{x_{i-1}}(t)\differential
t},$ (14)

where $e_{x}\equiv\sum_{x^{\prime}\neq x}k_{x^{\prime}x}$ is the escape rate
of state $x$.

We now consider the time-reverse process, or backward process, where both the
trajectory and the protocol evolves in reverse order in time. The concept of
backward process is critical in the derivation of various fluctuation
theorems. We define $\tilde{t}\equiv t_{n+1}-(t-t_{0})$, $\tilde{x}(t)\equiv
x(\tilde{t})$, $\tilde{\lambda}(t)\equiv\lambda(\tilde{t})$, and refer to
$P_{\tilde{\bm{x}}|x_{n}}(\tilde{\bm{\lambda}})$ as the relative probability
density of the backward trajectory.

Surprisingly, the ratio of $P_{\bm{x}|x_{0}}(\bm{\lambda})$ with
$P_{\tilde{\bm{x}}|x_{n}}(\tilde{\bm{\lambda}})$ can be represented by the
heat $q(\bm{x})$ released during the forward process $\bm{x}$ as in equation
(12):

$\frac{P_{\bm{x}|x_{0}}(\bm{\lambda})}{P_{\tilde{\bm{x}}|x_{n}}(\tilde{\bm{\lambda}})}=2^{q(\bm{x})}.$
(15)

The above equation is the so-called detailed fluctuation theorem(DFT).

##  III Derivation of the bound

In this section, we shall derive the generalized Zurek’s bound, with the
assumption that the system satisfies DFT.

First, let’s rewrite inequality (3) which we are going to prove:

$K(x|y,\mathcal{P})\overset{+}{\leq}\log\frac{1}{P(y|x)}+Q(x\to y),$ (16)

where $P(y|x)$ and $Q(x\to y)$ can be further expressed as:

$P(y|x)=\sum_{\bm{x}:x_{f}=y}P_{\bm{x}|x}(\bm{\lambda}),$ (17) $Q(x\to
y)=\frac{1}{P(y|x)}\sum_{\bm{x}:x_{f}=y}P_{\bm{x}|x}(\bm{\lambda})q(\bm{x}),$
(18)

where $x_{f}$ is the final state of the trajectory $\bm{x}$.

Since $P(\cdot|\cdot)$ and $Q(\cdot\to\cdot)$ can be computed from
$\mathcal{P}$, to prove inequality (16), we only have to prove that the right-
hand-side can be written as a negative logarithm of a semimeasure of $x$ given
$y$ (the coding theorem), that is:

$\sum_{x}2^{-(\log\frac{1}{P(y|x)}+Q(x\to y))}=\sum_{x}P(y|x)2^{-Q(x\to y)}\\\
\leq\sum_{x}P(y|x)\frac{1}{P(y|x)}\sum_{\bm{x}:x_{f}=y}P_{\bm{x}|x}(\bm{\lambda})2^{-q(\bm{x})}\\\
=\sum_{x}\sum_{\bm{x}:x_{f}=y}P_{\bm{x}|x}(\bm{\lambda})2^{-q(\bm{x})}=\sum_{x}\sum_{\bm{x}:x_{f}=y}P_{\bm{x}|x}(\bm{\lambda})\frac{P_{\tilde{\bm{x}}|y}(\tilde{\bm{\lambda}})}{P_{\bm{x}|x}(\bm{\lambda})}\\\
=\sum_{x}\sum_{\tilde{\bm{x}}:\tilde{x_{f}}=x}P_{\tilde{\bm{x}}|y}(\tilde{\bm{\lambda}})=1,$
(19)

where the first inequality comes from equation (18) and Jensen’s inequality
and the third equality comes from the assumption of detailed fluctuation (15).
Thus inequality (16) is proved.

Considering the inequality
$K(x|y,\mathcal{P})\overset{+}{\leq}K(x|y)-K(\mathcal{P})$ as deduced from
(8), we can write a weaker bound as:

$Q(x\to y)+\log\frac{1}{P(y|x)}+K(\mathcal{P})\overset{+}{\geq}K(x|y).$ (20)

As noted by KolchinskykolchinskyGeneralizedZurekBound2023 , the above
inequality tells a trade-off between heat, noise and protocol complexity that
has to be paid for the erased information in a computation from $x$ to $y$.

##  IV Applications

In this section, we discuss two applications of the generalized Zurek’s bound
we just proved.

###  IV.1 Cost of erasure of an input sequence

Imagine $x$ is a binary sequence of length $n$ ($n$ may be large) and we want
to set all the digits of $x$ to zero (to erase the sequence). If $x$ is a very
random sequence, then $K(x|\mathcal{P})\approx n$. Since
$K(0^{n}|\mathcal{P})\approx\log n\ll n$, the minimal heat release we have to
pay for the erasure is approximately $n-\log\frac{1}{P(0^{n}|x)}$, so that if
we hope to perform the erasure in a relatively high success rate, we have to
pay for a cost proportional to the length of the sequence to be erased, which
is consistent with the prediction given by Landauer’s principle.

However, if $x$ consists some kind of internal regularity, even if are unaware
of that regularity and keep $\mathcal{P}$ unchanged, $K(x|\mathcal{P})$ can
still be much smaller and less heat may be released in the erasure. For
example, if all the bits on odd positions in $x$ are $1$, that is, $x$ is of
the form $x_{0}1x_{2}1\cdots x_{n-2}1$, then $K(x|\mathcal{P})\approx n/2$, so
that the minimal heat release to perform an erasure is reduced to a half in
virtue of this regularity, which is a result cannot be concluded form
Landauer’s principle.

###  IV.2 Condition for heat functions of nondeterministic Turing machines

In this part, we generalize previous results on the thermodynamic properties
of Turing machineskolchinskyThermodynamicCostsTuring2020  to nondeterministic
Turing machines.

A physical Turing machine is a protocol $\mathcal{P}$ that mimics the input-
output relation $P:\mathcal{X}\to\mathcal{X}$ of a mathematical Turing
machine. $\mathcal{P}$ is called a realization of $P$. A Turing machine is
called (non)deterministic if $P$ is (non)deterministic.

Here (as in kolchinskyThermodynamicCostsTuring2020 ), we consider only the
thermodynamic properties of physical Turing machines. Suppose a physical
Turing machine $\mathcal{P}$ is coupled with a heat reservoir. When
$\mathcal{P}$ is given an input $x$, an average amount of heat $Q(x)$ is
released to the reservoir, that is:

$Q(x)\equiv\sum_{y}P(y|x)Q(x\to y).$ (21)

$Q(x)$ is called the heat function of $\mathcal{P}$.

It is proved in kolchinskyThermodynamicCostsTuring2020  that, when $P$ is
deterministic, the heat function $Q(x)$ is realizable iff for every
$y\in\mathcal{X}$, there is:

$\sum_{x:P(x)=y}2^{-Q(x)}\leq 1.$ (22)

Considering the form of the sum after the first equality in formula (19), we
can easily generalize inequality (22) to any nondeterministic function $P$,
and the heat function $Q(x\to y)$ is realizable iff for every
$y\in\mathcal{X}$, there is:

$\sum_{x}P(y|x)2^{-Q(x\to y)}\leq 1.$ (23)

A dominating realization of $P$ is a realization $\mathcal{P}_{dom}$ whose
heat function $Q_{dom}(x)$ is less than the heat function $Q(x)$ of any other
realization of $P$ up to a constant additive term which may depend on
$Q(\cdot)$. It is shown in kolchinskyThermodynamicCostsTuring2020  that for
any realization of any deterministic $P$, the heat function $Q(x)$ obeys:

$Q(x)\overset{+}{\geq}K(x|P(x))-K(Q,P).$ (24)

Thus we can assign $Q_{dom}(x)=K(x|P(x))$ as the dominating heat function of
$P$.

We can easily generalize inequality (24) to any nondeterministic function $P$,
since inequality (24) is actually a deterministic restriction of the
generalized Zurek’s bound (3). After rearrangement and note that
$\mathcal{P}=(P,Q)$, we have:

$Q(x\to y)\overset{+}{\geq}K(x|y,Q,P)-\log\frac{1}{P(y|x)}\\\
\overset{+}{\geq}K(x|y)-\log\frac{1}{P(y|x)}-K(Q,P),$ (25)

and the dominating heat function can be assigned as $Q_{dom}(x\to
y)=K(x|y)-\log\frac{1}{P(y|x)}.$

##  V Future work

In this paper, we have studied the applications of Kolmogorov complexity in
stochastic thermodynamics, especially the relationship between Kolmogorov
complexity and fluctuation theorems. In Appendix B we will introduce an
algorithmic definition of stochastic entropy that satisfies the integral
fluctuation theorem.

So far, there are still many interesting problems at the intersection of AIT
and thermodynamics but cannot be solved in our paradigm. For example, consider
a process that realizes a computation of a very hard problem $f$ (such as 3SAT
problem) but not erase the input, that is: $P(x)=(x,f(x))$ for a relatively
high success rate. Since $f$ is very hard to compute), it is reasonable that
this process should cost a lot(time, energy, etc.), but according to bound
(3), $K(x,f(x)|x)\approx 0$ so no lower bound of the cost of this process can
be acquired.

To solve the above problem, it may be helpful to consider resource-bounded
Kolmogorov complexity, or to restrict our consideration to protocols that can
be constructed from a limited set of subprograms (such as in
wolpertStochasticThermodynamicsComputation2019  and
wolpertThermodynamicsComputingCircuits2020 ). It would yield insightful
results by applying the concepts and techniques of the well-established domain
of computational complexity theory into the emergent field of stochastic
thermodynamics.

## References

  * (1) C. H. Bennett, “Demons, engines and the second law,” _Sci Am_ , vol. 257, no. 5, pp. 108–116, Nov. 1987.
  * (2) ——, “The thermodynamics of computation—a review,” _Int J Theor Phys_ , vol. 21, no. 12, pp. 905–940, Dec. 1982.
  * (3) W. H. Zurek, “Algorithmic randomness and physical entropy,” _Phys. Rev. A_ , vol. 40, no. 8, pp. 4731–4751, Oct. 1989.
  * (4) A. Kolchinsky, “Generalized zurek’s bound on the cost of an individual classical or quantum computation,” _Phys. Rev. E_ , vol. 108, no. 3, p. 034101, Sep. 2023.
  * (5) K. Micadei, G. T. Landi, and E. Lutz, “Quantum fluctuation theorems beyond two-point measurements,” _Phys. Rev. Lett._ , vol. 124, no. 9, p. 090602, Mar. 2020.
  * (6) M. Li and P. M. Vitányi, “Kolmogorov complexity and its applications,” in _Algorithms and Complexity_. Elsevier, 1990, pp. 187–254.
  * (7) C. Calude, _Information and Randomness: An Algorithmic Perspective_ , 2nd ed., ser. Texts in Theoretical Computer Science. Berlin ; New York: Springer, 2002.
  * (8) P. Grunwald and P. Vitanyi, “Shannon information and kolmogorov complexity,” Oct. 2004.
  * (9) U. Seifert, “Stochastic thermodynamics: From principles to the cost of precision,” _Physica A: Statistical Mechanics and its Applications_ , vol. 504, pp. 176–191, Aug. 2018.
  * (10) N. Shiraishi, _An Introduction to Stochastic Thermodynamics: From Basic to Advanced_ , ser. Fundamental Theories of Physics. Singapore: Springer Nature Singapore, 2023, vol. 212.
  * (11) A. Kolchinsky and D. H. Wolpert, “Thermodynamic costs of turing machines,” _Phys. Rev. Research_ , vol. 2, no. 3, p. 033312, Aug. 2020.
  * (12) D. H. Wolpert, “Stochastic thermodynamics of computation,” _J. Phys. A: Math. Theor._ , vol. 52, no. 19, p. 193001, May 2019.
  * (13) D. H. Wolpert and A. Kolchinsky, “Thermodynamics of computing with circuits,” _New J. Phys._ , vol. 22, no. 6, p. 063047, Jun. 2020.
  * (14) D. Woods and T. Neary, “The complexity of small universal turing machines: A survey,” _Theoretical Computer Science_ , vol. 410, no. 4-5, pp. 443–450, Feb. 2009.
  * (15) P. Gacs, “The boltzmann entropy and randomness tests,” in _Proceedings Workshop on Physics and Computation. PhysComp ’94_. Dallas, TX, USA: IEEE Comput. Soc. Press, 1994, pp. 209–216.
  * (16) A. Ebtekar, “The algorithmic second law of thermodynamics,” Sep. 2023.

##  APPENDIX A THE CONSTANT TERM IN THE GENERALIZED ZUREK’S BOUND

Many (in)equalities in this paper feature a constant additive term. In this
appendix, we show that the constant term can actually be omitted in practical
applications.

All the constant terms essentially come from the artificial choice of a
universal Turing machine, as the length of the interpreter in inequality (5).
To be more specific, it is reasonable to assume that
$l(int(U,U^{\prime}))\approx K_{U}(U^{\prime})$. We also suppose that
$U^{\prime}$ is a universal Turing machine with $s$ states and $a$ symbols.
Since there are in total $2^{s^{2}a^{2}}$ (nondeterministic) Turing machines
with $s$ states and $a$ symbols, we may further assume
$K_{U}(U^{\prime})\approx\log(2^{s^{2}a^{2}})=s^{2}a^{2}$. According to
woodsComplexitySmallUniversal2009 , the smallest universal Turing machines can
make $s^{2}a^{2}\approx 10^{2}$bits. Convert bits to Joule per Kelvin:

$10^{2}\operatorname{bits}=10^{-21}\operatorname{JK^{-1}},$

which is a negligible amount in comparison to practically interesting
thermodynamic quantities.

##  APPENDIX B AN ALGORITHMIC DEFINITION OF STOCHASTIC ENTROPY

In this appendix, we introduce an algorithmic definition of stochastic entropy
following gacsBoltzmannEntropyRandomness1994  and
ebtekarAlgorithmicSecondLaw2023 , and derive an integral fluctuation theorem
(IFT) of it.

Consider a time-inhomogenuous Markovian system with (meso)state space
$\mathcal{X}$. It is a common practice to assign a stochastic entropy (the
total entropy of the composite system of the system and the reservoir) to
every single state $x\in\mathcal{X}$
seifertStochasticThermodynamicsPrinciples2018 :

$s_{sto}(x)\equiv-\log p_{x}(t)-f_{x}(t),$ (26)

where $p_{x}(t)$ is the probability of the system being in state $x$ at time
$t$, and $f_{x}(t)$ is the free energy of state $x$. Because $p_{x}(t)$
depends on the prepared state distribution $p_{x}(0)$, the stochastic entropy
of the system depends not only on the state $x$ but also on the prepared state
distribution at time $t=0$, which is not a favorable property since we prefer
the entropy of the system to be a pure state function.

As in gacsBoltzmannEntropyRandomness1994  and ebtekarAlgorithmicSecondLaw2023
, we can define an entropy function of the system to depend only on $x$. To be
concrete, we define the algorithmic entropy as:

$s_{alg}(x)\equiv K(x|\mathcal{P})-f_{x}(t).$ (27)

Since $p_{x}(t)$ can be computed from $\mathcal{P}$, the coding theorem
implies that $K(x|\mathcal{P})\overset{+}{\leq}-\log p_{x}(t)$, so that
$s_{alg}(x)\overset{+}{\leq}s_{sto}(x)$.

We justify the above definition by demonstrating that $s_{alg}(x)$ can restore
to Boltzmann and Gibbs entropy in different senses. If $x$ is restricted in a
set $A$ with $|A|$ elements, then $K(x|A)\approx\log|A|$ which is the
Boltzmann entropy. For every probability distribution $P(x)$,
$S_{sh}(P)\overset{+}{=}\sum_{x}P(x)K(x|P)$, which means that Gibbs entropy is
the ensemble average of the algorithmic entropy for any ensemble.

What’s more, in the following we derive the integral fluctuation theorem for
$s_{alg}(x)$, thus proving the second law of the algorithmic entropy.
ebtekarAlgorithmicSecondLaw2023  has derived the integral fluctuation theorem
for a single jump, and here we generalize the previous result to any
trajectory.

The integral fluctuation theorem states that for every prepared state
distribution $p_{x}(0)$, there is:

$\langle 2^{-\Delta s_{alg}(\bm{x})}\rangle_{\bm{x}}\overset{\times}{\leq}1,$
(28)

where $\Delta s_{alg}(\bm{x})$ is the algorithmic entropy production during
the trajectory $\bm{x}$, and $\langle\cdot\rangle_{\bm{x}}$ means averaging
over trajectories.

From definition (27), $\Delta s_{alg}(\bm{x})$ can be expressed as:

$\Delta s_{alg}(\bm{x})=q(\bm{x})+K(x_{f}|\mathcal{P})-K(x_{0}|\mathcal{P})$
(29)

Thus we have:

$\langle 2^{-\Delta
s_{alg}(\bm{x})}\rangle_{\bm{x}}=\sum_{\bm{x}}P_{\bm{x}}(\bm{\lambda})2^{-q(\bm{x})-K(x_{f}|\mathcal{P})+K(x_{0}|\mathcal{P})}\\\
=\sum_{\bm{x}}p_{x_{0}}(0)P_{\bm{x}|x_{0}}(\bm{\lambda})\frac{P_{\tilde{\bm{x}}|x_{f}}(\tilde{\bm{\lambda}})}{P_{\bm{x}|x_{0}}(\bm{\lambda})}2^{-K(x_{f}|\mathcal{P})+K(x_{0}|\mathcal{P})}\\\
=\sum_{\bm{x}}p_{x_{0}}(0)P_{\tilde{\bm{x}}|x_{f}}(\tilde{\bm{\lambda}})2^{-K(x_{f}|\mathcal{P})+K(x_{0}|\mathcal{P})}\\\
\overset{\times}{\leq}\sum_{\bm{x}}p_{x_{0}}(0)P_{\tilde{\bm{x}}|x_{f}}(\tilde{\bm{\lambda}})2^{K(x_{0}|x_{f},\mathcal{P})}\\\
\overset{\times}{\leq}\sum_{\bm{x}}p_{x_{0}}(0)P_{\tilde{\bm{x}}|x_{f}}(\tilde{\bm{\lambda}})\frac{1}{\tilde{P}(x_{0}|x_{f},\mathcal{P})}=1,$
(30)

where the second equality comes from (15), the first inequality comes from
(8), and the second inequality comes from the coding theorem.

As shown in Appendix A, the constant multiplicative factor in (28) is
negligible, thus by Jensen’s inequality we arrive at the second law of the
algorithmic entropy:

$\Delta S_{alg}\equiv\langle\Delta s_{alg}\rangle_{\bm{x}}\geq 0.$ (31)