Hitting times for random walks with restarts (Q2910933)

Let \((X_{n})_{n\geq 0}\) be an irreducible Markov chain on \(\mathbb Z^{d}\), \(d\geq 2\), with \(X_0=x\neq 0\). A walker moving in accordance with this chain, and having the goal of reaching \(0\) as quickly as possible, has the option (following some strategy) to restart by an instantaneous jump at \(x\). The minimum, over all restarting strategies, of the expected hitting time of \(0\) is denoted by \(\gamma(x,0)\). In a more general setting, it was called the grade of \(x\) by \textit{I. Dumitriu, P. Tetali} and \textit{P. Winkler} [SIAM J. Discrete Math. 16, No. 4, 604--615 (2003; Zbl 1032.60065)]. The main purpose of this paper is to establish several conjectures of these authors on the asymptotics of \(\gamma(x,0)\) as \(|x| \to \infty\). Namely, for \(d=2\) the present authors show that \(\gamma(x,0)=2|x|^2\log|x|+(2E+3\log2-1)|x|^2+O(|x|\log|x|)\) as \(|x| \to \infty\), where \(E\) is Euler's constant, while, for \(d\geq 3\), they prove that \(\gamma(x,0)=(V_{d}/p_{d})|x|^{d}+O(|x|^{d-1})\) as \(|x| \to \infty\), where \(V_{d}\) is the volume of the unit ball in \(\mathbb R^{d}\), and \(p_{d}\) is the escape probability of the simple random walk in \(\mathbb Z^{d}\). Analogous exact results for a continuous version of the problem, with \((X_{n})_{n\geq 0}\) replaced by the Brownian motion in \(\mathbb R^{d}\), is also presented.