Coupling to the Future; Counterexample

• First of all we consider a method for ,,coupling'' the paths of Markov chains where the ,,time''
  • is running forward, i.e. in a way that is perceived as natural.
  • Therefore, one also refers to this method as coupling to the future.
• For all $i\in\{1,\ldots,\ell\}$ let ${\mathbf{X}}^{(i)}=\bigl({\mathbf{X}}_0^{(i)},{\mathbf{X}}_1^{(i)},\ldots\bigr)$ be a homogenous Markov chain with finite state space $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$
  • with deterministic initial state ${\mathbf{X}}_0^{(i)}={\mathbf{x}}_i$ and with an irreducible and aperiodic transition matrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$,
  • such that ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ is the ergodic limit distribution of the Markov chain ${\mathbf{X}}^{(i)}$.

Definitions

 

• For all $k\in\{1,\ldots,\ell\}$ we consider
  • a sequence ${\mathbf{U}}^{(k)}=\bigl(U_1^{(k)},U_2^{(k)},\ldots\bigr)$ of independent and $(0,1]$-uniformly distributed random variables $U_n^{(k)}$,
  • called innovations in step $n$ for the current state ${\mathbf{x}}_k\in E$.
• We consider two different cases:
  • Either we assume the sequences ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ to be independent
  • or we merely consider a single sequence ${\mathbf{U}}=\bigl(U_1,U_2,\ldots\bigr)$ and define ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$.
• Let the Markov chain ${\mathbf{X}}^{(i)}$ be defined recursively by

  $${\mathbf{X}}_n^{(i)}=\varphi\bigl({\mathbf{x}}_k,U^{(k)}_n\bigr) \mbox{if $X^{(i)}_{n-1}={\mathbf{x}}_k$,}$$ (87)

  
  
  where $\varphi:E\times(0,1]\to E$ is a so-called valid update function, i.e.
  • $\varphi({\mathbf{x}},\cdot):(0,1]\to E$ is piecewise constant for all ${\mathbf{x}}\in E$
  • and for arbitrary ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ such that $p_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$ the total length of the set $\{u\in(0,1]:\,\varphi({\mathbf{x}},u)={\mathbf{x}}^\prime\}$ equals $p_{{\mathbf{x}}{\mathbf{x}}^\prime}$.
• The random variable $\tau=\min\bigl\{n\ge 1:\,{\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}\bigr\}$ is called coupling time where we define $\tau=\infty$ if there is no natural number $n$ such that ${\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}$.

Theorem 3.21   $\;$ If the sequences of innovations ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ are independent, then $\tau<\infty$ with probability $1$ and ${\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}$ for all $n>\tau$ .

Proof

 

• The recursive definition (87) of the Markov chains ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ immediately implies ${\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}$ for all $n>\tau$.
• It is left to show that $P(\tau<\infty)=1$. We notice that it suffices to show that for arbitrary $i\not= i^\prime$
  $$\lim\limits_{r\to\infty} P\Bigl(\max\bigl\{n:{\mathbf{X}}_n^{(i)}\not={\mathbf{X}}_n^{(i^\prime)}\bigr\}\le r \Bigl)=1\,.$$
  • As
    

    $$P\Bigl(\max\bigl\{n:{\mathbf{X}}_n^{(i)}\not={\mathbf{X}}_n^{(i^\prime)}\bigr\}\le r \Bigl) = 1-P\Bigl(\max\bigl\{n:{\mathbf{X}}_n^{(i)}\not={\mathbf{X}}_n^{(i^\prime)}\bigr\}>r\Bigl)$$

    $$= 1- P\Bigl({\mathbf{X}}_r^{(i)}\not={\mathbf{X}}_r^{(i^\prime)}\Bigl)$$

    
    
    this is equivalent to
    $$\lim\limits_{r\to\infty}P\Bigl({\mathbf{X}}_r^{(i)}\not={\mathbf{X}}_r^{(i^\prime)}\Bigl)=0\,.$$

  • Let now $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\,,$$
    and consider the decomposition $r=m(r)n_0+k$ for some $m(r)\in\{0,1,\ldots\}$ and
    $k\in \{0,1,\ldots,n_0-1\}$.
  • The independence of the innovation sequences ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ yields for $r\to\infty$
    

    $${P\Bigl({\mathbf{X}}_r^{(i)}\not={\mathbf{X}}_r^{(i^\prime)}\Bigl... ...{(i^\prime)},\, {\mathbf{X}}_{r}^{(i)}\not={\mathbf{X}}_{r}^{(i^\prime)}\Bigl)}$$

    $$= \sum\limits_{j=1}^\ell\sum\limits_{j^\prime\not=j} P\Bigl({\mathb... ...{\mathbf{x}}_j,\, {\mathbf{X}}_{n_0}^{(i^\prime)}={\mathbf{x}}_{j^\prime}\Bigl)$$

    $$= \sum\limits_{j=1}^\ell\sum\limits_{j^\prime\not=j} P\Bigl({\mathb... ...; P\Bigl({\mathbf{X}}_{r-n_0}^{(j)}\not={\mathbf{X}}_{r-n_0}^{(j^\prime)}\Bigl)$$

    $$= \underbrace{\sum\limits_{j=1}^\ell p_{{\mathbf{x}}_i{\mathbf{x}}_... ...} P\Bigl({\mathbf{X}}_{r-n_0}^{(j)}\not={\mathbf{X}}_{r-n_0}^{(j^\prime)}\Bigl)$$

    $$\le (1-c)\, \max\limits_{j\not= j} P\Bigl({\mathbf{X}}_{r-n_0}^{(j)}\not={\mathbf{X}}_{r-n_0}^{(j^\prime)}\Bigl)$$

    $$\vdots$$

    $$\le (1-c)^{m(r)}\longrightarrow 0\,.$$

    
    
    
     
      $\Box$
    
    
    

Remarks

 

• Under additional assumptions about the irreducible and periodic transition matrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ it can be shown that the coupling time $\tau$ is finite even if
  • only a single sequence ${\mathbf{U}}=\bigl(U_1,U_2,\ldots\bigr)$ innovations is considered, i.e. ${\mathbf{U}}={\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}$,
  • and if for all ${\mathbf{x}}\in E$ the update function $\varphi:E\times(0,1]\to E$ is given by

    $$\varphi({\mathbf{x}},\,u)={\mathbf{x}}_j\,, \mbox{if $\sum\limits_{r=1}^{j-1} p_{{\mathbf{x}}{\mathbf{x}}_r} <u\le \sum\limits_{r=1}^j p_{{\mathbf{x}}{\mathbf{x}}_r}$.}$$ (88)

    
    

• Such an additional condition imposed on ${\mathbf{P}}$ will be discussed in the following theorem, see also the monotonicity condition in Section 3.5.3.

Theorem 3.22    

• Let ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$ and let the update function $\varphi:E\times(0,1]\to E$ be given by $(\ref{def.one.upd})$. Furthermore, for some ${\mathbf{x}}_{i_0}\in E$, let

  $$\max\limits_{{\mathbf{x}}\in E}\sum\limits_{r=1}^{i_0-1} p_{{\mat... ...ts_{{\mathbf{x}}\in E}\sum\limits_{r=1}^{i_0} p_{{\mathbf{x}}{\mathbf{x}}_r}\,.$$ (89)

  
  

• Then $\tau<\infty$ with probability $1$ and for all $n>\tau$ ${\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}$.

Proof

 

• Similar to the proof of Theorem 3.21 it suffices to show that for arbitrary $i\not= i^\prime$
  $$\lim\limits_{r\to\infty}P\Bigl({\mathbf{X}}_r^{(i)}\not={\mathbf{X}}_r^{(i^\prime)}\Bigl)=0\,.$$
  Observe that
• 
  

  $$P\Bigl({\mathbf{X}}_r^{(i)}\not={\mathbf{X}}_r^{(i^\prime)}\Bigl) = P\Bigl({\mathbf{X}}_1^{(i)}\not={\mathbf{X}}_1^{(i^\prime)},\,{\mathbf{X}}_r^{(i)}\not={\mathbf{X}}_r^{(i^\prime)}\Bigl)$$

  $$= \sum\limits_{j=1}^\ell\sum\limits_{j^\prime\not=j} P\Bigl({\mathb... ...i)}={\mathbf{x}}_j,\, {\mathbf{X}}_1^{(i^\prime)}={\mathbf{x}}_{j^\prime}\Bigl)$$

  $$= \sum\limits_{j=1}^\ell\sum\limits_{j^\prime\not=j} P\Bigl({\mathb... ...gl)\; P\Bigl({\mathbf{X}}_{r-1}^{(j)}\not={\mathbf{X}}_{r-1}^{(j^\prime)}\Bigr)$$

  $$\le \Bigl(1-\underbrace{P\Bigl({\mathbf{X}}_1^{(i)}={\mathbf{X}}_1^{(... ... j}\; P\Bigl({\mathbf{X}}_{r-1}^{(j)}\not={\mathbf{X}}_{r-1}^{(j^\prime)}\Bigr)$$

  $$\vdots$$

  $$\le (1-d)^r \longrightarrow 0\,,$$

  
  
  where we use that (87) - (89) imply
  $$0< d = \max\limits_{{\mathbf{x}}\in E}\sum\limits_{r=1}^{i_0-1} p... ...i_0}\Bigl)\le P\Bigl({\mathbf{X}}_1^{(i)}={\mathbf{X}}_1^{(i^\prime)}\Bigl)\,.$$
  
   
    $\Box$
  
  
  

Remarks

 

• In general $P(\tau<\infty)=1$ does not imply ${\mathbf{X}}_\tau^{(i)}\sim{\boldsymbol{\pi}}$,
  • i.e., at the coupling time $\tau$ the distribution of the Markov chain ${\mathbf{X}}^{(i)}$ does in general not coincide with the stationary limit distribution ${\boldsymbol{\pi}}$ although this could be a conjecture.
• The following counterexample illustrates this paradox.
  • Consider the state space $E=\{1,2\}$ and the irreducible and aperiodic transition matrix
    $${\mathbf{P}}=\left(\begin{array}{cc} 0.5 & 0.5\\ 1 & 0\end{array}\right)$$
    whose stationary limit distribution is ${\boldsymbol{\pi}}=(2/3,\,1/3)^\top$.
  • If ${\mathbf{X}}_{\tau-1}^{(1)}\not={\mathbf{X}}_{\tau-1}^{(2)}$ we necessarily obtain ${\mathbf{X}}_{\tau-1}^{(1)}=2$ or ${\mathbf{X}}_{\tau-1}^{(2)}=2$ and therefore ${\mathbf{X}}_\tau^{(1)}={\mathbf{X}}_\tau^{(2)}=1$.