Hitting times for random walks with restarts

Details Hitting times for random walks with restarts Hitting times for random walks with restarts

2010-05-24

arxiv.org/abs/1005.4275v1

Mathematics

Probability

12 pages

Scientific paper

The time it takes a random walker in a lattice to reach the origin from another vertex $x$, has infinite mean. If the walker can restart the walk at $x$ at will, then the minimum expected hitting time $T(x,0)$ (minimized over restarting strategies) is finite; it was called the ``grade'' of $x$ by Dumitriu, Tetali and Winkler. They showed that, in a more general setting, the grade (a variant of the ``Gittins index'') plays a crucial role in control problems involving several Markov chains. Here we establish several conjectures of Dumitriu et al on the asymptotics of the grade in Euclidean lattices. In particular, we show that in the planar square lattice, $T(x,0)$ is asymptotic to $2|x|^2\log|x|$ as $|x| \to \infty$. The proof hinges on the local variance of the potential kernel $h$ being almost constant on the level sets of $h$. We also show how the same method yields precise second order asymptotics for hitting times of a random walk (without restarts) in a lattice disk.

Affiliated with

Also associated with

No associations

Rating

Hitting times for random walks with restarts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hitting times for random walks with restarts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hitting times for random walks with restarts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-118912