Reachability for Markov process - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T17:07:34Z http://mathoverflow.net/feeds/question/50154 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50154/reachability-for-markov-process Reachability for Markov process Ilya 2010-12-22T14:01:01Z 2012-02-21T14:02:47Z <p>Let $X$ be a Markov process (in continuous or discrete time) and define an event $$R(T,A) = (\exists t\leq T: X_t \in A).$$ I have seen in one paper that $$\Pr[R(\infty,A)] = \sup\limits_{\tau} \mathbb{E}[I_A(X_\tau)],$$ where $I_A(x) = 1$ for $x\in A$ and $I_A(x)=0$ otherwise is an indicator function and supremum is taken over all stopping times $\tau:\Pr[\tau&lt;\infty] = 1$. </p> <p>Unfortunately the author did not provide a proof it, so I wonder is it right (and so obvious)? Also, does it imply that $$\Pr[R(T,A)] = \sup\limits_{\tau\leq T} \mathbb{E}[I_A(X_\tau)]?$$</p> http://mathoverflow.net/questions/50154/reachability-for-markov-process/50241#50241 Answer by Byron Schmuland for Reachability for Markov process Byron Schmuland 2010-12-23T13:41:34Z 2010-12-23T13:41:34Z <p>It is right, and not so obvious.</p> <p>The question of whether or not a Markov process hits particular sets is usually studied using the concept of capacity.</p> <p>For a continuous time parameter Markov process taking values in a general topological state space, this leads to non-trivial problems of measurability. For instance, for a Borel $A$ there is no guarantee that the set $R(T,A)\in{\cal F}$ where $(\Omega,{\cal F},\Pr)$ is the probability space. However, under suitable conditions, capacity theory can be used to show that $R(T,A)$ is universally measurable, and hence that $\Pr[R(T,A)]$ makes sense.</p> <p>Let's assume that the state space and process are "nice"; say, the state space is a locally compact, separable metric space, and the process has right continuous sample paths. For fixed $T&lt;\infty$, the formula $\phi(A)=\Pr[R(T,A)]$ defines a Choquet capacity on the Borel sets $A$. Therefore, $$\phi(A)=\sup(\phi(K): K\subseteq A,\ K\mbox{ compact}).$$</p> <p>For a compact $K$, define the stopping time $\tau(\omega):=\inf(t\geq 0: X_t(\omega)\in K)$. Since the sample paths of $(X_t)$ are right continuous and $K$ is closed, we have $R(T,K) = (X_{\tau\wedge T} \in K).$</p> <p>Therefore, $$\Pr[R(T,K)]\leq \mathbb{E}[I_A(X_{\tau\wedge T})]\leq \Pr[R(T,A)].$$</p> <p>Taking the supremum over compact subsets of $A$ gives $$\Pr[R(T,A)]=\sup_{\tau}\ \mathbb{E}[I_A(X_{\tau\wedge T})],$$ which gives your desired result. Letting $T\to\infty$ gives the infinite version.</p> <p>The result hinges on the fact that, as far as the process goes, the Borel set $A$ can be well approximated from the inside by compact sets.</p> <p>You can find more details in Chapter I, Section 10 of Blumenthal and Getoor's <em>Markov Processes and Potential Theory</em>, or in Section 3.3 of Kai Lai Chung's <em>Lectures from Markov Processes to Brownian Motion</em>.</p>