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

  • 1
    $\begingroup$ If Z is normal, the left hand side could be called “the price of a binary option with a discrete Asian barrier on a Brownian-motion asset”. Unfortunately the papers on “discrete Asian barrier options” don’t seem to address this case. $\endgroup$
    – user44143
    Nov 13, 2018 at 18:56
  • 2
    $\begingroup$ Something more should be assumed in general (because if all $Z_j=0$ with probability $1$, then you are out of luck). On the other hand, if you have bounded density and quickly decaying tails (as it seems to be the case), it becomes an interesting question. $\endgroup$
    – fedja
    Nov 13, 2018 at 19:58
  • $\begingroup$ @MattF. The Gaussian case is not too difficult (if one doesn't care about the best $\alpha$). The general case can, probably, be obtained by the CLT approximation, but the resulting argument looks too ugly to post ;-( $\endgroup$
    – fedja
    Nov 14, 2018 at 1:16

1 Answer 1


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.

  • $\begingroup$ Thank you very much for the nice solution! Is there a motivation behind your approach? The calculation seems like magic to me :) $\endgroup$
    – Xiao
    Nov 15, 2018 at 1:49
  • 1
    $\begingroup$ @Xiao The underlying idea is fairly simple: once you have the first $n$ terms, they have little chance to influence the sum more than the next $An$ terms, so you can sort of forget about them and think that you just start all over if $A$ is large enough. Also, by the CLT, the condition $\sum_{j=1}^k Z_j\le kt$ doesn't hold with probability close to $1$ only if the standard deviation $\sqrt k$ of the LHS is larger than the RHS, so there seems to be no point in looking at longer sums. This gives about $\log\frac 1t$ independent attempts to get large, each succeeding with constant probability. $\endgroup$
    – fedja
    Nov 15, 2018 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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