Recueil de modèles aléatoires

April 21st, 2015 No comments
Recueil de modèles aléatoires

Recueil de modèles aléatoires

J’ai l’immense joie de terminer la mise au point d’une nouvelle mouture du livre intitulé « Recueil de modèles aléatoires », écrit en collaboration avec Florent Malrieu. Cette nouvelle version, plus aboutie, contient en principe, moins de coquilles que la version antérieure, grâce notamment aux efforts de nombreux lecteurs. Le titre est légèrement différent, le contenu est plus homogène, et un nouveau chapitre a fait son apparition suite à une mitose. L’index a été considérablement enrichi. Bonne lecture !

Attention, ce livre n’est pas fait pour être lu d’une traite et ne constitue en aucune manière un cours. Son format condensé est un parti pris. Les chapitres ne sont pas tous du même niveau de difficulté. Voici la nouvelle table des matières (27 chapitres, une bibliographie, un index) :

  • Pile, face, coupons
  • Marches aléatoires
  • Urnes d’Ehrenfest
  • Modèle de Wright-Fisher
  • Branchement
  • Percolation
  • Renforcement
  • Simulation de permutations, de partitions, et de graphes aléatoires
  • Simulation de mesures de Gibbs
  • Restaurants chinois
  • Généalogies et coalescence
  • Agrégation limitée par diffusion interne
  • Chaînes de Markov cachées
  • Algorithme EM et mélanges
  • Records, extrêmes, et recrutements !
  • Polymères dirigés en environnement aléatoire
  • Matrices aléatoires
  • Problème du voyageur de commerce
  • File d’attente M/M/Infini
  • Ruine d’une compagnie d’assurance
  • Naissances et assassinats
  • Croissance et fragmentation
  • Modèle du télégraphe
  • Problème de Dirichlet
  • Processus d’Ornstein-Uhlenbeck
  • Modèles de diffusion cinétique
  • Des chaînes de Markov aux processus de diffusion
  • Bibliographie
  • Index
Share
Categories: Probability, Teaching

Tightness

April 14th, 2015 No comments
Yuri Vasilevich Prokhorov (1929 - 2013)

Yuri V. Prokhorov (1929 – 2013)

This post is about a basic fact which is not very well known. Let \( {{(\mu_i)}_{i\in I}} \) be a family of probability measures on a topological space \( {E} \) equipped with its Borel sigma-field. The following two properties are equivalent, and when they hold we say that \( {{(\mu_i)}_{i\in I}} \) is tight.

  1. for any \( {\varepsilon>0} \) there exists a compact set \( {K_\varepsilon\subset E} \) such that

    \[ \sup_{i\in I}\mu_i(K_\varepsilon^c)\leq\varepsilon; \]

  2. there exists a measurable \( {f:E\rightarrow[0,\infty]} \) with compact level-sets such that

    \[ \sup_{i\in I}\int\!f\,d\mu_i<\infty. \]

Recall that the level-sets of \( {f} \) are the sets \( {\{x\in E:f(x)\leq r\}} \), \( {r\geq0} \). If \( {E} \) is not compact then it cannot be a level-set of \( {f} \) and thus \( {f} \) cannot be bounded, while if \( {E} \) is compact then the property holds trivially with \( {f} \) constant.

To deduce 1. from 2. we write, using the Markov inequality, for any \( {r>0} \),

\[ \sup_{i\in I}\mu_i(\{x\in E:f(x)\leq r\}^c) \leq \frac{1}{r}\sup_{i\in I}\int\!f\,d\mu_i=\frac{C}{r}, \]

which leads to take \( {r=r_\varepsilon=C/\varepsilon} \) and \( {K_\varepsilon=\{x\in E:f(x)\leq r_\varepsilon\}} \), for any \( {\varepsilon>0} \).

To deduce 2. from 1. we first extract from 1. a sequence of compact subsets \( {{(K_{1/n^2})}_{n\geq1}} \). We can assume without loss of generality that it grows: \( {K_{1/n^2}\subset K_{1/m^2}} \) if \( {n\leq m} \). Now, for any \( {x\in F=\cup_{n}K_n} \), there exists \( {n_x} \) such that \( {x\in K_{1/m^2}} \) for any \( {m\geq n_x} \), and thus \( {\sum_n \mathbf{1}_{K_{1/n^2}^c}(x)=n_x-1<\infty} \). As a consequence, if one defines

\[ f:=\sum_n\mathbf{1}_{K_{1/n^2}^c} \]

then \( {f<\infty} \) on \( {F} \) while \( {f=\infty} \) on \( {F^c} \), and \( {f} \) has compact level-sets since \( {\{x\in E:f(x)\leq n-1\}=K_{1/n^2}} \) for any \( {n\geq1} \). On the other hand, by definition of \( {K_\varepsilon} \),

\[ \sup_{i\in I}\int\!f\,d\mu_i \leq\sum_n\frac{1}{n^2}<\infty. \]

Tightness is an important concept of probability theory. A famous theorem of Prokhorov states that a family of probability measures is tight if and only if it is relatively compact for the topology of narrow convergence.

Taking \( {X_i\sim\mu_i} \) for every \( {i\in I} \), the second property reads

\[ \sup_{i\in I}\mathbb{E}(f(X_i))<\infty. \]

It plays for tightness the role played by the famous de la Vallée Poussin criterion for uniform integrability.

Share
Categories: Analysis, Probability

An exercise in linear algebra

April 5th, 2015 No comments

Matrix

Exercise. Recently a friend of mine asked the following basic question: suppose that \( {H} \) is a \( {n\times n} \) Hermitian matrix with \( {>0} \) spectrum and suppose that \( {P} \) is a \( {n\times n} \) orthogonal projection matrix. Is it true that all the non-zero eigenvalues of the product \( {HP} \) are above the least eigenvalue of \( {H} \)?

Self-contained proof. Since \( {P} \) is an orthogonal projection, we have

\[ P^*=P, \]

and there exists a unitary matrix \( {U} \) such that \( {UPU^*} \) is diagonal with diagonal in \( {\{0,1\}} \). If \( {H} \) and \( {P} \) commute, then \( {UHU^*} \) is also diagonal, with diagonal elements in \( {\mathbb{R}_+} \), and therefore \( {UHPU^*} \) is diagonal with diagonal elements in \( {\{0\}\cup\mathrm{spectrum}(H)} \). This shows that the problem has positive answer when \( {H} \) and \( {P} \) commute.

In the general situation, \( {H} \) and \( {P} \) do not commute, and the product \( {HP} \) is not necessarily Hermitian even if \( {H} \) and \( {P} \) are Hermitian. We may use the fact that \( {AB} \) and \( {BA} \) have same spectrum. This is a consequence of the Sylvester determinant theorem which states that

\[ \det(I+AB)=\det(I+BA). \]

As a consequence, if \( {A} \) and \( {B} \) are both Hermitian with \( {\geq0} \) spectrum, then \( {AB} \) has the spectrum of the Hermitian matrix \( {B^{1/2}A^{1/2}A^{1/2}B^{1/2}} \). Therefore, this spectrum is real and \( {\geq0} \), formed by the squared singular values of \( {A^{1/2}B^{1/2}} \). In particular, if \( {A=H} \) is Hermitian with \( {\geq0} \) spectrum and if \( {B=P} \) is the matrix of an orthogonal projection, then \( {AB=HP} \) has a real \( {\geq0} \) spectrum, formed by the squared singular values of \( {H^{1/2}P^{1/2}=H^{1/2}P} \) since \( {P^{1/2}=P} \) (\( {P} \) is an orthogonal projection).

If one denotes by \( {s_1(M)\geq\cdots\geq s_n(M)\geq0} \) the singular values of a \( {n\times n} \) matrix \( {M} \), then the Courant-Fischer min-max variational formulas give, for any \( {1\leq k\leq n} \),

\[ s_k(M) =\max_{V\in\mathcal{V}_k}\min_{\substack{v\in V\\\left\Vert v\right\Vert_2=1}}\left\Vert Mv\right\Vert_2 \left(=\min_{V\in\mathcal{V}_{n-k+1}}\max_{\substack{v\in V\\\left\Vert v\right\Vert_2=1}}\left\Vert Mv\right\Vert_2\right) \]

where \( {\mathcal{V}_k} \) is the set of sub-spaces with dimension \( {k} \). Used with \( {M=H^{1/2}P} \),

\[ s_k(H^{1/2}P)=\max_{V\in\mathcal{V}_k}\min_{\substack{v\in V\\\left\Vert v\right\Vert_2=1}} \left\Vert H^{1/2}Pv\right\Vert_2. \]

If \( {V\cap\mathrm{ker}(P)\neq\{0\}} \) then there exists \( {v\in V} \) with \( {\left\Vert v\right\Vert_2=1} \) and \( {\left\Vert H^{1/2}Pv\right\Vert_2=0} \), hence

\[ s_k(H^{1/2}P) =\max_{\substack{V\in\mathcal{V}_k\\V\cap\mathrm{ker}(P)\neq\{0\}}} \min_{\substack{v\in V\\\left\Vert v\right\Vert_2=1}} \left\Vert H^{1/2}Pv\right\Vert_2. \]

Now if \( {k>d} \) where \( {d=n-\mathrm{dim}(\mathrm{ker}(P))=\mathrm{dim}(\mathrm{Im}(P))} \), then for every \( {V\in\mathcal{V}_k} \), we have \( {V\cap\mathrm{ker}(P)\neq\{0\}} \), and thus \( {s_k(H^{1/2}P)=0} \).

Let us suppose in contrast now that \( {k\leq d} \). Then there exists \( {V_*\in\mathcal{V}_k} \) such that \( {V_*\subset\mathrm{Im}(P)\perp\mathrm{ker}(P)} \), and thus, for every \( {v\in V_*} \) such that \( {\left\Vert v\right\Vert_2=1} \), we have \( {Pv=v} \), which gives then

\[ s_k(H^{1/2}P) \geq \min_{\substack{v\in V_*\\\left\Vert v\right\Vert_2=1}} \left\Vert H^{1/2}v\right\Vert_2 \geq \min_{\left\Vert v\right\Vert_2=1}\left\Vert H^{1/2}v\right\Vert_2 = s_n(H^{1/2})=s_n(H)^{1/2}. \]

As a conclusion we have, still with \( {d=\mathrm{dim}(\mathrm{Im}(P))} \),

\[ s_1(HP)\geq\cdots\geq s_d(HP)\geq s_n(H) \]

\[ s_{d+1}(HP)=\cdots=s_n(HP)=0. \]

This ends the proof.

Alternative. Actually, the result can be deduced quickly from the following general bound, which is also a consequence of Courant-Fischer formulas: if \( {A} \) and \( {D} \) are \( {n\times n} \) with \( {D} \) diagonal then for any \( {1\leq k\leq n} \),

\[ s_n(D)s_k(A)\leq s_k(DA)\leq s_1(D)s_k(A). \]

Indeed, if \( {P} \) is an orthogonal projector and if \( {H=UDU^*} \) is Hermitian with \( {\geq0} \) spectrum, then the lower bound in the inequality above used with \( {A=U^*P} \) gives

\[ s_n(H)s_k(P)=s_n(D)s_k(U^*P)\leq s_k(DU^*P)=s_k(UDU^*P)=s_k(HP). \]

Now \( {s_k(P)=1} \) if \( {k\geq d} \), where \( {d=n-\mathrm{dim}(\mathrm{ker}(P))=\mathrm{dim}(\mathrm{Im}(P))} \), which gives \( {s_k(HP)\geq s_n(H)} \) if \( {k\geq d} \). On the other hand, using the upper bound we get

\[ s_k(HP)=s_k(UDU^*P)=s_k(DU^*P)\leq s_1(D)s_k(U^*P)=s_1(H)s_k(P). \]

Now if \( {k<d} \) then \( {s_k(P)=0} \), which gives \( {s_k(HP)=0} \).

Further reading. Many other bounds are available, see for instance the books

Share
Categories: LinearAlgebra

Back to basics: martingales

April 5th, 2015 No comments
Joseph Leo Doob (1910 - 2004) creator of martingale theory.

Joseph Leo Doob (1910 – 2004) creator of martingale theory.

Recently, I had to teach quickly basic knowledge about martingales. What we should know at minimum about martingales? Well, numerous things, indeed.

Martingales are generalizations of sums of independent random variables (random walks) in which each new increment is in a way conditionally orthogonal to the past increments. Indeed, a sequence of random variables \( {M={(M_n)}_{n\geq0}} \) is a martingale with respect to a filtration \( {\mathcal{F}={(\mathcal{F})}_{n\geq0}} \) when for any \( {n\geq0} \), \( {M_n\in L^1(\mathcal{F}_n)} \), and

\[ \mathbb{E}(M_{n+1}-M_n|\mathcal{F}_n)=0. \]

If so then we have the conservation law of the mean:

\[ \mathbb{E}(M_0)=\mathbb{E}(M_1)=\cdots \]

If \( {M_n\in L^2} \) for every \( {n\geq0} \) then for any \( {n\geq0} \),

\[ M_{n+1}-M_n\perp L^2(\mathcal{F}_n). \]

Basic examples of martingales. (guess the filtration):

  • Sum. \( {S_0=0} \), \( {S_n=X_1+\cdots+X_n} \), \( {{(X_n)}_{n\geq1}} \) independent with mean \( {m} \)

    \[ M_n=S_n-nm; \]

  • Product. \( {P_0=1} \), \( {P_n=X_1\cdots X_n} \), \( {{(X_n)}_{n\geq1}} \) independent, \( {\geq0} \) with mean \( {m} \)

    \[ M_n=\frac{P_n}{m^n}; \]

  • Weights. \( {S_{-1}=0} \), \( {{(S_n)}_{n\geq0}} \) martingale, \( {H_n} \) \( {\mathcal{F}_{n-1}} \)-measurable

    \[ M_n=\sum_{k=0}^n H_k(S_k-S_{k-1}); \]

  • Squared sum. \( {S_0=0} \), \( {S_n=X_1+\cdots+X_n} \), \( {{(X_n)}_{n\geq1}} \) iid mean \( {0} \) variance \( {\sigma^2} \)

    \[ M_n=S_n^2-n\sigma^2; \]

  • Exponential. \( {S_0=0} \), \( {S_n=X_1+\cdots+X_n} \), \( {{(X_n)}_{n\geq1}} \) iid Rademacher \( {p\delta_1+q\delta_{-1}} \)

    \[ M_n=\left(\frac{q}{p}\right)^{S_n}; \]

    More generally if \( {S_0=x} \), \( {S_n=x+X_1+\cdots+X_n} \), \( {\alpha>0} \), \( {\varphi(\alpha)=\log(\mathbb{E}(e^{-\alpha X_1}))} \)

    \[ M_n=\exp\left(-\alpha S_n-n\varphi(\alpha)\right); \]

  • Wright-Fisher model. \( {X_0\in[0,N]} \), \( {\mathrm{Law}(X_{n+1}|X_n,\ldots,X_0)=\mathrm{Binom}(N,X_n/N)} \)

    \[ M_n=X_n; \]

  • Polya urn model. \( {{(U_n)}_{n\geq0}} \) iid uniform on \( {[0,1]} \), \( {(A_0,B_0)=(1,1)} \),

    \[ (A_{n+1},B_{n+1})=(A_n+\mathbf{1}_{U_n\leq M_n},B_n+\mathbf{1}_{U_n>M_n}), \]

    \[ M_n=\frac{A_n}{A_n+B_n}; \]

  • Galton-Watson process. \( {{(Z_n)}_{n\geq0}} \) Galton-Watson, \( {m=\mathbb{E}(Z_1)} \), \( {\mathbb{E}(\rho^{Z_1})=\rho\leq1} \),

    \[ M_n=\rho^{Z_n}; \]

    and

    \[ M_n=\frac{Z_n}{m^n}; \]

  • Markov chain. Markov chain \( {{(X_n)}_{n\geq0}} \) on countable state space \( {E} \), \( {f:E\rightarrow\mathbb{R}} \) harmonic for the generator \( {L} \) of \( {X} \) (means that \( {Lf=0} \));

    \[ M_n=f(X_n)-f(X_0). \]

    This includes some of the examples above in a single concept. We have also discussed some relations to Markov chains in a previous post.

If \( {T} \) is a stopping time for \( {\mathcal{F}} \) taking its values in \( {\{0,1,\ldots\}\cup\{\infty\}} \) then the optional stopping theorem states that the stopped process

\[ {(M_{\min(n,T)})}_{n\geq0} \]

is again a martingale, and in particular by the conservation law, for any \( {n\geq0} \),

\[ \mathbb{E}(M_0)=\mathbb{E}(M_{\min(n,T)}). \]

Now since \( {\min(n,T)\rightarrow T} \) almost surely on \( {\{T<\infty\}} \), then \( {M_{\min(n,T)}\rightarrow M_T} \) almost surely on \( {\{T<\infty\}} \). In order to deduce that

\[ \mathbb{E}(M_0)=\mathbb{E}(M_T), \]

we need that \( {T<\infty} \) almost surely and a way to pass from almost sure convergence to convergence of expectations. It works for example by dominated convergence if \( {T<\infty} \) almost surely and \( {M} \) is uniformly integrable, for instance if \( {\sup_{n\geq0}|M_n|\in L^1} \). It turns out also that it also works if \( {T\in L^\infty} \), or if \( {T<\infty} \) almost surely and \( {M} \) has uniformly bounded oscilliations in the sense that \( {\sup_{n\geq0}|M_{n+1}-M_n|\in L^\infty} \).

The optional stopping theorem is useful to extract information about a stopping time. For instance, let \( {X={(X_n)}_{n\geq1}} \) be iid Bernoulli \( {p\delta_1+q\delta_0} \) with \( {p>0} \), and let

\[ T=\inf\{n\geq2:X_n=X_{n-1}=X_{n-2}=1\} \]

be the first time of occurrence of the sequence \( {111} \) in \( {X} \). Let \( {S_0=0} \) and

\[ S_{n+1}=(S_n+1)\frac{X_{n+1}}{p}. \]

Then the random sequence \( {M={(M_n)}_{n\geq0}} \) defined by \( {M_n=S_n-n} \) for any \( {n\geq0} \) is a martingale. Now, the stopping time \( {T} \) is almost surely finite since \( {T\leq T’} \) with \( {T’=\inf\{n\geq0:(X_{3n},X_{3n+1},X_{3n+2})=(1,1,1)\}} \), and \( {T’} \) follows the geometric law of parameter \( {p^3>0} \) (coin tossing game). Next, by using the optional stopping theorem and then the monotone and the dominated convergence theorems, we obtain

\[ \mathbb{E}(S_T)=\mathbb{E}(T). \]

On the other hand we have by definition of \( {S} \) and \( {T} \) that

\[ S_T=\frac{1}{p}\left(1+\frac{1}{p}\left(1+\frac{1}{p}\right)\right). \]

In this example, the martingale is purely instrumental, and provides at the end a formula for \( {\mathbb{E}(T)} \). By using the same approach for the Gambler’s ruin problem, one can use the squared sum martingale in order to get the expectation of the ruin time, and even the exponential martingale in order to get the Laplace transform of the ruin time!

Martingales are a stochastic analogue of constant sequences: they are constant in expectation. Similarly, we may define sub-martingales, which are growing in expectation (they are below=sub a limit), and super-martingales, which are decreasing in expectation (they are above=sup a limit). Indeed if a sequence of random variables \( {M={(M_n)}_{n\geq0}} \) satisfies to \( {M_n\in L^1(\mathcal{F}_n)} \) for every \( {n\geq0} \), then it is

  • a sub-martingale when for every \( {n\geq0} \),

    \[ \mathbb{E}(M_{n+1}-M_n|\mathcal{F}_n)\geq0. \]

  • a super-martingale when for every \( {n\geq0} \),

    \[ \mathbb{E}(M_{n+1}-M_n|\mathcal{F}_n)\leq0. \]

By the Jensen inequality if \( {M} \) is a martingale such that \( {M_n\in L^2} \) for every \( {n\geq0} \) then \( {{(M_n^2)}_{n\geq0}} \) is a sub-martingale. If one defines \( {\left<M\right>={(\left<M\right>_n)}_{n\geq0}} \) by \( {\left<M\right>_0=0} \) and

\[ \left<M\right>_{n+1}-\left<M\right>_n =\mathbb{E}((M_{n+1}-M_n)^2|\mathcal{F}_n) =\mathbb{E}(M_{n+1}^2-M_n^2|\mathcal{F}_n) \]

then \( {{(M_n^2-\left<M\right>_n)}_{n\geq0}} \) is a martingale. The process \( {\left<M\right>} \) is called the increasing process of \( {M} \) or the quadratic variation of \( {M} \). It is also called the compensator of the sub-martingale \( {{(M_n^2)}_{n\geq0}} \). This process \( {\left<M\right>} \) is non-negative, non-decreasing, predictable, integrable. For example, if \( {M_n=X_1+\cdots+X_n} \) where \( {{(X_n)}_{n\geq0}} \) are iid with mean \( {0} \) and variance \( {\sigma^2} \), then \( {\left<M\right>_n=n\sigma^2} \).

Given that martingales are generalizations of sums of independent centered random variables, one may ask about some extension of the Doob maximal inequality, the law of large numbers and the central limit theorem.

The Doob maximal inequality for martingales allows to control the maximum by the terminal value. It states that if \( {M} \) is a \( {\geq0} \) martingale bounded in \( {L^p} \), \( {p>1} \), then

\[ \left\Vert \sup_{0\leq k\leq n}M_k\right\Vert_p \leq \frac{p}{p-1}\left\Vert M_n\right\Vert_p. \]

The basic theorems of convergence for martingales are the following:

  • If \( {M} \) is a martingale bounded in \( {L^p} \), with \( {p>1} \), meaning that \( {\sup_{n\geq0}\mathbb{E}(|M_n|^p)<\infty} \), then there exists a random variable \( {M_\infty\in L^p} \) such that

    \[ \lim_{n\rightarrow\infty}M_n=M_\infty \]

    almost surely and in \( {L^p} \). Here the almost sure convergence comes from the Doob maximal inequality for martingales and the Borel-Cantelli lemma, while the \( {L^p} \) convergence comes from the Cauchy criterion or from the uniform integrability which comes in turn from the boundedness in \( {L^p} \) with \( {p>1} \). Furthermore we have \( {M_n=\mathbb{E}(M_\infty|\mathcal{F}_n)} \);

  • If \( {M} \) is a sub-martingale such that \( {{(M_n^+)}_{n\geq0}} \) is bounded in \( {L^1} \), meaning that \( {\sup_{n\geq0}\mathbb{E}(\max(0,M_n))<\infty} \), then there exists a random variable \( {M_\infty\in L^1} \) such that

    \[ \lim_{n\rightarrow\infty}M_n=M_\infty \]

    almost surely. In particular, this holds for instance if \( {M} \) is a \( {\geq0} \) martingale since in this case \( {\mathbb{E}(\max(0,M_n))=\mathbb{E}(M_n)=\mathbb{E}(M_0)} \). The boundedness in \( {L^1} \) is not enough to ensure uniform integrability. The convergence holds in \( {L^1} \) if and only if \( {M} \) is uniformly integrable (counter example: critical Galton-Watson process, tends almost surely to \( {0} \) while keeping a mean of \( {1} \)). Other remarkable special cases are when \( {M} \) is a sub-martingale bounded above by a constant, or a super-martingale bounded below by a constant.

The law of large numbers for martingales states that if \( {M} \) is a martingale such that \( {M_n\in L^2} \) for any \( {n\geq0} \) and if \( {\left<M\right>_\infty=\lim_{n\rightarrow\infty}\left<M_n\right>} \) then there exists \( {M_\infty\in L^2} \) such that

  • on \( {\{\left<M\right>_\infty<\infty\}} \), we have, almost surely,

    \[ \lim_{n\rightarrow\infty} M_n=M_\infty; \]

  • on \( {\{\left<M\right>_\infty=\infty\}} \), we have, almost surely,

    \[ \lim_{n\rightarrow\infty}\frac{M_n}{\left<M\right>_n}=0, \]

    and various refinements are possible here, such as, almost surely, for any \( {\varepsilon>0} \),

    \[ \frac{M_n^2}{\left<M\right>_n}=o((\log(\left<M\right>_n))^{1+\varepsilon}). \]

The central limit theorem for martingales states that if \( {M} \) is a martingale such that \( {M_n\in L^2} \) for any \( {n\geq0} \) and if \( {{(a_n)}_{n\geq0}} \) is a deterministic sequence such that

  • \( {a_n\geq0} \) for any \( {n\geq0} \) and \( {a_n\nearrow\infty} \) as \( {n\rightarrow\infty} \);
  • there exists a real number \( {\ell\geq0} \) such that

    \[ \frac{\left<M\right>_n}{a_n}\overset{\mathbb{P}}{\underset{n\rightarrow\infty}{\longrightarrow}}\ell; \]

  • the so-called Lindeberg condition is satisfied: for any \( {\varepsilon>0} \),

    \[ \frac{1}{a_n}\sum_{k=1}^n\mathbb{E}(|M_{k}-M_{k-1}|^2\mathbf{1}_{|M_{k+1}-M_k|\geq\varepsilon\sqrt{a_n}}|\mathcal{F}_{k-1}) \overset{\mathbb{P}}{\underset{n\rightarrow\infty}{\longrightarrow}}0; \]

then we have

\[ \frac{M_n}{\sqrt{a_n}} \overset{\mathrm{law}}{\underset{n\rightarrow\infty}{\longrightarrow}} \mathcal{N}(0,\ell), \]

and moreover if \( {\ell>0} \) then

\[ \sqrt{a_n}\frac{M_n}{\sqrt{\left<M\right>_n}} \overset{\mathrm{law}}{\underset{n\rightarrow\infty}{\longrightarrow}} \mathcal{N}\left(0,\ell^{-1}\right). \]

The Lindeberg condition expresses the fact that some sort of global variance at time \( {n} \) is well spread across the increments of the martingale. You may take a look at a former post about such aspects in the case of sums of independent random variables (sparsity and localization). One can satisfy the Lindeberg condition by checking the so-called Lyapunov condition, which is a bit simpler: for some real \( {p>2} \),

\[ \frac{1}{a_n}\sum_{k=1}^n\mathbb{E}\left(|M_{k}-M_{k-1}|^p|\mathcal{F}_{k-1}\right) \overset{\mathbb{P}}{\underset{n\rightarrow\infty}{\longrightarrow}}0. \]

The central limit theorem for martingales provides many examples of Gaussian fluctuations with a speed which is not \( {\sqrt{n}} \). One may think for example about the number of tables in the chinese restaurant process, for which \( {a_n=\theta\log(n)} \).

Many aspects of this post are inspired by my teaching at École Polytechnique, and by the 2007 book co-authored with Bernard Bercu (in French).

Further reading.

Share
Categories: Probability