I am interested in finding a comprehensive list of all noticeable random walk inequalities.
ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$
I can only seem to find books/papers that list the already well known ones like Kolmogorov's maximal inequality.
Does anyone know of such a paper/book?
There I will list the inequalities and asymptotic theorems on random walks, that are currently known to me:
Notation that will be used in the list:
$\{X_n\}_{n = 1}^\infty$ are i.i.d. random variables.
$\{S_n\}$ is the random walk ($S_n = \Sigma_{k = 1}^n X_k$)
$\nu(t) = \max\{n \in \mathbb{N}_0 | S_n < t \}$ - the corresponding renewal process (well defined if $P(X_1 > 0) = 1$)
$U(t) = 1 + E(\nu(t))$ -the corresponding renewal function (well defined if $P(X_1 > 0) = 1$)
The types of convergence will be denoted in the following way:
$\to_D$ is convergence by distribution
$\to_P$ is convergence by probability
$\to_{a.s.}$ is convergence almost surely
$\Rightarrow$ is convergence of stochastic processes in Skorokhod space.
THE LIST:
Law of Large Numbers
If $|E(X_1)| < \infty$, then
$$\frac{S_n}{n} \to_{a.s.} E(X_1)$$
Laws of Iterated Logarithm
1.Suppose $E(X_1) = 0$ and $Var(X_1) = 1$, then
$$P(\overline{\lim_{n \to \infty}} \frac{S_n}{\sqrt{2n\log\log n}} = 1) = 1$$
2.Suppose $E(X_1) = 0$ and $Var(X_1) = 1$, then
$$P(\underline{\lim_{n \to \infty}} \frac{S_n}{\sqrt{2n\log\log n}} = -1) = 1$$
Central Limit Theorem
If $|E(X_1)| < \infty$ and $Var(X_1) < \infty$, then
$$\frac{S_n - nE(X_1)}{\sqrt{n}} \to_{D} Z \sim {N}(0, Var(X_1))$$
Berry-Esseen Inequality
If $E(X_1) = 0$, $0 < Var(X_1) < +\infty$ and $E(|X_1|^3) < +\infty$, then
$$|P(S_n \leq x \sqrt{n Var(X_1)}) - \frac{e^{\frac{x^2}{2}}}{\sqrt{2\pi}}| < \frac{0.4748 E(|X_1|^3)}{(Var(X_1))^{\frac{3}{2}} \sqrt{n}}$$
Shevtsova inequalities
1.If $E(X_1)= 0$, $0 < Var(X_1) < +\infty$ and $E(|X_1|^3) < +\infty$, then
$$|P(S_n \leq x \sqrt{n Var(X_1)}) - \frac{e^{\frac{x^2}{2}}}{\sqrt{2\pi}}| < \frac{0.33554 E(|X_1|^3) + 0.415 (Var(X_1))^{\frac{3}{2}}}{(Var(X_1))^{\frac{3}{2}} \sqrt{n}}$$
2.If $E(X_1) = 0$, $0 < Var(X_1) < +\infty$ and $1.286(Var(X_1))^{\frac{3}{2}} < E(|X_1|^3)< +\infty$, then
$$|P(S_n \leq x \sqrt{n Var(X_1)}) - \frac{e^{\frac{x^2}{2}}}{\sqrt{2\pi}}| < \frac{0.3328 E(|X_1|^3) + 0.429 (Var(X_1))^{\frac{3}{2}}}{(Var(X_1))^{\frac{3}{2}} \sqrt{n}}$$
Hoeffding Inequalities
1.If $P(X_1 \in [0;1])=1$ and $t > 0$, then
$$P(S_n - nE(X_1) \geq t) \leq e^{\frac{2t^2}{n}}$$
2.If $P(X_1 \in [0;1])=1$ and $t > 0$, then
$$P(|S_n - nE(X_1)| \geq t) \leq 2e^{\frac{2t^2}{n}}$$
Bennet Inequality
Suppose $E(X_1) = 0$, $0 < Var(X_1) < +\infty$, $P(X_1 < a) = 1$, for some $a < +\infty$ and $t > 0$ then
$$P(S_n > t) \leq {(\frac{Var(X_1) + at}{Var(X_1)})}^{-\frac{Var(X_1) + at}{a^2}} e^{\frac{t}{a}}$$
Bernstein Inequalities
1.If $E(X_1) = 0$ and $P(|X_1| \leq M) = 1$, then
$$P(S_n > t) \leq e^{- \frac{3t^2}{6n Var(X_1) + 2Mt}}$$
2.If $\exists L >0$ $\forall k > 1$ $2E(|X_1^k|) \leq k!L E(X_1^2)$ and $0 < t < \frac{n E(X_1^2)}{L}$ then
$$P(S_n > t) < e^{-\frac{t^2}{4n E(X_1^2)}}$$
3.If $\exists L >0$ $\forall k > 3$ $4!5^{k - 4}E(|X_1^k|) \leq k!L^{k - 4}$, and $0 < t < \frac{5}{4L}$, then
$$P(|S_n - \frac{2}{3}nE(X_1^3)t^2| \geq 2nE(X_1^2)t(1 + \frac{E(X_1^4)t^2}{3E(X_1^2)}))) < 2e^{-nE(X_1^2)t^2}$$
Kolmogorov Inequality
If $E(X_1) = 0$, $Var(X_1) < +\infty$ and $t > 0$, then
$$P(\max_{1 \leq k \leq n} S_k \geq t) \leq \frac{n Var(X_1)}{t^2}$$
Law of Large Numbers for Renewal Process
If $P(X_1 > 0) = 1$, $E(X_1) < +\infty$ , $t \to +\infty$ then
$$\frac{\nu(t)}{t} \to_{P} \frac{1}{E(X_1)}$$
Central Limit Theorem for Renewal Process
If $P(X_1 > 0) = 1$, $E(X_1) < +\infty$ , $Var(X_1) < +\infty$, $t \to +\infty$ then
$$\frac{(E(X_1))^\frac{3}{2} \nu(t) - t (E(X_1))^{\frac{1}{2}} }{t^{\frac{1}{2}}(Var(X_1))} \to_{D} Z \cong Z \sim {N}(0, 1)$$
Wald Equality
If $P(X_1 > 0) = 1$, $E(X_1) < +\infty$ and $t > 0$ then
$$E(S_{\nu(t) + 1})=U(t)E(X_1)$$
Fundamental Renewal Theorem
If $P(X_1 > 0) = 1$, $h > 0$ and $E(X_1) < +\infty$ then
$$\lim_{t \to \infty} (U(t + h) - U(t))= \frac{h}{E(X_1)}$$
Integral Renewal Theorem
If $P(X_1 > 0) = 1$ and $E(X_1) < +\infty$ then
$$\lim_{t \to \infty} \frac{U(t)}{t} = \frac{1}{E(X_1)}$$
Donsker invariance principle
If $E(X_1) = 0$, $0 < Var(X_1) < +\infty$ and $t \in [0; 1]$ then
$$\frac{S_{\lfloor nt \rfloor}}{\sqrt{n Var(X_1)}} \Rightarrow W(t)$$
where, $W(t)$ stands for Brownian motion.
Liggett invariance principle
If $E(X_1) = 0$, $0 < Var(X_1) < +\infty$, $t \in [0; 1]$ and $a > 0$ then
$$\frac{S_{\lfloor nt \rfloor}}{\sqrt{n Var(X_1)}} | S_n \in (-a; a] \Rightarrow B(t)$$
where, $B(t)$ stands for Brownian bridge.
Eagleheart invariance principle
If $E(X_1) = 0$, $0 < Var(X_1) < +\infty$ and $t \in [0; 1]$ then
$$\frac{S_{\lfloor nt \rfloor}}{\sqrt{n Var(X_1)}} | \min\{n > 0| S_n \leq 0\} > n \Rightarrow W^+(t)$$
where, $W^+(t)$ stands for Brownian meander.
Hopf lemma
If $E(X_1) < +\infty$, $p \in \mathbb{R}$ and $n \in \mathbb{N}$ then
$$E(X_1 ; \{max_{k \leq n} \frac{S_k}{k} > t\}) \geq tP(\{max_{k \leq n} \frac{S_k}{k} > t\})$$
He-Zhang-Zhang inequality
If $P(X_1 > 0) = 1$ and $EX_1 = 1$, then
$$P( \frac{S_n}{n} - 1 \geq \frac{1}{n}) \leq \frac{7}{8}$$
Van Zuijlen bounds
$$P(|S_n| \leq \sqrt{n}) \geq 0.5$$
$$P(|S_n| \leq \sqrt{n}) \geq 0.31$$
Elementary Renewal-Reward Theorem
Suppose $P(X_1 > 0) = 1$, $E(X_1) < +\infty$, $\{Y_n\}_{n = 1}^{\infty}$ is a sequence of i.i.d. random variables with finite expectation, then
$$\lim_{t \to \infty} \frac{E(\Sigma_{i = 1}^{\nu(t)}Y_i)}{t} = \frac{E(Y_1)}{E(X_1)}$$
Law of Large Numbers for Renewal-Reward processes
Suppose $P(X_1 > 0) = 1$, $E(X_1) < +\infty$, $\{Y_n\}_{n = 1}^{\infty}$ is a sequence of i.i.d. random variables with finite expectation, and $t \to +\infty$ then
$$\frac{\Sigma_{i = 1}^{\nu(t)}Y_i}{t} \to_{a.s.} \frac{E(Y_1)}{E(X_1)}$$
Renewal Equation
Suppose $P(X_1 > 0) = 1$, $E(X_1) < +\infty$, $t > 0$ and $P(X_1 \leq x) \in C^1[0; 1]$ then
$$E(\nu(t)) = P(X_1 \leq t) + \int_0^t E(\nu(t - s))\frac{\partial P(X_1 \leq s)}{\partial s}ds$$
Inspection Paradox
Suppose $P(X_1 > 0) = 1$, $x > 0$ and $t > 0$, then
$$P(X_{\nu(t) + 1} > x) \geq P(X_1 > x)$$
Local limit theorem
Suppose $A \subset \mathbb{Z}$ is finite and $P(X_1 \in A) = 1$. Then $\exists 0 < C_1 < C_2 < +\infty$, such that
$$\frac{C_1}{\sqrt{n}} \leq sup_{k \in \mathbb{Z}} P(S_n = k) \leq \frac{C_2}{\sqrt{n}}$$
Kurtosis Equality
Suppose $E(X_1^4)$ is finite. Then
$$\frac{E((S_n - nE(X_1))^4)}{(nVar(X_1))^2} - 3 = \frac{1}{n}(\frac{E((X_1 - E(X_1))^4)}{(Var(X_1))^2} - 3)$$
Erdos-Renyi counting inequality
Suppose $P(X_1 \geq 0) = 1$ and $P(X_1 > 0) > 0$, then
$$P(S_n > 0) \geq \frac{nP(X_1 = 0)}{1 + (n-1)P(X_1 = 0)}$$
Durrett Finite Moment Theorem
Suppose $E(X_1) = 0$ and
$$\frac{S_n}{n^{\frac{1}{p}}} \to_{a.s.} 0$$
then $E(|X_1|^p)<+\infty$
Cramer Theorem
If $\forall t \in \mathbb{R}$ $E[e^{tX_1}]<+\infty$, then
$$\lim_{n \to \infty} \frac{1}{n}\ln(P(S_n \geq nx)) = \inf_{t \in \mathbb{R}}(\ln(E[e^{tX_1}])-tx)$$
If you already know all these facts and want something more exotic, then sorry (however, if I find anything else, I will expand this list)
This is a large subject, but the following books are an excellent starting point; each of them has been cited thousands of times.
Chow, Yuan Shih, and Henry Teicher, 2012. Probability theory: independence, interchangeability, martingales. Springer.
Petrov, V.V., (1976, 2012). Sums of independent random variables (Vol. 82). Springer
Ledoux, Michel, and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer 2013.
Dembo, A. and Zeitouni, O. (1998, 2011). Large deviations techniques and applications. Springer Applications of Mathematics, 38.
