18 - Characterisation of Hitting Probabilities

Characterisation of Hitting Probabilities

Vector of Hitting Probabilities $(h_i^A,i\in I)$ is minimal non-negative solution to equations

$$h_i^A=\{\begin{array}{ll}1& \text{ if }i\in A\\ \sum _j{p}_{ij}{h}_j^A& \text{ if }i\notin A\end{array}$$

Note that minimal means that if $(x_i,i\in I)$ is another non-negative solution to system then $h_i\le x_i$ for all $i$

Proof

If $i\in A$ then $h_i^A=1$

Otherwise if $i\notin A$ then

$$\begin{array}{rl}{h}_i^A& ={\mathbb{P}}_i(X_n\in A\text{ for some }n\ge 0)\\ & ={\mathbb{P}}_i(X_n\in A\text{ for some }n\ge 1)\\ & =\sum _j{\mathbb{P}}_i(X_1=j)\mathbb{P}(X_n\in A\text{ for some }n\ge 1\mid X_0=i,X_1=j)\\ & =\sum _j{p}_{ij}\mathbb{P}(X_n\in A\text{ for some }n\ge 1\mid X_1=j)\\ & =\sum _j{p}_{ij}{h}_j^A\end{array}$$

Let $(x_i,i\in I)$ be any non-negative solution then
Prove by induction on $M$: For any $M\in \mathbb{N}$ and for all $i\in I$ then

$$x_i\ge {\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)$$

For $M=0$ then

$$\text{LHS is }1\text{ for }i\in A\text{ and }\text{RHS is }0\text{ for }i\notin A$$

So it holds for $M=0$

Induction Step so suppose

$$x_i\ge {\mathbb{P}}_i(X_n\in A\text{ for some }n\le M-1)\text{ for all }i\in I$$

If $i\in A$ then $x_i=1$ so holds
Otherwise If $i\notin A$ then

$$\begin{array}{rl}{\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)& =\sum _j{p}_{ij}{\mathbb{P}}_i(X_n\in A\text{ for some }n\in \{1,2,\cdots M\}\mid X_1=j)\\ & =\sum _j{p}_{ij}{\mathbb{P}}_j(X_n\in A\text{ for some }n\in \{0,1,\cdots ,M-1\})\\ & \le \sum _j{p}_{ij}{x}_j\\ & =x_i\end{array}$$

Hence induction step is complete

So statement holds for all $i$ and $M$

So as sequence of events $x_i\ge {\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)$ is increasing in $M$ then

$$\begin{array}{rl}{x}_i& \ge \underset{M\to \infty }{\lim }{\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)\\ & ={\mathbb{P}}_i\left(\bigcup _M\{X_n\in A\text{ for some }n\le M\}\right)\\ & ={\mathbb{P}}_i(X_n\in A\text{ for some }n)\\ & =h_i^A\end{array}$$