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.
 A: 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. 
The set of techniques an inequalities is huge, without further details I can not be more precise. Hope it helps though!
A: 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.
