## Reachability for Markov process

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

It says that if you blindfold someone moving at random and tell him when to stop and look, his chance to see a cow will be less than his chance to see it if he roams forever with open eyes but you can come close if you tell him to stop the first time you see a cow nearby or after a very long time whichever comes first. I doubt I can make it more obvious than that.  The supremum can actually be taken over all stop-functions, but stopping times are enough to achieve it. As always, there are some measurability issues with continuous time, but, I guess, they are taken care of in the paper. – fedja Dec 22 2010 at 15:51
It's not a proof ) – Ilya Dec 22 2010 at 16:01
What particular phrase do you have difficulty with when translating back into the formal language?   – fedja Dec 22 2010 at 18:52
That's an interesting way of phrasing this. Have you tried it for longer arguments? – Omer Dec 22 2010 at 19:21
Haha, have you mentioned that the definition of $R(T,A)$ does not coincide with the definition of $I_A(X_\tau)$. Of course you can say it's obvious that if two triangles have the same sides, they are equal - but maybe you remember that this simple fact also need to be proved.  – Ilya Dec 23 2010 at 8:49
show 2 more comments

## 1 Answer

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.

-

Thank you very much, I have proved in the almost same way yesterday for the finite time $T$. I'm just wondering if it is admissible to state that we can put T\to \infty\$ and say that it is a proof for the infinite time horizon? – Ilya Dec 23 2010 at 13:58
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9446962475776672, "perplexity_flag": "head"}