I got stuck on a question about proving a large deviation type upper bound. The questions is: Suppose $X_i$ are i.i.d random variables with finite moment generating functions. Let $H(\alpha) = \log Ee^{\alpha X_1}$ and $L(\beta) = \sup_{\alpha}[\alpha\beta - H(\alpha)]$. For $b \geq EX_1$, does \begin{equation} \lim\sup_{n\rightarrow\infty} \frac1n \log P\left(\max_{i=1,\cdots,n}\frac1nS_i\geq b\right) \leq -L(b) \end{equation} hold?

When $EX_1 \geq 0$, $\forall \alpha \geq 0$, we can construct a submartingale $Y_k = e^{\frac{\alpha}{n}S_k}$. As a result, we have \begin{equation} P\left(\max_{i=1,\cdots,n}\frac1nS_i\geq b\right) = P\left(\max_{i=1,\cdots,n}e^{\frac{\alpha}nS_i}\geq e^{\alpha b}\right) \leq \frac{Ee^{\frac{\alpha}{n}S_n}}{e^{\alpha b}} = \frac{e^{nH(\frac{\alpha}{n})}}{e^{\alpha b}} \end{equation} So \begin{equation} \frac1n \log P\left(\max_{i=1,\cdots,n}\frac1nS_i\geq b\right) \leq -\left(\frac{\alpha}n b - H\left(\frac{\alpha}{n}\right)\right), \forall \alpha \geq 0 \end{equation} Conseqently, \begin{equation} \frac1n \log P\left(\max_{i=1,\cdots,n}\frac1nS_i\geq b\right) \leq -\sup_{\alpha\geq 0}\left(\frac{\alpha}n b - H\left(\frac{\alpha}{n}\right)\right) = -\sup_{\alpha\geq 0}(\alpha b - H(\alpha)) = -L(b) \end{equation} The last equality holds because $b \geq EX_1$. But for the case where $EX_1 < 0$, $Y_k$ is no longer a submartingale, so this argument doesn't apply. I tried to convert this case to $EX_1 \geq 0$ case, but failed. Does anyone know how to prove this in this case? Thanks!

  • $\begingroup$ What happens if you apply the preceding result to $\bar X_k=X_k-E(X_1)$ and $\bar b=b-E(X_1)$? $\endgroup$ – Did Feb 19 '13 at 6:17
  • $\begingroup$ Please use \max and \sup. $\endgroup$ – Did Feb 19 '13 at 6:18
  • $\begingroup$ You can get appropriately sized parentheses by preceding them with \left and \right, respectively. Especially in displayed equations with display-style fractions that makes for much better visual impression and legibility. $\endgroup$ – joriki Feb 19 '13 at 7:57
  • $\begingroup$ @Did Then \begin{equation} P(\max_{i=1,\cdots,n}\frac1nS_i\geq b) = P(\max_{i=1,\cdots,n}(\frac1n\bar{S}_i + \frac{i}{n} EX_1)\geq b) \geq (\text{not $\leq$ since $EX_1 <0$, which is the problem})\ P(\max_{i=1,\cdots,n}\frac1n\bar{S}_i\geq \bar{b})\end{equation} $\endgroup$ – qitao Feb 19 '13 at 17:12
  • $\begingroup$ @joriki I fixed these issues. Thanks for the tips. $\endgroup$ – qitao Feb 19 '13 at 17:24

The large deviations principle fails in the regime of parameters $\mathbb E(X_1)<b<0$.

To see this, note that the event $A_n=\big[\max\limits_{1\leqslant i⩽n}S_i⩾nb\big]$ is a very probable event since the random walk $(S_i)_{i\geqslant1}$, even though it has a negative bias, starts from $X_1$ hence $\max\limits_{1\leqslant i⩽n}S_i$ is of order $1$ while $nb→−∞$. For example, $A_n⊇[X_1⩾nb]$ and $\mathbb P(X_1⩾nb)→1$ when $n→∞$.

  • $\begingroup$ This is a helpful observation. Thanks. I didn't see this before you pointed it out. However, I think it fails because we picked a $b<0$, and if we have $b>0$, it should still hold. Is this correct? I also edited the question to include this new problem. $\endgroup$ – qitao Feb 21 '13 at 14:10
  • $\begingroup$ One is not supposed to modify a question once one received answers, hence you might want to revert to the correct version of the question. $\endgroup$ – Did Feb 21 '13 at 15:21
  • $\begingroup$ Do you mean for this point that I'm still not clear about, I should post a new question, which will be almost exactly the same as this one? I happened to see your answer when you first post it, at which time it was still only a comment to my original question. I didn't have the time to reply to you at that time, but now I kind of regret it because if I did, you might not post such a strange comment. I think your answer is helpful, so I edited the question as you asked me to. But I think you care too much about things other than math. $\endgroup$ – qitao Feb 23 '13 at 0:44
  • $\begingroup$ Like the ways the site is supposed to function? Right, this is quite strange... $\endgroup$ – Did Feb 23 '13 at 6:12

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.