Is it easy to write down the large deviations rate for the maximizer of a random walk with negative drift?

Let $X_i$ be the (iid, mean $-\mu$, variance $\sigma$, arbitrarily nice tails) jumps of a random walk $S_i$. I am interested in the location of the maximum of $S_i$, i.e. in $\arg\max_k S_k$. (If $X_i$ are continuous, the maximizer is almost surely unique.)

There's a trivial exponential upper bound $$ \mathbb{P}(\arg\max_k(S_k) > n) \leq \mathbb{P}(S_{n+1} > 0) = \mathbb{P}(\sum_{i=1}^n X_i > 0) $$ and the trivial exponential lower bound $$ \mathbb{P}(\arg\max_k(S_k) > n) \geq \mathbb{P}(X_i > 0\ \forall i \leq n) $$ and they (of course) don't match. Is there a limit $$ \lim_{n \to \infty}n^{-1}\log\mathbb{P}(\arg\max_k(S_k) > n), $$ and is it possible to write it down in terms of the distribution of the jumps $X_i$?

  • $\begingroup$ The answer of course depends on the tail assumptions for the $X_i$s. Do they have exponential tails? In that case, you have a $\log$ missing in your question, and the answer can be read off large deviations for the maximum (which are covered by e.g. Iglehart's 1972 paper). $\endgroup$ Dec 7, 2014 at 22:58
  • $\begingroup$ Thank you, Ofer! Yes, of course, it should be $\log\mathbb{P}(...)$. $\endgroup$ Dec 10, 2014 at 16:29
  • $\begingroup$ The system won't let me write a comment cause I'm a new user, so I'll write an answer instead. I have a question in the OP, in the upper bound part, why is it that $$\mathbb{P}(\arg \max_k (S_k)>n)\leq\mathbb{P}(S_{n+1}>0)$$ I don't quite get that part... Any help would be appreciated :-) $\endgroup$
    – Oliver
    May 15, 2017 at 15:42
  • $\begingroup$ I don't remember if I had a better reason three years ago, but it would definitely true as $\mathbb{P}(\text{arg max}_k(S_k) = n) \leq \mathbb{P}(S_{n+1} > 0)$, which should be close enough from a large deviations standpoint. $\endgroup$ May 16, 2017 at 21:57

1 Answer 1


The upper bound gives the correct large deviations; that is, the answer is $$n^{-1}\log P(\mbox{ arg max}_k S_k>n)\to -I(0)\,,$$ where $I(0)=-\inf_\lambda \log E(e^{\lambda X_1})$.

The upper bound appears in the OP. For the lower bound, just consider the event $$ {\cal A}_n:=\{S_n\geq \epsilon n \}$$ and note that $P(\mbox{ argmax}_k S_k <n(1-\delta)|{\cal A}_n)$ goes to $0$ as $n\to\infty$ if $\delta>>\epsilon$ (but both small). But $n^{-1}\log P({\cal A}_n)\to-I(\epsilon)$. Now use the continuity of $I$ in $\epsilon$ (here you need to assume something on the tails; finite logarithmic mgf is enough).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.