NAVIGATION

Home

Research

Bookshelf

Garden

FIND ME ON

GitHub

LinkedIn

Email

Home

Research

Bookshelf

Garden

Created by Knut M. Synstadfrom the Noun Project

Hitting Time

Definition (Hitting Time)

Let (Xn)n≥0(X_n)_{n\ge0} be a Markov chain with the state space SS and Transition Kernel PP. Let A⊂SA\subset S be a subset of interest, and TAT^A the first time that the MC hits the set A: TA(ω)=inf⁡{n≥0:Xn(ω)∈A}T^A(\omega)=\inf\{n\ge0:X_n(\omega)\in A\}

Proposition (Properties of hitting times)

  1. TAT^{A} takes values from {0,1,⋯ }\{0,1,\cdots\}
  2. {TA=n}={X0∉A,⋯ ,Xn−1∉A,Xn∈A}\{T^{A}=n\}=\{X_{0}\not\in A,\cdots,X_{n-1}\not\in A,X_{n}\in A\}
  3. {TA≠n}={(X0,⋯ ,Xn)∈Bnc}\{T^{A}\not=n\}=\{(X_0,\cdots,X_{n})\in B_{n}^{c}\}

Definition (Hitting probability)

For each i∈Si\in S, denote the probability of hitting AA starting from position ii by hiA=P(TA<∞∣X0=i)h^A_{i}=P(T^A<\infty|X_0=i)where TAT^A is the hitting time for event AA. For simplicity, we will write PiP_i for P(⋅∣X0=i)P(\cdot|X_0=i).

Theorem (System of Equations for Hitting Probability)

  1. The vector of hitting probabilities hA=(hiA,i∈S)h^A=(h^{A}_{i},i\in S) is a solution to the equations: xi=1,\mboxifi∈Axi=∑j∈Spijxj\mboxifi∉A\begin{align*}&x_{i}=1,&\mbox{if }i\in A \\\tag{*}&x_{i}=\sum\limits_{j\in S}p_{ij}x_{j}&\mbox{if }i\not\in A \\\end{align*}
  2. hAh^{A} is the minimal non-negative solution to (*) in the sense that for any other non-negative solution xx to (*), hiA≤xi,\mboxforeachi∈S\begin{align*}h^{A}_{i}\le x_{i}, & \mbox{ for each }i\in S\end{align*}

Definition (Expected hitting time)

For i∈Si\in S, the expected time of hitting AA is κiA=Ei[TA]=E[TA∣X0=i]\begin{align*} \kappa_{i}^{A}&=E_{i}[T^{A}]\\ &=E[T^{A}|X_{0}=i] \end{align*}where TAT^{A} is the hitting time of event AA. By definition we have κi=∑n<∞nPi(TA=n)+∞∗Pi(TA=∞)\kappa_{i}=\sum\limits_{n<\infty}nP_{i}(T^{A}=n)+\infty*P_{i}(T^{A}=\infty) If the probability of not hitting the set AA from state ii is positive, then κi=∞\kappa_{i}=\infty.

  • i.e. if hitting probability hi=1h_{i}=1 then κi<∞\kappa_{i}<\infty or “if we’re for sure hitting A then we have a expected hitting time”
  • i.e. if hitting probability hi<1h_i<1 then κi=∞\kappa_{i}=\infty or “if we’re not hitting A for sure then expected hitting time is infinite”

Theorem (System of Equations for Expected Hitting Time)

  1. The vector of expected hitting times κA=(κiA,i∈S)\kappa^{A}=(\kappa^{A}_{i},i\in S) is a solution to the equations:xi=0,\mboxifi∈Axi=1+∑j∈Acpijxj\mboxifi∉A\begin{align*}&x_{i}=0,&\mbox{if }i\in A \\\tag{*}&x_{i}=1+\sum\limits_{j\in A^{c}}p_{ij}x_{j} &\mbox{if }i\not\in A \\\end{align*}
  2. κA\kappa^{A} is the minimal non-negative solution to (*) in the sense that for any other non-negative solution xx to (*), κiA≤xi,\mboxforeachi∈S\begin{align*}\kappa^{A}_{i}\le x_{i}, & \mbox{ for each }i\in S\end{align*}

Linked from

Hitting Time

Passage Time

Stopping Time