# A maximal inequality for sample variance

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.

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

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