Recursive Representation

• In this section we will show
  • how Markov chains can be constructed from sequences of independent and identically distributed random variables,
  • that the recursive formulaê (9), (10), (11) and (13) are special cases of a general principle for the construction of Markov chains,
  • that vice versa every Markov chain can be considered as solution of a recursive stochastic equation.
• As usual let $E=\{1,2,\ldots,\ell\}$ be a finite (or countably infinite) set.
  • Furthermore, let $(D,\mathcal{D})$ be a measurable space, e.g. $D=\mathbb{R}^d$ could be the $d$-dimensional Euclidian space and $\mathcal{D}=\mathcal{B}(\mathbb{R}^d)$ the Borel $\sigma$-algebra on $\mathbb{R}^d$, or $D=[0,1]$ could be defined as the unit interval and $\mathcal{D}=\mathcal{B}([0,1])$ as the Borel $\sigma$-algebra on $[0,1]$.
  • Let now $Z_1,Z_2,\ldots:\Omega\to D$ be a sequence of independent and identically distributed random variables mapping into $D$, and let $X_0:\Omega\to E$ be independent of $Z_1,Z_2,\ldots$.
  • Let the random variables $X_1,X_2,\ldots:\Omega\to E$ be given by the stochastic recursion equation

    $$X_n=\varphi(X_{n-1},Z_n)\,,$$ (14)

    
    
    where $\varphi:E\times D\to E$ is an arbitrary measurable function.

Theorem 2.2    

• Let the random variables $X_0,X_1,\ldots:\Omega\to E$ be given by $(\ref{rec.sto.equ})$.
• Then
  $$P(X_{n}=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0=i_{0})= P(X_{n}=i_n\mid X_{n-1}=i_{n-1})$$
  holds for any $n\ge 1$ and $i_0,i_1,\ldots,i_n\in E$ such that $P( X_{n-1}=i_{n-1},\ldots,X_0=i_{0})>0$.

Proof

 

• Formula (14) implies that
  

  $$P(X_n=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0=i_0) = P(\varphi(X_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0 =i_0)$$

  $$= P(\varphi(i_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0 =i_0)$$

  $$= P(\varphi(i_{n-1},Z_n)=i_n) \,,$$

  
  
  • where the last equality follows from the transformation theorem for independent and identically distributed random variables (see Theorem WR-3.18),
  • as the random variables $X_0,\ldots,X_{n-1}$ are functions of $Z_1,\ldots,Z_{n-1}$ and hence independent of $\varphi(i_{n-1},Z_n)$.
• In the same way one concludes that
  

  $$P(\varphi(i_{n-1},Z_n)=i_n) = P(\varphi(i_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1})$$

  $$= P(\varphi(X_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1})$$

  $$= P(X_n=i_n\mid X_{n-1}=i_{n-1})\,.$$

  
  
  
   
    $\Box$
  
  
  

Remarks

 

• The proof of Theorem 2.2 yields that the conditional probability
  $$p_{ij}=P(X_n=j\mid X_{n-1}=i)$$
  is given by $p_{ij}=P(\varphi(i,Z_n)=j)$.
• $p_{ij}$ does not dependent on $n$, as the ``innovations'' $Z_n$ are identically distributed.
• Moreover, the joint probability $P(X_0=i_0,X_1=i_1, \ldots,X_n=i_n)$ is given by

  $$P(X_0=i_0,X_1=i_1,\ldots,X_n=i_n)=\alpha_{i_0}p_{i_0i_1}\ldots p_{i_{n-1}i_n}\,,$$ (15)

  
  
  where $\alpha_{i_0}=P(X_0=i_0)$.
• Consequently, the sequence $X_0,X_1,\ldots$ of random variables given by the recursive definition (14) is a Markov chain following the definition given in (3).

Our next step will be to show that vice versa, every Markov chain can be regarded as the solution of a recursive stochastic equation.

• Let $X_0,X_1,\ldots:\Omega\to E$ be a Markov chain with state space $E=\{1,2,\ldots,\ell\}$, initial distribution ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ and transition matrix ${\mathbf{P}}=(p_{ij})$.
• Based on a recursive equation of the form (14) we will construct a Markov chain $X_0^\prime,X_1^\prime,\ldots$ with initial distribution ${\boldsymbol{\alpha}}$ and transition matrix ${\mathbf{P}}$ such that

  $$P(X_0=i_0,\ldots,X_n=i_n)= P(X_0^\prime=i_0,\ldots,X_n^\prime=i_n)\,,\qquad\forall\,i_0,\ldots,i_n\in E$$ (16)

  
  
  for all $n\ge 0$:
  1. We start with a sequence $Z_0,Z_1,\ldots$ of independent random variables that are uniformly distributed on the interval $(0,1]$.
  2. First of all the $E$-valued random variable $X_0^\prime$ is defined as follows:
     $$\displaystyle X_0^\prime=k$$   if and only if$$\qquad Z_0\in\Bigl(\sum_{i=1}^{k-1} \alpha_i,\sum_{i=1}^{k}\alpha_i\Bigr]\,,$$
     for all $k=1,\ldots,\ell$, i.e.

     $$X_0^\prime=\sum_{k=1}^\ell k {1\hspace{-1mm}{\rm I}}\Bigl(\sum_{i=1}^{k-1}\alpha_i <Z_0\le \sum_{i=1}^{k}\alpha_i\Bigr)\,.$$ (17)

     
     

  3. The random variables $X_1^\prime,X_2^\prime,\ldots$ are defined by the recursive equation

     $$X_n^\prime=\varphi(X_{n-1}^\prime,Z_n)\,,$$ (18)

     
     
     where the function $\varphi:E\times(0,1]\to E$ is given by

     $$\varphi(i,z)=\sum_{k=1}^\ell k {1\hspace{-1mm}{\rm I}}\Bigl(\sum_{j=1}^{k-1}p_{ij} <z\le \sum_{j=1}^{k}p_{ij}\Bigr)\,.$$ (19)

     
     

• It is easy to see that the probabilities $P(X_0^\prime=i_0,X_1^\prime=i_1,\ldots,X_n^\prime=i_n)$ for the sequence $\{X_n^\prime\}$ defined by (17)-(18) are given by (3), i.e., $\{X_n^\prime\}$ is a Markov chain with initial distribution ${\boldsymbol{\alpha}}$ and transition matrix ${\mathbf{P}}$.

Remarks

 

• If (16) holds for two sequences $\{X_i\}$ and $\{X_i^\prime\}$ of random variables, these sequences are called stochastically equivalent.
• The construction principle (17)-(19) can be exploited for the Monte-Carlo simulation of Markov chains with given initial distribution and transition matrix.
• Markov chains on a countably infinite state space can be constructed and simulated in the same way. However, in this case (17)-(19) need to be modified by considering vectors ${\boldsymbol{\alpha}}$ and matrices ${\mathbf{P}}$ of infinite dimensions.