On the approximation of one Markov chain by another (Q818819): Difference between revisions

Consider an ergodic discrete time Markov process, with state space \(\Omega\) and transition probability \(P(x,\cdot)\), and another (``approximating'') Markov process, with state space \(\hat\Omega\subseteq\Omega\) and transition probability \(\hat P(x,\cdot)\). Consider in \(\Omega\) a separable metric \(d\) and define the family of metrics in the space of probabilities on \(\Omega\) \[ \rho_{\lambda}(\pi,\pi'):=\inf\{\varepsilon:\;\pi(A)\leq\pi'(A^{\lambda\varepsilon})+\varepsilon \text{ for all closed \(A\)}\}, \] where \(A^{\lambda\varepsilon}:=\{y:\;d(y,A)\leq \lambda\varepsilon\}\). Denote by \(P^t\) the corresponding \(t\)-steps transition probability and define the variation threshold time \[ \tau_1:=\min\{t:\;\|P^t(x,\cdot)-P^t(x',\cdot)\|\leq e^{-1},\;\text{for all \(x,x'\in\Omega\)}\}, \] where \(\|\cdot\|\) means total variation. The main result of the paper is the following: Suppose that for some \(\lambda,\;C,\;\delta\geq 0\), it holds that \newline 1. \(\rho_{\lambda}(\hat P(x,\cdot),P(x,\cdot))\leq \delta\), for all \(x\in\hat\Omega\); 2. \(\rho_{\lambda}(\hat P(x,\cdot),P(x',\cdot))\leq C d(x,x')\), for all \(x,x'\in\Omega\); \newline 3. the Markov process defined by \(P\) has stationary distribution \(\pi\). Then: \(\rho_{\lambda}(\hat P^t(x,\cdot),\pi)\leq \varepsilon\) if \(t\geq t_{\varepsilon}:=\log(2e/\varepsilon)\tau_1\) and, moreover: a. if \(\lambda C < 1\), then \(\delta\leq (1-\lambda C)\varepsilon/2t_\varepsilon\), b. if \(\lambda C =1\), then \(\delta\leq \varepsilon/t_\varepsilon(t_\varepsilon+1)\), c. if \(\lambda C \geq1\), then \(\delta\leq (\lambda C-1)^2\varepsilon/2(\lambda C)^{t_\varepsilon-1}\). An example of each situation is shown. Special attention is devoted to the ball walk problem in \(\mathbb R^n\) (which belongs to case a) in which a step is taken by uniformly choosing a point in a fixed radius ball centred at the current position \(x\).