3
$\begingroup$

Let $(X_t)_{t\in\mathbb{R}\geqslant 0}$ be a Markov Jump Process on a discrete state space $S\cup \{0\}$, with $0$ an absorbing state. If $T_0$ is the hitting time of $0$, I want to prove that

$$ \mathbb{P}_x(T_0<+\infty)=1$$

knowing these facts:

1) For some (finite) neighbourhood of $0$, say $C$, $\mathbb{P}_x(T_C<+\infty)=1\ \ \forall x \notin C$

2) For all $x\in C$, there's a positive probability $p_x$ of eventually reaching $0$,starting from $x$ (This implies there's a uniform probability $p>0$ of reaching $0$ from any state in $C$,as $C$ is finite).

The strategy would be to bound $T_0$ from above, by a Geometric (with parameter $q:=1-p$) sum of iid variables $T_C^{(i)}$ plus the times spent inside $C$.

I would like to write this idea properly. Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Your conditions 1) and 2) imply that the chain is Harris-recurrent in the sense of Definition 6.1.1 in Glynn. By Remark 6.1.1 there, there exists $z\in S$ such that $P_x(\tau(z) < \infty$) = 1 for $x\in S$, where $\tau(z) = \inf\{n\ge1 : X_n = z\}$. From that, your desired conclusion, $P_x(T_0<\infty)=1$, follows immediately. Indeed, $0$ is absorbing and hence $z$ is necessarily $0$, since for any $z\ne0$ one has $P_0(\tau(z)<\infty)=0\ne1$.

However, I do not know how to prove the mentioned remark; perhaps you can ask Peter Glynn about that.

Theorem 14.2.7 in Athreya and Lahiri seems of relevance here, but you seem to lack condition (2.15) in that theorem (which may be somehow established, though).

$\endgroup$
  • $\begingroup$ From what I understand, for conditions 1) and 2) to imply Harris Recurrence, I need to work a little bit, here's what I think I would need to do: $\endgroup$ – Max Oct 10 '17 at 14:10
  • $\begingroup$ a) As this chain is in continuous time, take $(Y_n)$ the jump chain. Then b) Condition 1 holds c) For condition 2) take $\varphi=\delta_0$ and $\lambda=p$. And $m$ (here I'm not sure) would be the maximum of $m_x$, $x\in C$ (where $m_x$ is such that $p_{x0}^{(m_x)}>0$). Is this what you thought? $\endgroup$ – Max Oct 10 '17 at 14:17
  • $\begingroup$ And a technicality: Is $\tau(z)$ well defined under $\mathbb{P}_z$ , when $z$ is an absorbing state? $\endgroup$ – Max Oct 10 '17 at 15:42
  • $\begingroup$ Before your editing the question, I somehow perceived that you deal with a discrete-time process. For $m$ (according to Glynn's presentation), one can indeed take $\max_{x\in C}m_x$, because $p_{x0}^{(m_x)}>0$ implies $p_{x0}^{(n)}>0$ for all $n\ge m_x$, since $0$ is absorbing. Also, I don't see a problem with the definition of $\tau(z)$, as it is defined path-wise, without involving any probability measure. $\endgroup$ – Iosif Pinelis Oct 10 '17 at 20:36
1
$\begingroup$

I see no difference between working with the continuous time process and discrete-time process for this problem. Hence, to mitigate the unnecessary burden of notation, the rest of the work will be presented as the problem is posed for discrete time process.

Denote that:

  • $ S'=S\cup \{ 0 \}$

  • $C=\{ c_1,c_2,..,c_n\}$

  • $ \mathcal{ D}(S'), \mathcal{ D}(C) $ are family of all positive distributions over $S'$ and $C$ , respectively.

  • $m(t,V) = \mathbb{P}_{V}( X^t=0 ) $ for $ t \in \mathbb{N}, V \in \mathcal{D}(C)$

  • $m(t) = \inf_{ V \in \mathcal{D}(C) } m(t,V)$

  • $P$ is the transition matrix of the chain.

Before the demonstration of the problem, we start with some propositions

Firstly with those concerning $m(t)$

Proposition 1: For all $t \in \mathbb{N}$ , $\begin{array}{lccl} m_t : & \mathcal{D}(C) & \rightarrow & \mathbb{R} \\ &V & \mapsto& m(t,V) \end{array} $ is an affine function.

Demonstration 1 If each distribution represented as a stochastic row vector, $m(t,V) $ is indeed equal to $ VP^t\delta_0^T$ .QED

Proposition 2: For each $t$, the infimum in the definition of $m(t)$ is achievable, ie. $ \exists \mu_t \in \mathcal{D}(C) : m(t) = m(t, \mu_t)$.

Demonstration 2 Following from the previous proposition, in looking for the infimum of $m(t,V)$ over $\mathcal{D}(C)$, we are minimizing a continuous function over a compact set ( $ dim( \mathcal{D}(C) ) < \infty $ as $ |C| <\infty$ ). It therefore has a minimum.

Remark 1: As $m_t$ is affine, it is reasonable to even suppose that $\mu_t = \delta_{d_t} $ for some $ d_t \in C$.

Proposition 3: $( m(t) )_{t \in \mathbb{N}}$ is an increasing sequence.

Demonstration 3 The proposition 2 and the fact that $0$ is an absorbing state imply :

$m(t+1) = m(t+1, \mu_{t+1}) = \mathbb{P}_{\mu_{t+1}}( X^{t+1} =0)$

$ \ge \mathbb{P}_{\mu_{t+1}}( X^{t} =0) \ge \min_{\mu \in \mathcal{D}(C)} \mathbb{P}_{\mu}( X^{t} =0) =m(t)$ . QED

Then, some proposition for estimation.

Proposition 4: $ \exists p> 0 $ and $N \in \mathbb{N}$ such that : $ \mathbb{P}_{U}(X^N =0)>p $ for all $U \in \mathcal{D}(C)$ ,ie :

$ m(N) >p$.

Demonstration 4 The second condition of the problem shows that for each $ i \in \mathbb{1,n}$ , there is $p_i>0$ and $N_i>0$ such that :

$\mathbb{P}_{c_i}( X^{N_i} =0 ) > p_i$

Choose $ p= \min( p_1,p_2,..,p_n); N=\max(N_1,N_2,..,N_n)$, using the fact that $0$ is an absorbing state, we deduce that:

$\mathbb{P}_{c}( X^{N} =0 ) > p \forall c \in C$

Therefore, QED.

And the last ingredient,

Proposition 5: $\lim_{ t \rightarrow \infty} m(t) = \inf_{ \mu \in \mathcal{D}(C) } \lim_{t \rightarrow \infty} \mathcal{P}_{\mu}(X^t = 0)= I $

Demonstration 5:

As $0$ is an absorbing state, for all $ \mu \in \mathcal{D}(C) $, $ ( \mathcal{P}_{\mu}(X^t = 0) )_{t \ge 0 }$ is an increasing state.

Therefore, $ \lim_{t \rightarrow \infty} \mathcal{P}_{\mu}(X^t = 0) \ge \mathcal{P}_{\mu}(X^n = 0) \ge m(n) \forall n$

$\Rightarrow RHS \ge LHS$

On the other hand, following the remark 1 , and the fact that $|C| $ is finite, we deduce that :

$\exists$ an strictly increasing sequence of natural numbers $(n_i)_{i \ge 0}$ and a state $c^* \in C$ such that:

$ m(n_i) = m(n_i, \delta_{c^*} ) = \mathbb{P}_{\delta_{c^*} }( X^{n_i} =0)$

As $(m(t))_{t \ge 0}$ is an strictly increasing sequence, we also deduce: $\Rightarrow \lim_{t \rightarrow \infty} m(t) = \lim_{t \rightarrow \infty} \mathbb{P}_{\delta_{c^*} }( X^{t} =0) \ge \inf_{ \mu \in \mathcal{D}(C) } \lim_{t \rightarrow \infty} \mathcal{P}_{\mu}(X^t = 0) $

$\Rightarrow LHS \ge RHS$

QED.

Let's begin the main demonstration

Demonstration

For all $t>0$ , $ \mu \in \mathcal{D}_{C}$ and the fact that $0$ is an absoribng state (*) , we have:

  • $ \mathbb{P}_{\mu} (X^{N+t} =0) >p$ ( $N,p$ are defined as in the Proposition 3)

  • Take $V \in \mathcal{D}(S' )$ such that $ \mathbb{P}_{\mu} (X^{N} =s |X^N \ne 0 )= \mathbb{P}_{V}( X_0=s)$

    $\Rightarrow \mathbb{P}_{\mu} (X^{N+t} =0 |X^N \ne 0 )= \mathbb{P}_{V}( X^t=0) \forall t $

From those, we deduce:

$ \mathbb{P}_{\mu} (X^{N+t} =0) \ge p+(1-p) \mathbb{P}_{V} (X^{t} =0)$ (1)

On the other hand, we have:

  • $ \mathbb{P}_{V} (X^{t} =0) = \sum_{i\ge 0 }^t \mathbb{P}_{V} (X^{t} =0 | T_{C} =i) \mathbb{P}_{V}( T_{C} =i)= E$

    Choose $\mu_i \in \mathcal{D}(C) $ such that:

    • $ \mathbb{P}_{V} (X^{t} =0 | T_{C} =i) =\mathbb{P}_{ \mu_i }( X^{t-i}=0)$( the same way we chose V )

    Therefore,

    $ E= \sum_{i\ge 0 }^t \mathbb{P}_{\mu_i } (X^{t-i} =0 ) \mathbb{P}_{V}( T_{C} =i) \ge \sum_{i\ge 0 }^t m(t-i) \mathbb{P}_{V}( T_{C} =i) $ (2)

From (1) and (2) , we get:

$\mathbb{P}_{\mu} (X^{N+t} =0) \ge p+(1-p)( \sum_{i\ge 0 }^t m(t-i) \mathbb{P}_{V}( T_{C} =i)) $

Take the limit and do some calculations,

$ \lim_{ t \rightarrow \infty} \mathbb{P}_{\mu} (X^{t} =0) \ge p+(1-p)( I ( \sum_{i\ge 0 }^t \mathbb{P}_{V}( T_{C} =i) )$

$ = p+(1-p)I (\mathbb{P}_{V}( T_C<\infty))$

$ = p+(1-p)(I \sum_{s \in S'} \mathbb{P}_{s}( T_C<\infty)\mathbb{P}_V ( X_0=s'))$

$ = p+(1-p)(I \sum_{s \in S'} \mathbb{P}_V ( X_0=s'))$ (first condition)

$ = p+(1-p)I$

Then take the infimum.

$\Rightarrow I \ge p+(1-p)I \Rightarrow I=1$

Therefore, $ \forall \mu \in \mathcal{D}(C) : \lim_{t \rightarrow \infty} \mathbb{P}_{\mu}(X^t = 0)=1$

Which gives $ \mathbb{P}_{\mu}( T_0 < \infty)=1$.()**

Finally, $\forall x \in S'$, we have:

$ \mathbb{P}_{x}( T_0 < \infty) \ge \sum_{i \ge 0 } \mathbb{P}_{x}( T_0 < \infty | T_C = i) \mathbb{P}_{x}( T_C=i) $

$ =^{**} \sum_{i \ge 0 } 1. \mathbb{P}_{x}( T_C=i) = \mathbb{P}_{x}( T_C< \infty)=1$ Q.E.D

$\endgroup$
  • $\begingroup$ How do you get "that $\exists M \in \mathbb{N}: \mathbb{P}_{U} ( X_M \in C ) \ge 1 -\epsilon$"? $\endgroup$ – Iosif Pinelis Oct 11 '17 at 0:27
  • $\begingroup$ Yeah, it requires some work and I didn't state it clearly. $\endgroup$ – Taro NGUYEN Oct 12 '17 at 18:06
  • $\begingroup$ Without loss of generality, as $S$ is countable, we can represent $S'=S\cup \{0\} =\{ s_0,s_1,...,s_n,..\} $ . Because $U$ is a distribution over $S'$, $\exists n \in \mathbb{N} $ such that : $ \sum_{i=0}^{n} \mathbb{P}_{U}( X_0= s_i) > 1-\frac{\epsilon}{2}$ . On other hand, from the first condition , $ \exists M \in \mathbb{N} : \mathbb{P}_{s_i} ( X_M \in C) > 1-\frac{\epsilon{2} \for i \in \overline{0,n}$ ; from which we get the above proposition. $\endgroup$ – Taro NGUYEN Oct 12 '17 at 18:13
  • $\begingroup$ And how do you show that "$\exists M \in \mathbb{N} : \mathbb{P}_{s_i} ( X_M \in C) > 1-\frac\epsilon{2} \text{ for } i \in \overline{0,n}$"? This latter version indeed seems very close to the previous one, which was quite unclear to me: "that $\exists M \in \mathbb{N}: \mathbb{P}_{U} ( X_M \in C ) \ge 1 -\epsilon$". The same $M$ for all $s_i$, and with probability $> 1-\frac\epsilon{2}$? I have no idea how to get this. $\endgroup$ – Iosif Pinelis Oct 12 '17 at 19:57
  • 1
    $\begingroup$ Yeah, I did it again, and all wrote down explicitly. $\endgroup$ – Taro NGUYEN Oct 14 '17 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.