Large deviations for the range of an integer valued random walk (Q1599996): Difference between revisions

Let \(X, X_1, X_2, \ldots \) be i.i.d. integer-valued random variables with \(P(X=0) < 1\) and consider the corresponding random walk \((S_n)\) with \(S_0 =0\) and \(S_n = \sum_{i=1}^n X_i\), \(n= 1, 2, \ldots \). The range \(R_n\) of the random walk is the number of different points among \(\{0, S_1, S_2, \ldots \}\). It is well-known that \(R_n/n\) converges almost surely to \(r\), where \(r:= P(S_n \neq 0 \text{ for all } n \geq 1)\) is the escape probability of the random walk. The authors prove that, for \(x\geq 0\), \(\psi(x): = -\lim_n \frac{1}{n} \log P(R_n \geq nx)\) exists, and has the following properties: \(\psi(x) =0\) for \(x\leq r\), \(0< \psi(x) < \infty\) for \(r< x \leq 1\), \(\psi(x) = \infty\) for \(x > 1\), and \(\psi(x)\) is continuous on \([0,1]\). If the tail of the random variable \(X\) satisfies \(\limsup (P(|X|\geq n)^{1/n} =1\), then \(\psi\) is also convex on \([0,1]\). This paper extends results given by the same authors for random walks on \(Z^d\), \(d \geq 2\).