Monotone Coupling Algorithms

• We additionally assume that the state space $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ is partially ordered and has a maximal element ${\,{\bf 1}}\in E$ and a minimal element ${\,{\bf0}}\in E$, i.e., there is a relation $\preceq$ on $E$ such that

  (a)

  ${\mathbf{x}}\preceq{\mathbf{x}}\,,\qquad\forall\,{\mathbf{x}}\in E\,,$

  (b)

  ${\mathbf{x}}\preceq{\mathbf{y}}$ and ${\mathbf{y}}\preceq{\mathbf{z}}$ $\Rightarrow$ ${\mathbf{x}}\preceq{\mathbf{z}}\,,\qquad\forall\,{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}\in E\,,$

  (c)

  ${\mathbf{x}}\preceq{\mathbf{y}}$ and ${\mathbf{y}}\preceq{\mathbf{x}}$ $\Rightarrow$ ${\mathbf{x}}={\mathbf{y}}\,,\qquad\forall\,{\mathbf{x}},{\mathbf{y}}\in E\,,$

  (d)

  ${\,{\bf0}}\preceq{\mathbf{x}}\preceq{\,{\bf 1}}\,,\qquad\forall\,{\mathbf{x}}\in E\,.$

• Furthermore, we impose the condition
  • that the update function $\varphi:E\times(0,1]\to E$ is monotonously nondecreasing with respect to the partial order $\preceq$, i.e., for arbitrary ${\mathbf{x}},{\mathbf{y}}\in E$ such that ${\mathbf{x}}\preceq{\mathbf{y}}$ we have

    $$\varphi({\mathbf{x}},u)\preceq \varphi({\mathbf{y}},u)\,,\qquad\forall\, u\in(0,1]\,.$$ (91)

    
    

• Let the innovations ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ be identical with probability $1$,
  • i.e., we merely consider a single sequence ${\mathbf{U}}=\bigl(U_0,U_{-1},\ldots\bigr)$ of independent and $(0,1]$-uniformly distributed random variables and define ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$.
  • For arbitrary $m\in\{-1,-2,\ldots\}$ and $i\in\{1,\ldots,\ell\}$ the Markov chain ${\mathbf{X}}^{(m,i)}$ is recursively defined by

    $${\mathbf{X}}_n^{(m,i)}=\varphi\bigl({\mathbf{X}}^{(m,i)}_{n-1},U_n\bigr)\,, \qquad\forall\,n=m+1,m+2,\ldots\,.$$ (92)

    
    

Remarks

 

• If ${\mathbf{x}}_i\preceq{\mathbf{x}}_j$, then by (91) and (92) we get that for all $n\ge m$

  $${\mathbf{X}}_n^{(m,i)}\preceq{\mathbf{X}}_n^{(m,j)}\,.$$ (93)

  
  

• In particular, for arbitrary $n\ge m$ and $i\in\{1,\ldots,\ell\}$,

  $${\mathbf{X}}_n^{(m,\min)}\preceq{\mathbf{X}}_n^{(m,i)}\preceq{\mathbf{X}}_n^{(m,\max)}\,,$$ (94)

  
  
  • where ${\mathbf{X}}^{(m,\min)}$ and ${\mathbf{X}}^{(m,\max)}$ denote the Markov chains
    $${\mathbf{X}}^{(m,\min)}=({\mathbf{X}}_m^{(m,\min)},{\mathbf{X}}_{m+1}^{(m,\min)},\ldots)$$   und$$\qquad {\mathbf{X}}^{(m,\max)}=({\mathbf{X}}_m^{(m,\max)},{\mathbf{X}}_{m+1}^{(m,\max)},\ldots)$$

  • that are recursively defined by (92) with ${\mathbf{X}}_m^{(m,\min)}={\,{\bf0}}$ and ${\mathbf{X}}_m^{(m,\max)}={\,{\bf 1}}$.
• Due to (94) it suffices to choose an initial ,,time'' that lies far enough in the past
  • such that the paths of ${\mathbf{X}}^{(m,\min)}$ and ${\mathbf{X}}^{(m,\max)}$ will have merged by ,,time'' 0,
  • i.e., we consider the CFTP coupling time

    $$\zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,\min)}={\mathbf{X}}_0^{(m,\max)}\bigr\}\,.$$ (95)

    
    

Theorem 3.24   $\;$ Let the update function $\varphi:E\times(0,1]\to E$ satisfy the monotonicity condition $(\ref{iso.upd.fun})$.

• Then, for the CFTP coupling time defined by $(\ref{mon.kop.zei})$, it holds that $\zeta<\infty$ with probability $1$.
• Moreover, for arbitrary $m\le-\zeta$ and $i,j\in\{1,\ldots,\ell\}$, ${\mathbf{X}}_0^{(m,i)}={\mathbf{X}}_0^{(-\zeta,j)}\sim{\boldsymbol{\pi}}$.

Proof

 

• As the argument showing that ${\mathbf{X}}_0^{(m,i)}={\mathbf{X}}_0^{(-\zeta,j)}\sim{\boldsymbol{\pi}}$ for arbitrary $m\le-\zeta$ and $i,j\in\{1,\ldots,\ell\}$ if $P(\zeta<\infty)=1$, is similar to the proof of Theorem 3.23 this part of the proof is omitted.
• We merely show that $P(\zeta<\infty)=1$.
  • First of all, we observe that for all $r\ge 1$

    $$\{\zeta>r\}\subset\Bigl\{{\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\,{\bf 1}},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\,{\bf 1}}\Bigr\}\,,$$ (96)

    
    
    as (94) implies
    

    $$\{\zeta>r\} = \Bigl\{ {\mathbf{X}}_0^{(-r,\min)}\not={\mathbf{X}}_0^{(-r,\max)}\Bigr\}$$

    $$= \Bigl\{{\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\mathbf{X}}_{-r+1}^{(... ...)},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\mathbf{X}}_0^{(-r,\max)}\Bigr\}$$

    $$\stackrel{(\ref{sem.min.maj})}{\subset} \Bigl\{{\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\,{\bf 1}},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\,{\bf 1}}\Bigr\}\,.$$

    
    

  • As in the proof of Theorem 3.21 let $n_0\ge 1$ be a natural number such that

    $$\min\limits_{{\mathbf{x}},{\mathbf{x}}^\prime\in E} p_{{\mathbf{x}}{\mathbf{x}}^\prime}^{(n_0)}=c>0\,,$$ (97)

    
    
    and decompose $r$ such that $r=m(r)n_0+k$ for some $m(r)\in\{0,1,\ldots\}$ and $k\in \{0,1,\ldots,n_0-1\}$.
  • By (96) and (97) we obtain
    

    $$P\bigl(\zeta=\infty\bigr) = \lim\limits_{r\to\infty}P\bigl(\zeta>r\bigr)$$

    $$\stackrel{(\ref{ent.hal.rel})}{\le} \lim\limits_{r\to\infty} P\Bigl({\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\,{\bf 1}},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\,{\bf 1}}\Bigr)$$

    $$\le \lim\limits_{r\to\infty} \sum\limits_{{\mathbf{x}}_1,\ldots,{\mat... ...hbf{x}}_2}\cdot\ldots\cdot p^{(n_0)}_{{\mathbf{x}}_{m(r)-1}{\mathbf{x}}_{m(r)}}$$

    $$\stackrel{(\ref{min.ube.war})}{\le} \lim\limits_{r\to\infty} (1-c)^{m(r)}=0\,.$$

    
    
    
     
      $\Box$
    
    
    

Remarks

 

• Sometimes the update function $\varphi:E\times(0,1]\to E$ is not monotonously nondecreasing but nonincreasing with respect to the partial order $\preceq$, i.e., for arbitrary ${\mathbf{x}},{\mathbf{y}}\in E$ such that ${\mathbf{x}}\preceq{\mathbf{y}}$ we have

  $$\varphi({\mathbf{x}},u)\succeq \varphi({\mathbf{y}},u)\,,\qquad\forall\, u\in(0,1]\,.$$ (98)

  
  

• In this case the following cross-over technique turns out to be useful.
  • Based on the update function $\varphi:E\times(0,1]\to E$ we construct a new nondecreasing update function $\varphi^\prime:E\times(0,1]^2\to E$ which is given as

    $$\varphi^\prime({\mathbf{x}};u_1,u_2)=\varphi(\varphi({\mathbf{x}},u_1),u_2)\,,\qquad\forall \,{\mathbf{x}}\in E;\,u_1,u_2\in(0,1]\,.$$ (99)

    
    

  • This function has the desired property as by (98) and (99) we obtain for arbitrary ${\mathbf{x}},{\mathbf{y}}\in E$ such that ${\mathbf{x}}\preceq{\mathbf{y}}$
    $$\varphi^\prime({\mathbf{x}};u_1,u_2)=\varphi(\varphi({\mathbf{x}}... ...u_2)=\varphi^\prime({\mathbf{y}};u_1,u_2)\,,\qquad\forall \,u_1,u_2\in(0,1]\,,$$
    i.e., $\varphi^\prime:E\times(0,1]^2\to E$ is nondecreasing if $\varphi:E\times(0,1]\to E$ is nonincreasing.
• Let now $\varphi:E\times(0,1]\to E$ be an update function with respect to the irreducible and aperiodic transition matrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ with ergodic limit distribution ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$.
  • Then the map $\varphi^\prime:E\times(0,1]^2\to E$ defined by (99) is a valid update function with respect to the irreducible and aperiodic two-step transition matrix ${\mathbf{P}}^{(2)}=(p^{(2)}_{{\mathbf{x}}{\mathbf{x}}^\prime})$ and it has the same ergodic limit distribution ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$.
  • In the same way that was used to prove Theorem 3.24 one can show that the coupling time $\zeta^\prime=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(2m,\min)}={\mathbf{X}}_0^{(2m,\max)}\bigr\}$ is finite with probability $1$, i.e., $\zeta^\prime<\infty$ and ${\mathbf{X}}_0^{(-2\zeta^\prime,i)}\sim{\boldsymbol{\pi}}$ for all $i\in\{1,\ldots,\ell\}$ if $\varphi:E\times(0,1]\to E$ is nonincreasing.