1
$\begingroup$

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$?

$\endgroup$
  • $\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$ – ofer zeitouni Dec 7 '14 at 22:58
  • $\begingroup$ Thank you, Ofer! Yes, of course, it should be $\log\mathbb{P}(...)$. $\endgroup$ – Elena Yudovina Dec 10 '14 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 '17 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$ – Elena Yudovina May 16 '17 at 21:57
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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