Reachability for Markov process

2010-12-22T14:01:01Z

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<\infty] = 1$.

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)]? $$

Answer by Byron Schmuland for Reachability for Markov process

2010-12-23T13:41:34Z

It is right, and not so obvious.

The question of whether or not a Markov process hits particular sets is usually studied using the concept of capacity.

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.

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<\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}).$$

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).$

Therefore, $$\Pr[R(T,K)]\leq \mathbb{E}[I_A(X_{\tau\wedge T})]\leq \Pr[R(T,A)].$$

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.

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.

You can find more details in Chapter I, Section 10 of Blumenthal and Getoor's Markov Processes and Potential Theory, or in Section 3.3 of Kai Lai Chung's Lectures from Markov Processes to Brownian Motion.

Reachability for Markov process - MathOverflow

Reachability for Markov process

Answer by Byron Schmuland for Reachability for Markov process