Expected hitting time

For a target set $A$, the expected hitting time $g(i)={\mathbb{E}}_i{T}_A$ satisfies $g=0$ on $A$ andoutside $A$, whenever the expectation is finite.

For a finite Markov chain, let $T$ be the first hitting time of $D$, assume $T<\infty$ almost surely, $f=0$ on $D$ and $Pf=f-\delta$ on its complement, with $\delta >0$. The stopped martingale $f(X_{n\wedge T})+\delta (n\wedge T)$ has mean $f(x)$. Boundedness of $f$ and bounded convergence theorem give $\mathbb{E}f(X_{n\wedge T})\to 0$; monotone convergence then gives the stated finite expected hitting time. No drift condition is required after entry into $D$.

Take two four-cycles, connect corresponding vertices, and connect each inner vertex to an absorbing hub. For the ordinary random walk on a graph, symmetry reduces mean remaining times to outer and inner types, satisfying $O=1+(2O+I)/3$ and $I=1+(O+2I)/4$. Thus $O=10$, $I=7$. For the non-backtracking random walk, directed-edge types outer-outer, outer-inner, inner-outer and inner-inner give remaining means $13/2,9/2,15/2,21/4$. Starting at an outer vertex, the first-step distribution yields total mean $41/6$.

For simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

On $\{1,\dots ,n\}$, make $1$ an absorbing state and let each state $i>1$ move uniformly to $\{1,\dots ,i-1\}$. Its expected hitting time of $1$, allowing zero time when started at $1$, is $e_i=H_{i-1}$. First-step analysis gives $e_i=1+(i-1{)}^{-1}{\sum }_{j<i}{e}_j$; subtracting consecutive recurrences yields $e_i-e_{i-1}=1/(i-1)$ and hence the formula.