6
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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

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

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)

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – RaphaelB4 Jun 15 at 13:57
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.