On the approximation of one Markov chain by another (Q818819): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Mark R. Jerrum / rank | |||
Property / author | |||
Property / author: Mark R. Jerrum / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1973958076 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0312340 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3660628 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Biased random walks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4870855 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the linear programming approach to the optimality property of Prokhorov's distance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4798347 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Random walks in a convex body and an improved volume algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3999495 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Perturbation Theory for Ergodic Markov Chains and Application to Numerical Approximations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Existence of Probability Measures with Given Marginals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4333039 / rank | |||
Normal rank |
Latest revision as of 12:17, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the approximation of one Markov chain by another |
scientific article |
Statements
On the approximation of one Markov chain by another (English)
0 references
21 March 2006
0 references
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\).
0 references
0 references