# A comprehensive list of random walk inequalities?

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 random processes by finite-dimensional distribution.

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)}$$

Wiener Theorem

If $$E(X_1) = 0$$ and $$0 < Var(X_1) < +\infty$$, then

$$\frac{S_{\lfloor nt \rfloor}}{\sqrt{n Var(X_1)}} \Rightarrow W(t)$$

where, $$W(t)$$ stands for Wiener process.

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

1. If $$P(X_1 = 1) = P(X_1 = -1) = 0.5$$, then

$$P(|S_n| \leq \sqrt{n}) \geq 0.5$$

1. If $$X_1 \sim N(0, 1)$$, then

$$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$$

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 1 - \frac{P(X_1 = 0)}{nP(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)

• If $X_1$ has finite exponantial moment you can add Cramer theorem (more general and powerfull than Hoeffding inequality). With $\mathbb{E}[X_1]=0$ and some finite moment : you have all the nice theorems from Martingale such as the Doob's inequalities. – RaphaelB4 Jun 15 '19 at 13:57

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.