# 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

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