# Measure concentration for law of large numbers

The classical law of large numbers states that $$\frac1k\sum_{i=1}^k X_i \rightarrow \mathbb{E} X_1$$ for i.i.d. $X_1, X_2, \ldots$ with finite $L^1$ norm.

I was wondering whether is it possible to derive a concentration bound for $$\mathbb{P}\Big(\sup_{k \geq j} \Big|\frac1k\sum_{i=1}^k X_i - \mathbb{E} X_1 \Big| > c\Big)$$ for a large $j$ and some $c > 0$.

It would be great if any relevant references could be suggested.

• This is the maximal function, which has been studied heavily, see for example here: markhkim.com/uploads/seminars/spsu14-harmonic-analysis/… – Christian Remling Aug 13 '14 at 13:26
• In the stationary case, this corresponds to the maximal ergodic theorem. – Asaf Oct 1 '14 at 15:12
• Assuming only $L^1$ it is hard to get estimates. Assuming that the $X_i$ have momenta of any order more can be said. For large $c$ that is the theory of large deviations arxiv.org/pdf/1106.4146v3.pdf The author. – Liviu Nicolaescu Dec 27 '15 at 19:25

Depending on the type of bound you are looking for, I suggest you look at the large deviations principle for your particular problem. Essentially, LDP states (in the 1d case for simplicity) that $$\lim_{ n \to \infty } n^{-1} \log \mathbb{P} \left( \left\vert \frac{1}{n} \sum_{i=1}^nX_i-\mathbb{E}X \right \vert > a \right ) = - I(a),$$ where $I(a) = \sup_{ \theta } \left(\theta a - \log \mathbb{E}e^{ \theta X_1 } \right)$. To get the supremum in, you have to study the continuity properties of the supremum to apply varadhan's lemma. Examples of these kind of techniques are crisply explained in Den Hollanders large deviations monograph.
Now, if asymptotic in $n$ estimates is not what you need. You have an arsenal of concentration inequalities. An easy entry point can be found for example in the survey "Concentration inequalities and martingale inequalities as survey" published in the now discontinued internet math. journal. To get the supremum in, there is also a set of well known techniques, Talagrand's chaining being the strongest one.
I understand you're looking for a non-asymptotic bound with finite $j$ (rather than a limsup bound). This can be proved by observing that $\sum_{i=1}^k (X_i - \mathbb{E}X_i)$ is a martingale, and using stopping time techniques; see Sec. 3.1 (Thm. 10) of http://arxiv.org/pdf/1405.2639v4.pdf . In your notation, this will give you a probability of $\delta$ with $j = \Theta (\log \frac{1}{\delta})$ and $c$ depending on the variance of $X_i$.
That specific reference deals with almost surely bounded $X_i$ because the proofs are simpler, but it can be readily extended to e.g. bounded higher moments as with Bernstein's inequalities; the bounds will be similar, and the constants etc. can be worked out, as in the above reference. With more details about the properties of $X_i$, I can give more specifics.