0.5 Beyond lossless compression  (Page 7/7)

The rest of proof is structured as follows. First, we show that the sequence of stable state distributions for the Markov chains (MC) used by the MCMC algorithm converges to a uniform distribution over the set of sequences that minimize the energy function as the iteration count $t$ increases. Then, we show using  Theorem 11 and  Theorem 12 that the non-homogeneous MC used in the MCMC algorithm is strongly ergodic, which by the definition of strong ergodicity implies that MCMC always converges to the stable distribution found above. This implies that the outcome of the MCMC algorithm converges to a minimum-energy solution as $t\to \infty$ , completing the proof of Theorem  Theorem 10 .

We therefore begin by finding the stable state distribution for the non-homogeneous MC used by the MCMC algorithm. At each super-iteration $r$ , the distribution defined as

satisfies ${\pi }_{\left(r\right)}{P}_{\left(r\right)}={\pi }_{\left(r\right)}$ . We can show that the distribution ${\pi }_{\left(r\right)}$ converges to a uniform distribution over the set of sequences that minimize the energy function, i.e.,

where $\mathcal{H}=\{w^n\in {\hat{\alpha }}^n\mathrm{s}.\mathrm{t}.ϵ\left(w^n\right)={min}_{z^n\in {\hat{\alpha }}^n}ϵ\left(z^n\right)\}$ . To show [link] , we will show that ${\pi }_{\left(r\right)}\left(w^n\right)$ is increasing for $w^n\in \mathcal{H}$ and eventually decreasing for $w^n\in {\mathcal{H}}^C$ . Since for $w^n\in \mathcal{H}$ and $z^n\in {\hat{\alpha }}^n$ , $ϵ\left(z^n\right)-ϵ\left(w^n\right)\ge 0$ , and so for $r_1<r_2$ we have

which together with [link] implies ${\pi }_{\left(r_1\right)}\left(w^n\right)\le {\pi }_{\left(r_2\right)}\left(w^n\right)$ . On the other hand, if $w^n\notin \mathcal{H}$ , then

For sufficiently small $t$ , the right hand side (more precisely, the second and third lines) of [link] is dominated by the second term (third line), which increases when $t$ decreases, and therefore ${\pi }_{\left(r\right)}\left(w^n\right)$ decreases for $w^n\in \mathcal{H}$ as $t$ increases. Finally, since all sequences $w^n\in \mathcal{H}$ have the same energy $ϵ\left(w^n\right)$ , it follows that the distribution is uniform over the symbols in $\mathcal{H}$ .

Having shown convergence of the non-homogenous Markov chain's stable state distributions, we now show that the non-homogeneous MC is strongly ergodic. The transition matrix $P_{\left(r\right)}$ of the MC at iteration $t$ depends on the temperature $t$ used within MCMC algorithm. We first show that the MC used in the MCMC algorithm is weakly ergodic via  Theorem 11 ; the proof of the following Lemma is given at the end of this section.

Lemma 2 The ergodic coefficient of $P_{\left(r\right)}$ for any $r\ge 0$ is upper bounded by

where ${\Delta }_k$ is defined in [link] .

Let $w_1^n,w_2^n$ be two arbitrary sequences in ${\hat{\alpha }}^n$ . The probability of transitioning from a given state to a neighboring state in an iteration within iteration $r^{\text{'}}$ of super iteration $r$ of the MCMC algorithm is given by [link] , and can be rewritten as

where ${ϵ}_{min,r^{\text{'}}}\left(w_1^{r^{\text{'}}-1}b{w}_{r^{\text{'}}+1}^n\right)={min}_{b^{\text{'}}\in \hat{\alpha }}ϵ\left(w_1^{r^{\text{'}}-1}{b}^{\text{'}}{w}_{r^{\text{'}}+1}^n\right)$ . Therefore the smallest probability of transition from $w_1^n$ to $w_2^n$ within super-iteration $r$ is bounded by

Using the alternative definition of the ergodic coefficient given in [link] ,

Using Lemma 2 , we can evaluate the sum given in Theorem 11 as

and therefore the non-homogeneous MC defined by ${\left\{P_{\left(r\right)}\right\}}_{r=1}^{\infty }$ is weakly ergodic. Now we can use Theorem 12 to show that the MC is strongly ergodic by proving that

Since we know from earlier in the proof that ${\pi }_{\left(r\right)}\left(w^n\right)$ is increasing for $w^n\in \mathcal{H}$ and eventually decreasing for $w^n\in {\mathcal{H}}^C$ , there exists a $r_0\in \mathbb{N}$ such that for any $r_1>r_0$ ,

Since the right hand side does not depend on $r_1$ , then we have that

This implies that the non-homogeneous MC used by MCMC algorithm is strongly ergodic, and thus completes the proof of  Theorem 10 .