A maximal inequality for sample variance

Question

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.

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*}