# Proving a Large Deviation type Upper Bound

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 $$\lim\sup_{n\rightarrow\infty} \frac1n \log P\left(\max_{i=1,\cdots,n}\frac1nS_i\geq b\right) \leq -L(b)$$ 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 $$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}}$$ So $$\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$$ Conseqently, $$\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)$$ 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!

-
What happens if you apply the preceding result to $\bar X_k=X_k-E(X_1)$ and $\bar b=b-E(X_1)$? –  Did Feb 19 '13 at 6:17
Please use \max and \sup. –  Did Feb 19 '13 at 6:18
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. –  joriki Feb 19 '13 at 7:57
@Did Then $$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})$$ –  qitao Feb 19 '13 at 17:12
@joriki I fixed these issues. Thanks for the tips. –  qitao Feb 19 '13 at 17:24

## 1 Answer

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→∞$.

-
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. –  qitao Feb 21 '13 at 14:10
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. –  Did Feb 21 '13 at 15:21
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. –  qitao Feb 23 '13 at 0:44
Like the ways the site is supposed to function? Right, this is quite strange... –  Did Feb 23 '13 at 6:12