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.



A maximal inequality for sample variance
$\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](https://math.stackexchange.com/q/360580/96609) and [this](https://math.stackexchange.com/a/360632/96609)),
\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\*}


