I work with i.i.d. variables $X_1, \dots, X_{N}$ such that $0 \le X_i \le 1$, $E[X_i] = \mu$, $\operatorname{Var}[X_i] = \sigma^2$.

I am gradually sampling $X_1, X_2, \dots$ and want to ensure that the natural sample variance estimate stays within reasonable bounds. More formally, define $A_n = \sum_{i = 1}^n (X_i - \bar X_n)^2 - (n-1)\sigma^2$ where $\bar X_n = \sum_{i = 1}^{n} X_i/n$. We have $E[A_n] = 0$ for every $n$. Also, using that $X_i$s are bounded, we can crudely upper bound the variance as $\operatorname{Var}[A_n] \le n\sigma^2$.

Using Chebyshev's inequality, we can conclude that $P[|A_{N}| > 100\sqrt{N\sigma^2}] < 0.5$. However, I would like to have a stronger result $P[\max_{n = 1}^{N} |A_{n}| > 100\sqrt{N\sigma^2}] < 0.5$. My question is: How do we achieve this bound? Is there some well-known inequality that proves this?

Note that if $A_n$ was a martingale, we could use Kolmogorov's inequality to arrive at this conclusion. My intuition why the inequality holds is that $A_n$ behaves very similar to a martingale.

  • $\begingroup$ Do you have a response to the answer below? $\endgroup$ Apr 9, 2023 at 0:51
  • $\begingroup$ @IosifPinelis No, it's perfect! :) Thanks! $\endgroup$
    – Vasek
    Apr 10, 2023 at 10:12

1 Answer 1


$\newcommand{\si}{\sigma}$Note that \begin{equation*} A_n=B_n-C_n, \end{equation*} where \begin{equation*} B_n:=\sum_1^n Y_i,\quad C_n:=\frac1n\,\Big(\sum_1^n Z_i\Big)^2-\si^2, \end{equation*} \begin{equation*} Z_i:=X_i-\mu,\quad Y_i:=Z_i^2-\si^2. \end{equation*} Note also that, in view of the condition $0\le X_i\le1$ and excluding the trivial case with $\si^2=0$, \begin{equation*} \si:=\sqrt{\si^2}\in(0,1/2]. \tag{10}\label{10} \end{equation*} So, for any integer $N\ge1$, letting \begin{equation*} y:=10\si\sqrt N,\quad z:=90\si\sqrt N,\quad x:=y+z=100\si\sqrt N, \tag{20}\label{20} \end{equation*} we get \begin{equation*} z\ge\si^2 \tag{30}\label{30} \end{equation*} and \begin{equation*} P(\max_1^N|A_n|>x)\le Q_1+Q_2, \tag{40}\label{40} \end{equation*} where \begin{equation*} Q_1:=P(\max_1^N|B_n|>y) \end{equation*} and \begin{equation*} Q_2:=P(\max_1^N|C_n|>z)=P(\max_1^N C_n>z), \end{equation*} because $-C_n\le\si^2\le z$ for all $n$, by \eqref{30}.

By Kolmogorov's maximal inequality and \eqref{20}, \begin{equation*} Q_1\le\frac{EB_N^2}{y^2}=\frac{N\,EY_1^2}{y^2}\le\frac{N\si^2}{y^2}=\frac1{100}, \end{equation*} because $EY_1^2\le EZ_1^4\le EZ_1^2=\si^2$.

To bound $Q_2$, we use the following simple but crucial construction: let \begin{equation*} D_n:=C_n+\si^2+\si^2(H_N-H_n), \end{equation*} where $H_n:=\sum_1^n\frac1k$. Noting that \begin{equation*} C_n-C_{n-1} =-\frac1{n(n-1)}\,\Big(\sum_1^{n-1}Z_i\Big)^2+\frac{Z_n^2}n+\frac{2Z_n}n\,\sum_1^{n-1}Z_i \\ \le\frac{Z_n^2}n+\frac{2Z_n}n\,\sum_1^{n-1}Z_i, \end{equation*} we see that $(D_n)_1^N$ is a nonnegative supermartingale with respect to the filtration generated by the $X_i$'s (or, equivalently, by the $Z_i$'s). Therefore (see e.g. this and this), \begin{equation*} Q_2\le P(\max_1^N D_n>z)\le\frac{ED_1}z=\frac{\si^2 H_N}{90\si\sqrt N}<\frac1{100}, \end{equation*} in view of \eqref{20}, \eqref{10}, and inequality $\dfrac{H_N}{\sqrt N}\le\dfrac{H_2}{\sqrt2}<1.07$ for integers $N\ge1$.

Thus, by \eqref{40}, \begin{equation*} P(\max_1^N|A_n|>100\si\sqrt N)<\frac2{100}<0.5.\quad\Box \end{equation*}


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.