Skip to main content
3 of 13
added 188 characters in body
Chain Markov
  • 2.6k
  • 15
  • 26

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

$F_n$ is CDF of $S_n$

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

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

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

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

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

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

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)

Chain Markov
  • 2.6k
  • 15
  • 26