Let $Z\_i$ be i.i.d. random variables with $\mathbb{E}[Z\_i] = 0$ and $\mathbb{E}|Z\_i|^p< \infty$ for $p=1,2,3,\cdots$. I am looking for the following type of estimate if possible, and it is not like the concentration inequalities that one normally sees. 



> 
> There exists $N\_0$ sufficiently large and $t\_0$ sufficiently small
>  such that for all $N\geq N\_0$ and $1/N<t\leq t\_0$, we have $$\mathbb{P}
>  \left\{\max\_{1 \leq k \leq N} \left( \frac{1}{k}\sum\_{i=1}^k Z\_i
>  \right)\leq t \right\} \leq C t^\alpha$$ or equivalently $$\mathbb{P}
>  \left\{\max\_{1 \leq k \leq N} \sum\_{i=1}^k Z\_i
>  - tk \leq 0 \right\} \leq C t^\alpha. \quad (\star)$$
> 
> 
> 


(I know the distributions of $Z\_i$'s, if this is helpful). 


Is there a name for this type of inequality where we look at the maximum of the averages (or the sum of i.i.d. random variables but we can not move the constant to the other side, like in $\star$ above).


I found a related general results in [this](https://www.ams.org/journals/tran/1948-064-02/S0002-9947-1948-0026274-0/S0002-9947-1948-0026274-0.pdf) paper by Chung (page 2); here the mean zero random variables are only assumed to be independent. With his notation, $S\_n^\* = \max\_{1\leq k\leq n} |S\_n|$, and $s\_n = \text{Var}[S\_n]$ which is $Cn$ in the i.i.d. case, we have


**Theorem 2.** If $g\_n \downarrow 0$ and 
$$g\_n^{-1} = O((\log\_2 s\_n)^{1/2})$$
then we have 
$$\mathbb{P}(S\_n^\* < g\_ns\_n) = (1+o(1)) \exp\left(-\frac{\pi^2}{8g\_n^2}.\right)$$


Is there a simpler inequality of this type for i.i.d. random variables? The proof of this inequality in his general setting is quite technical.


**Background:**
The original event that I was trying to estimate is 
$$\left\{\inf\_{1\leq k \leq tN} \sup\_{tN
 \leq l \leq N}\sum\_{i=k+1}^l X\_i - Y\_i \leq 0\right\}$$
where $X\_i \sim \exp(\rho)$, and $Y\_i \sim \exp(\rho- t)$ all independent of each other. 


Like Kolmogorov or Doob's maximal inequality, maybe it is helpful to center the random variables; by defining
$Z\_i = X\_i - Y\_i - \mathbb{E}[X\_i - Y\_i] $, we get the centered version 
$$\left\{\inf\_{1\leq k \leq tN} \sup\_{tN
 \leq l \leq N}\sum\_{i=k+1}^l \left(Z\_i - \frac{t}{\rho(\rho-t)} \right) \leq 0 \right\},$$
and this boils down to estimate $$\mathbb{P} \left\{\inf\_{1\leq k \leq tN} \sup\_{tN
 \leq l \leq N} \left( \frac{1}{l-k}\sum\_{i=k+1}^l Z\_i \right)\leq t
 \right\} \leq C t^\alpha$$
for some positive $C, \alpha$.


**Final remark:**
One way to get some kind of tail estimate is to go to Brownian motion using Donsker's theorem, and we could obtain 
$$\limsup\_{N\rightarrow \infty} \mathbb{P} \left\{\inf\_{1\leq k \leq tN} \sup\_{tN
 \leq l \leq N} \left( \frac{1}{l-k}\sum\_{i=k+1}^l Z\_i \right)\leq t
 \right\} \leq C t^\alpha$$ for all $t\in (0, t\_0)$. In this case, the $N\_0$ would be dependent on $t$ so instead of $``N\geq N\_0"$ we have to use $``\limsup\_N"$, and I am trying to avoid this.



Maximal inequality for the average of i.i.d. random variables
I streamlined my proof a bit so it is postable now :-)


First, a disclaimer. I have no doubt that there is some slick theorem dating back to 1980's that immediately implies what you want and all one needs is to wait for a while until someone posts a reference to it. Meanwhile, here is a crude computation that gives a rather dismal value of $\alpha$ but still provides a reasonably clear idea of why such estimates should hold.


Let's normalize $Z$ to $E[Z^2]=1$ (as I said in the remarks, some normalization is necessary).


We fix a few parameters now. Let $\delta>0$ be any number such that the probability that the standard Gaussian random variable is less than $\delta$ is strictly less than $q=\frac 23$, say. Fix $b\in(0,\frac 12)$ and an integer $A\ge 2$ to be chosen later. Split the natural numbers $1,2,3,\dots$ into intervals $J\_k$ of length $|J\_k|=A^k$ from left to right (so $J\_1=\{1,\dots,A\}, J\_2=\{1+A,\dots, A+A^2\}, J\_3=\{1+A+A^2,\dots,A+A^2+A^3\}$ and so on). Consider 
$$
W\_k=\sum\_{j\in J\_k}Z\_j
$$
where $k$ runs from $1$ to $K$ with $K$ being the largest number satisfying 
$$
2 A^K t\le b A^{K/2}
$$
Notice that then $A^K\approx t^{-2}$ so we have all the corresponding intervals $J\_k$ in the range $[1,N]$ if $t\ge N^{-1/2}$. However, if we cover this range, we can then easily extend it to the required range $t>\frac 1N$ by just decreasing the value of $\alpha$ twice. Also $K\approx \frac{\log\frac 1t}{\log A}$ for small $t$.


Now, the event we are interested in is a subset of the event
$$
W\_1\le bA^{1/2}, W\_1+W\_2\le b A^{2/2},\dots, W\_1+\dots+W\_K\le bA^{K/2}\,.
$$
We shall prove by induction that the event 
$$
E\_k=\{W\_1\le bA^{1/2}, W\_1+W\_2\le b A^{2/2},\dots, W\_1+\dots+W\_k\le bA^{k/2}\}
$$
has probability at most $CQ^k$ with $Q=\frac 34$, say, provided that $b$ and $A$ are chosen appropriately. Since $K$ is of order $\log\frac 1t$, this will yield the desired power bound immediately.


By the CLT, $W\_k$ get close to normals with mean $0$ and variance $A^k$ for large $k$. All we need is that
$$
P\{W\_k<\delta A^{k/2}\}\le q\text{ for }k>k\_0\,.
$$
Note that $k\_0$ depends only on the distribution of $Z$ here (which, of course, should play some role).
Now choose $C>0$ so that $CQ^{k\_0}\ge 1$, so we have nothing to prove for $k=1,\dots,k\_0$. 


Assume now that $k>k\_0$ and the desired estimate holds for $1,\dots,k-1$. The event $E\_k$ is covered by the events
$$
A\_m=E\_{m-1}\cap\{W\_m\le -b^{k-m} A^{k/2}\},\quad m=1,2,\dots,k-1
$$
and 
$$
A=E\_{k-1}\cap \{W\_1+\dots+W\_{k-1}\ge -\tfrac b{1-b}A^{k/2}\}\cap \{W\_k\le (b+\tfrac{b}{1-b})A^{k/2}\}\,.
$$
Here $E\_0$ is the entire probability space.


By the independence of $W\_m$, the induction assumption, and Chebyshev's inequality, we have
$$
P(A\_m)\le CQ^{m-1}\frac 1{(b^2A)^{k-m}}
$$
while 
$$
P(A)\le CQ^{k-1}q
$$
provided that $b+\frac b{1-b}\le\delta$.
Adding all these bounds, we get
$$
CQ^{k-1}\left[q+\sum\_{\ell=1}^{k-1}(Qb^2A)^{-\ell}\right]\le CQ^{k-1}\left(q+\frac 1{Qb^2A-1}\right)\le CQ^k\,,
$$
provided that $A$ was chosen large enough.


