MCMC Estimators; Bias and Fundamental Matrix

In this section we will investigate the characteristics of Monte-Carlo estimators for expectations.

• Examples for similar problems were already discussed in Section 3.1.1,
  • when we estimated $\pi$ by statistical means
  • and the value of integrals via Monte-Carlo simulation.
• However, for these purposes we assumed
  • that the pseudo-random numbers can be regarded as realizations of independent and identically distributed sampling variables.
  • In the present section we assume that the sample variables form an (appropriately chosen) Markov chain.
• This is the reason why these estimators are called Markov-Chain-Monte-Carlo estimators (MCMC estimators).

Statistical Model

 

• Let $V$ be a finite (nonempty) index set and let ${\mathbf{X}}=(X(v),\,v\in V)$ be a discrete random vector,
  • taking values in the finite state space $E\subset\mathbb{R}^{\vert V\vert}$ with probability $1$,
  • where $E$ is identified with the set $E=\{1,\ldots,\ell\}$ of the first $\ell=\vert E\vert$ natural numbers.
  • Furthermore, we assume $\pi_i>0$ for all $i\in E$ where ${\boldsymbol{\pi}}=(\pi_i,\,i\in E)$ denotes the probability function of the random vector ${\mathbf{X}}$.
• Our goal
  • is to estimate the expectation $\theta={\mathbb{E}\,}\varphi({\mathbf{X}})$ via MCMC simulation where

    $$\theta={\boldsymbol{\pi}}^\top{\boldsymbol{\varphi}}$$ (69)

    
    

  • and ${\boldsymbol{\varphi}}=(\varphi_1,\ldots,\varphi_{\ell})^{\top}: E \to \mathbb{R}$ is an arbitrary but fixed function.
• As an estimator for $\theta$ we consider the random variable

  $$\widehat\theta_n=\frac{1}{n}\;\sum\limits_{k=0}^{n-1} \varphi({\mathbf{X}}_k)\,,\qquad\forall\, n\ge 1 \,,$$ (70)

  
  
  • where ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ is a Markov chain with state space $E$, arbitrary but fixed initial distribution ${\boldsymbol{\alpha}}$ and
  • an irreducible and aperiodic transition matrix ${\mathbf{P}}=\bigl(p_{ij}\bigr)$, such that ${\boldsymbol{\pi}}$ is the ergodic limit distribution with respect to ${\mathbf{P}}$.

Remarks

 

• Typically, the initial distribution ${\boldsymbol{\alpha}}$ does not coincide with the simulated distribution ${\boldsymbol{\pi}}$.
  • Consequently, the MCMC estimator $\widehat\theta_n$ defined by (70) is not unbiased for fixed (finite) sample size,
  • i.e. in general ${\mathbb{E}\,}\widehat\theta_n\not=\theta$ for all $n\ge 1$.
• For determining the bias ${\mathbb{E}\,}\,\widehat\theta_n-\theta$ the following representation formula will be helpful.

Theorem 3.17   $\;$ For all $n\ge 1$,

$${\mathbb{E}\,}\,\widehat\theta_n= \frac{1}{n}\; {\boldsymbol{\alpha}}^\top\sum\limits_{k=0}^{n-1}{\mathbf{P}}^k{\boldsymbol{\varphi}}\,.$$ (71)

Proof

 

• In Theorem 2.3 we proved that for all $k\ge 1$ the distribution ${\boldsymbol{\alpha}}_k$ of ${\mathbf{X}}_k$ is given by ${\boldsymbol{\alpha}}_k^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}^k$.
• Thus, by definition (70) of the MCMC estimator $\widehat\theta_n$, we get that
  $${\mathbb{E}\,}\,\widehat\theta_n = \frac{1}{n}\;\sum\limits_{k=0}... ...l{\alpha}}^\top \sum\limits_{k=0}^{n-1}{\mathbf{P}}^k{\boldsymbol{\varphi}}\,.$$
  
   
    $\Box$
  
  
  

Remarks

 

• As an immediate consequence of Theorem 3.17, the ergodicity of the transition matrix ${\mathbf{P}}$, and (69), one obtains
  $$\lim\limits_{n\to\infty} {\mathbb{E}\,}\widehat\theta_n=\theta\,,$$

• i.e., the MCMC estimator $\widehat\theta_n$ for $\theta$ defined in (70) is asymptotically unbiased.

Apart from this, the asymptotic behavior of $n\bigl({\mathbb{E}\,}\,\widehat\theta_n-\theta\bigr)$ for $n\to\infty$ can be determined. For this purpose we need the following two lemmata.

Lemma 3.2   $\;$ Let ${\boldsymbol{\Pi}}$ be the $\ell\times\ell$ matrix consisting of the $\ell$ identical row vectors ${\boldsymbol{\pi}}^\top$. Then

$$({\mathbf{P}}-{\boldsymbol{\Pi}})^n={\mathbf{P}}^n-{\boldsymbol{\Pi}}$$ (72)

for all $n\ge 1$ and in particular

$$\lim\limits_{n\to\infty}({\mathbf{P}}-{\boldsymbol{\Pi}})^n={\,{\bf0}}\,.$$ (73)

Proof

 

• Evidently, (72) holds for $n=1$.
  • If we assume that (72) holds for some $n-1\ge 1$, then
    

    $$({\mathbf{P}}-{\boldsymbol{\Pi}})^n = ({\mathbf{P}}-{\boldsymbol{\Pi}})^{n-1} ({\mathbf{P}}-{\boldsymbol{\Pi}})=({\mathbf{P}}^{n-1}-{\boldsymbol{\Pi}}) ({\mathbf{P}}-{\boldsymbol{\Pi}})$$

    $$= {\mathbf{P}}^n-{\boldsymbol{\Pi}}{\mathbf{P}}-{\mathbf{P}}^{n-1}{\boldsymbol{\Pi}}+{\boldsymbol{\Pi}}^2 = {\mathbf{P}}^n-{\boldsymbol{\Pi}}\,,$$

    
    
    where the last equality follows from the fact that
    $${\boldsymbol{\pi}}^\top{\mathbf{P}}={\boldsymbol{\pi}}^\top$$   and thus$$\qquad {\boldsymbol{\Pi}}{\mathbf{P}}={\mathbf{P}}{\boldsymbol{\Pi}}={\boldsymbol{\Pi}}={\boldsymbol{\Pi}}^2\,.$$

  • This proves (72) for all $n\ge 1$.
• As ${\mathbf{P}}$ is assumed to be irreducible and aperiodic,
  • by Theorems 2.4 and 2.9 we get that ${\mathbf{P}}^n-{\boldsymbol{\Pi}}\to{\,{\bf0}}$ if $n\to\infty$.
  • Thus, by (72), also $({\mathbf{P}}-{\boldsymbol{\Pi}})^n\to{\,{\bf0}}$ if $n\to\infty$.
    
    $\Box$

Remarks

 

• By the zero convergence $({\mathbf{P}}-{\boldsymbol{\Pi}})^n\to{\,{\bf0}}$ for $n\to\infty$ in Lemma 3.2 and Lemma 2.4, the matrix ${\mathbf{I}}-({\mathbf{P}}-{\boldsymbol{\Pi}})$ is invertible.
• In order to show this it suffices to consider the matrix ${\mathbf{A}}={\mathbf{P}}-{\boldsymbol{\Pi}}$ in Lemma 2.4.
• The inverse matrix

  $${\mathbf{Z}}=({\mathbf{I}}-({\mathbf{P}}- {\boldsymbol{\Pi}}))^{-1}$$ (74)

  
  
  is hence well defined. It is called the fundamental matrix of ${\mathbf{P}}$.

Lemma 3.3   $\;$ The fundamental matrix ${\mathbf{Z}}=({\mathbf{I}}-({\mathbf{P}}-{\boldsymbol{\Pi}}))^{-1}$ of the irreducible and aperiodic transition matrix ${\mathbf{P}}$ has the representation formulae

$${\mathbf{Z}}={\mathbf{I}}+\sum\limits_{k=1}^\infty ({\mathbf{P}}^k-{\boldsymbol{\Pi}})$$ (75)

and

$${\mathbf{Z}}={\mathbf{I}}+ \lim\limits_{n\to\infty}\sum_{k=1}^{n-1}\;\frac{n-k}{n}\;({\mathbf{P}}^k-{\boldsymbol{\Pi}})\,.$$ (76)

Proof

 

• Formula (75) follows from Lemmas 2.4 and  3.2 as for ${\mathbf{A}}={\mathbf{P}}-{\boldsymbol{\Pi}}$
  

  $${\mathbf{Z}} = ({\mathbf{I}}-{\mathbf{A}})^{-1}$$

  $$= ({\mathbf{I}}-{\mathbf{A}})^{-1}\lim\limits_{n\to\infty}({\mathbf{I}}-{\mathbf{A}}^n)$$

  $$= \lim\limits_{n\to\infty}\Bigl(({\mathbf{I}}-{\mathbf{A}})^{-1}({\mathbf{I}}-{\mathbf{A}}^n)\Bigr)$$

  $$\stackrel{(2.\ref{geo.mat.ser})}{=} \lim\limits_{n\to\infty} \Bigl({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}\Bigr)$$

  $$= {\mathbf{I}}+\sum\limits_{k=1}^\infty {\mathbf{A}}^k \qquad\Biggl... ...\mathbf{I}}+\sum\limits_{k=1}^\infty ({\mathbf{P}}-{\boldsymbol{\Pi}})^k\Biggr)$$

  $$\stackrel{(\ref{rep.fun.mat})}{=} {\mathbf{I}}+\sum\limits_{k=1}^\infty ({\mathbf{P}}^k-{\boldsymbol{\Pi}})\,.$$

  
  

• In order to show (76) it suffices to notice that
  $$\sum\limits_{k=1}^n ({\mathbf{P}}^k-{\boldsymbol{\Pi}})-\sum\limi... ...}})=\;\frac{1}{n}\; \sum\limits_{k=1}^{n} k({\mathbf{P}}-{\boldsymbol{\Pi}})^k$$
  and that the last expression converges to ${\,{\bf0}}$ for $n\to\infty$.
• The zero convergence is due to the fact that for every $\ell\times\ell$ matrix ${\mathbf{A}}$
  $$({\mathbf{I}}-{\mathbf{A}})\sum\limits_{k=1}^n k{\mathbf{A}}^k=\sum\limits_{k=1}^n {\mathbf{A}}^k-n{\mathbf{A}}^{n+1}$$
  and thus for ${\mathbf{A}}={\mathbf{P}}-{\boldsymbol{\Pi}}$
  

  $$\lim\limits_{n\to\infty}\;\frac{1}{n}\;\sum\limits_{k=1}^{n} k({\mathbf{P}}-{\boldsymbol{\Pi}})^k = \lim\limits_{n\to\infty}\;\Biggl(\frac{1}{n}\;{\mathbf{Z}}\sum\li... ...\boldsymbol{\Pi}})^k-{\mathbf{Z}}({\mathbf{P}}-{\boldsymbol{\Pi}})^{n+1}\Biggr)$$

  $$\stackrel{(\ref{rep.fun.mat})}{=} {\mathbf{Z}}\Biggl(\lim\limits_{n\to... ...i}})^{n+1}}_{\stackrel{(\ref{lim.peh.phi})}{\longrightarrow}{\,{\bf0}}} \Biggr)$$

  $$= {\,{\bf0}}\,.$$

  
  
  
   
    $\Box$
  
  
  

Theorem 3.17 and Lemma 3.3 enable us to give a more detailed description of the asymptotic behavior of the bias ${\mathbb{E}\,}\,\widehat\theta_n-\theta$.

Theorem 3.18    

• Let $a=\bigl({\boldsymbol{\alpha}}^\top{\mathbf{Z}}-{\boldsymbol{\pi}}^\top\bigr){\boldsymbol{\varphi}}$ where ${\mathbf{Z}}$ denotes the fundamental matrix of ${\mathbf{P}}$ that was introduced by $(\ref{def.fun.mat})$.
• Then, for all $n\ge 1$,

  $$n \bigl({\mathbb{E}\,}\,\widehat\theta_n-\theta\bigr) = a+e_n\,,$$ (77)

  
  
  where $e_n$ is a remainder such that $e_n\to 0$ for $n\to\infty$.

Proof

 

• The representation formula (75) in Lemma 3.3 yields
  

  $${\boldsymbol{\alpha}}^\top{\mathbf{Z}}{\boldsymbol{\varphi}} = {\boldsymbol{\alpha}}^\top{\boldsymbol{\varphi}}+ {\boldsymbol{\a... ...infty}\sum_{k=1}^{n-1}({\mathbf{P}}^k-{\boldsymbol{\Pi}}){\boldsymbol{\varphi}}$$

  $$= {\boldsymbol{\alpha}}^\top{\boldsymbol{\varphi}}+\lim\limits_{n\t... ...\top{\boldsymbol{\Pi}}}_{={\boldsymbol{\pi}}^\top} {\boldsymbol{\varphi}}\Bigr)$$

  $$= \lim\limits_{n\to\infty} \Bigl({\boldsymbol{\alpha}}^\top\Bigl(\s... ...oldsymbol{\varphi}}-(n-1){\boldsymbol{\pi}}^\top{\boldsymbol{\varphi}}\Bigr)\,.$$

  
  

• Hence by taking into account Theorem 3.17 we obtain the following for a certain sequence $\{e_n\}$ such that $e_n\to 0$:
  

  $$a = \bigl({\boldsymbol{\alpha}}^\top{\mathbf{Z}}-{\boldsymbol{\pi}}^\top\bigr){\boldsymbol{\varphi}}$$

  $$= {\boldsymbol{\alpha}}^\top\Bigl(\sum_{k=0}^{n-1} {\mathbf{P}}^k\Bigr){\boldsymbol{\varphi}}-n{\boldsymbol{\pi}}^\top{\boldsymbol{\varphi}}-e_n$$

  $$\stackrel{(\ref{for.bia.mcm})}{=} n\,{\mathbb{E}\,}\widehat\theta_n-n{\boldsymbol{\pi}}^\top{\boldsymbol{\varphi}}-e_n$$

  $$\stackrel{(\ref{dar.erw.the})}{=} n \bigl({\mathbb{E}\,}\,\widehat\theta_n-\theta\bigr)-e_n\,.$$

  
  
  
   
    $\Box$