For a target set , the Expected hitting time satisfies on and
outside , whenever the expectation is finite.
For a finite Markov chain, let be the first hitting time of , assume almost surely, on and on its complement, with . The stopped martingale has mean . Boundedness of and bounded convergence theorem give ; monotone convergence then gives the stated finite expected hitting time. No drift condition is required after entry into .
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 and . Thus , . For the non-backtracking random walk, directed-edge types outer-outer, outer-inner, inner-outer and inner-inner give remaining means . Starting at an outer vertex, the first-step distribution yields total mean .
For simple random walk on two disjoint complete graphs of size joined through one new vertex , let be the expected hitting time of from either vertex attached to , and the expected hitting time from any other clique vertex. First-step analysis gives and , so and . The expected hitting time from is zero. In discrete time the random walk is an aperiodic Markov chain only for .
On , make an absorbing state and let each state move uniformly to . Its expected hitting time of , allowing zero time when started at , is . First-step analysis gives ; subtracting consecutive recurrences yields and hence the formula.

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.