FIND ME ON

GitHub

LinkedIn

Hitting Time

🌱

Definition
StochasticProcesses

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

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

For each iSi\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).

1. The vector of hitting probabilities hA=(hiA,iS)h^A=(h^{A}_{i},i\in S) is a solution to the equations: xi=1,\mboxifiAxi=jSpijxj\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 (*), hiAxi,\mboxforeachiS\begin{align*}h^{A}_{i}\le x_{i}, & \mbox{ for each }i\in S\end{align*}

For iSi\in S, the expected time of hitting AA is κiA=Ei[TA]=E[TAX0=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”

1. The vector of expected hitting times κA=(κiA,iS)\kappa^{A}=(\kappa^{A}_{i},i\in S) is a solution to the equations:xi=0,\mboxifiAxi=1+jAcpijxj\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 (*), κiAxi,\mboxforeachiS\begin{align*}\kappa^{A}_{i}\le x_{i}, & \mbox{ for each }i\in S\end{align*}

Linked from