Press "Enter" to skip to content

Libres pensées d'un mathématicien ordinaire Posts

Circular law theorem for random Markov matrices

I have uploaded on arXiv a paper written with Charles Bordenave and Pietro Caputo entitled Circular Law Theorem for Random Markov Matrices. We provide, probably for the first time, an almost sure  circular law theorem for a model of random matrices with dependent entries and finite positive variance. This work leads us to formulate some open problems of variable difficulty, listed at the end of the introduction. Feel free to solve them!

To be a bit more precise, let $latex (X_{jk})_{jk\geq1}$ be i.i.d. nonnegative random variables with bounded density, mean $latex m$, and finite positive variance $latex \sigma^2$. Let $latex M$ be the $latex n\times n$ random Markov matrix with i.i.d. rows defined by $latex M_{jk}=X_{jk}/(X_{j1}+\cdots+X_{jn})$.  Let $latex \lambda_1,\ldots,\lambda_n$ be the eigenvalues of $latex \sqrt{n}M$ i.e. the roots in $latex \mathbb{C}$ of its characteristic polynomial. Our main result states that with probability one, the counting probability measure $latex \frac{1}{n}\delta_{\lambda_1}+\cdots+\frac{1}{n}\delta_{\lambda_n}$ converges weakly as $latex n\to\infty$ to the uniform law on the disk $latex \{z\in\mathbb{C}:|z|\leq m^{-1}\sigma\}$ (circular law).

In particular, when $latex X_{11}$ follows an exponential law, the random matrix $latex M$ belongs to the Dirichlet Markov Ensemble of random stochastic matrices, and our main result gives a positive answer to the question raised in a previous paper.

The matrix $latex M$ is Markov: its entries belong to $latex [0,1]$ and each row sums up to $latex 1$. It has equally distributed dependent entries. However, the rows of $latex M$ are i.i.d. and follow an exchangeable law on $latex \mathbb{R}^n$ supported by the simplex. Since $latex \sigma<\infty$, the uniform law of large numbers of Bai and Yin states that almost surely

$latex \displaystyle\max_{1\leq i\leq n}\left|X_{i1}+\cdots+X_{in}-nm\right|=o(n)$.

This suggests that $latex m^{-1}\sqrt{n}M$ is approximately equal to $latex n^{-1/2}X$ for $latex n$ large enough. One can then expect that almost surely the counting probability measure of the singular values of $latex \sqrt{n}M$ will converge as $latex n\to\infty$ to  a quartercircular law while the counting probability measure of the eigenvalues of $latex \sqrt{n}M$ will converges to a circular law. We show that this heuristics is valid. There is however a complexity gap between these two statements due to the fact that for nonnormal operators such as $latex M$, the eigenvalues are less stable than the singular values under perturbations (here the least singular value enters the scene).

The proof of the main result is inspired from the Tao and Vu version of the Girko Hermitization via logarithmic potentials. More precisely, the starting point is the following Hermitization identity valid for any $latex n\times n$ complex matrix $latex A$ and any $latex z$ outside the spectrum of $latex A$:

$latex \displaystyle \frac{1}{n}\sum_{k=1}^n\log|\lambda_k(A)-z|=\frac{1}{n}\sum_{k=1}^n\log(\lambda_k(\sqrt{(A-zI)(A-zI)^*})).$

The left hand side is the logarithmic potential at point $latex z$ of the counting probability measure of the eigenvalues of $latex A$. The right hand side is the integral of $latex \log(\cdot)$ for the counting probability measure of the singular values of $latex A-zI$. Thanks to the Girko Hermitization theorem, the problem boils down then to show that for Lebesgue almost all $latex z\in\mathbb{C}$, almost surely,

  1. the counting probability measure $latex \nu_{\sqrt{n}M-zI}$ of the singular values of $latex \sqrt{n}M-zI$ tends weakly as $latex n\to\infty$ to a deterministic probability measure $latex \nu_z$ related to the circular law
  2. the function $latex \log(\cdot)$ is uniformly integrable for the sequence $latex (\nu_{\sqrt{n}M-zI})_{n\geq1}$

For the first statement, we use a result of Dozier and Silverstein, which is based on Hermitian techniques: truncation, centralization,  recursion for the Cauchy-Stieltjes transform (trace of the resolvent) via Sherman-Morrison bloc inversion, producing finally a cubic equation for the Cauchy-Stieltjes transform of the limiting law.

The second statement  involves as essential ingredients a Talagrand concentration inequality (for the control of the distance of rows to the span of other rows), and a polynomial control of the operator norm of the resolvent (i.e. the least singular value of $latex \sqrt{n}M-zI$). The bounded density assumption is purely technical and comes from the way we control the operator norm of the resolvent. A possible route for the removal of this assumption is to control the least singular value for a certain kind of matrices with independent rows.

1 Comment

Deux questions entre statistique et calcul stochastique

Qu’elle est la meilleure manière de simuler la loi de la variable aléatoire \( {Z=\int_0^1\!f(t)\,dB_t} \) où \( {f:[0,1]\rightarrow\mathbb{R}} \) est une fonction déterministe sympathique et où \( {(B_t)_{t\geq0}} \) est un mouvement brownien standard issu de \( {0} \) ?

Soit \( {(\mathcal{F}_t)_{t\geq0}} \) la filtration naturelle de \( {(B_t)_{t\geq0}} \) définie par \( {\mathcal{F}_t=\sigma(B_s)_{0\leq s\leq t}} \) pour tout \( {t\geq0} \). Soit \( {0\leq t_1\leq \cdots\leq t_r\leq 1} \) une suite de temps. Considérons une fonction aléatoire \( {F:[0,1]\times \Omega\rightarrow\mathbb{R}} \) de la forme

\[ F(t,\omega)=\sum_{i=1}^{r-1} E_i(\omega) \mathbf{1}_{[t_i,t_{i+1})} \]

où pour tout \( {1\leq i\leq r-1} \) la variable aléatoire \( {E_i} \) est \( {\mathcal{F}_{t_i}} \) mesurable. On dispose alors de la formule stochastique suivante :

\[ I(F)=\int_0^1\!F(t,\cdot)\,dB_t=\sum_{i=1}^{r-1}E_i(B_{t_{i+1}}-B_{t_i}). \]

Cette formule permet de définir par un procédé d’approximation des intégrales stochastiques plus générales pour des fonctions \( {F} \) plus complexes, cf. par exemple Oksendal pour une introduction accessible, et Revuz & Yor, Karatzas & Shreve, et Chung & Williams pour aller plus loin. Lorsque les variables aléatoires \( {(E_i)_{1\leq i\leq n}} \) sont déterministes, la variable aléatoire \( {I(F)} \) est gaussienne centrée et sa variance se calcule directement par bilinéarité. Revenons à la question posée. La fonction \( {F} \) est déterministe (\( {F(\cdot,\omega)=f} \)) et la variable aléatoire \( {Z} \) est gaussienne centrée. La variance de \( {Z} \) se calcule au moyen de l’isométrie d’Itô :

\[ \mathbb{E}[Z^2] =\mathbb{E}\left[\left(\int_0^1\!f(t)\,dB_t\right)^2\right] =\mathbb{E}\left[\int_0^1\!f(t)^2\,dt\right] =\int_0^1\!f(t)^2\,dt. \]

Pour simuler \( {Z} \), il suffit donc de pré-calculer ou d’approcher par une méthode numérique l’intégrale déterministe \( {\iota=\int_0^1\!f(t)^2\,dt} \) puis de simuler la loi gaussienne \( {\mathcal{N}(0,\iota)} \). Pour s’en convaincre, lorsque \( {f=\mathbf{1}_{[0,t]}} \) on trouve \( {\iota=t} \) et donc \( {Z\sim\mathcal{N}(0,t)} \), ce qui est bien normal car pour cette fonction \( {f} \) la variable aléatoire \( {Z} \) vaut \( {B_t} \).

On peut également voir l’intégrale stochastique \( {Z} \) comme la valeur au temps \( {1} \) de la solution \( {(X_t)_{0\leq t\leq 1}} \) de l’équation différentielle stochastique (EDS) très simple \( {dX_t=f(t)dB_t} \) avec condition initiale \( {X_0=0} \). Ainsi, toute méthode de simulation approchée de cette EDS permet en particulier de simuler de manière approchée \( {Z} \). Une méthode classique pour les EDS : les schémas d’Euler, cf. par exemple Kloeden & Platen, Kloeden & Platen, ou Iacus. Cependant, pour la question posée, l’EDS est si simple que la méthode explicite gaussienne évoquée précédemment est préférable. Les schémas d’Euler permettent de simuler de manière approchée la solution d’EDS plus générales de la forme

\[ dX_t=f(t,X_t)dB_t+g(t,X_t)dt \]

dont la solution n’est pas forcément gaussienne (dès lors que \( {f(t,x)} \) dépend de \( {x} \) où que \( {g(t,x)} \) n’est pas affine en \( {x} \). Lorsque \( {f(t,x)=\alpha} \) et \( {g(t,x)=-\beta x} \) on obtient un processus gaussien d’Ornstein-Uhlenbeck) :

\[ X_1=\int_0^1\!f(t,X_t)\,dB_t + \int_0^1\!g(t,X_t)\,dt. \]

Ces méthodes numériques sont utilisées en finance mathématique, cf. par exemple Karatzas & Shreve. En statistique, les intégrales stochastiques gaussiennes apparaissent par exemple dans des théorèmes limites du type TCL, cf. également les problèmes statistiques liés aux processus de diffusion, cf. par exemple Kutoyants.

Les schémas d’Euler pour les EDS peuvent être poussés à des ordres plus élevés. Le schéma de Milstein par exemple correspond à une approximation à l’ordre deux, peu utilisée toutefois en pratique. On distingue l’erreur d’approximation forte de l’erreur d’approximation faible (i.e. en espérance, qui fait gagner un ordre de puissance \( {n^{1/2}} \) où \( {n} \) est le nombre de pas de discrétisation du temps). Pour ces aspects, on pourra consulter par exemple Kloeden & Platen, Kloeden & Platen, et Bouleau & Lépingle. Des approches plus originales figurent dans Gaines & Lyons, Gaines & Lyons, Lyons & Victoir, Pagès.

Sot \( {(B_t)_{t\geq0}} \) un mouvement brownien standard issu de \( {0} \) et \( {f:\mathbb{R}_+\rightarrow\mathbb{R}} \) une fonction lisse. Soit \( {(X_t)_{t\geq0}} \) la solution de l’équation différentielle stochastique (EDS) suivante : \( {dX_t=dB_t+f(t)dt} \), \( {X_0=0} \). Qu’elle est la densité de la loi de \( {(X_t)_{t\geq0}} \) par rapport à \( {(B_t)_{t\geq0}} \), sur l’espace des trajectoires ? Comment s’exprime la \( {\log} \)-vraisemblance ?

On a \( {X_t=\int_0^t\!f(s)\,ds+B_t\sim\mathcal{N}(\int_0^t\!f(s)\,ds,t)} \) pour tout \( {t\geq0} \). Le processus \( {(X_t)_{t\geq0}} \) est gaussien, de même fonction de covariance que \( {(B_t)_{t\geq0}} \). La densité de la loi de \( {(X_t)_{t\geq0}} \) par rapport à \( {(B_t)_{t\geq0}} \), sur l’espace des trajectoires est donnée par la formule de Cameron-Martin-Girsanov, cf. Oksendal (théorème 8.6.4 page 162 et exemple 8.6.5 page 164). Plus précisément, soit \( {H} \) une fonction qui dépend de la trajectoire sur l’intervalle de temps \( {[0,t]} \). Par exemple, une fonction de la forme \( {H(x_{[0,t]}) = \mathbf{1}_{x_{s_1} \in A_1}\cdots\mathbf{1}_{x_{s_n} \in A_n}} \) où les \( {s_i} \) sont fixés dans \( {[0,t]} \) et où les \( {A_i} \) sont des boréliens de \( {\mathbb{R}} \). Alors on a

\[ E\left[H(X_{[0,t]})\right] = E\left[H(W_{[0,t]}) Q((W_{[0,t]})\right] \]

\[ \log Q(W_{[0,t]}) := \int_0^t\!f(s)\,dB_s +\frac{1}{2}\int_0^t\!f(s)^2 ds. \]

La fonction \( {Q} \) est la densité recherchée par rapport à la loi de \( {(B_t)_{t\geq0}} \) sur \( {[0,t]} \). Comme la motivation de la question est de calculer des vraisemblances, on souhaite surtout exprimer \( {Q} \) en terme de \( {(X_t)_{t\geq0}} \) plutôt qu’en terme de \( {(B_t)_{t\geq0}} \). Or l’EDS donne immédiatement

\[ \log Q = \int_0^t\!f(s)\,dX_s – \frac{1}{2}\int_0^t\!\!f^2(s)\,ds, \]

qui est la \( {\log} \)-vraisemblance recherchée. Au passage, quand \( {f} \) est constante et égale à un réel \( {\theta} \), on trouve bien que le maximum de vraisemblance en \( {\theta} \) vaut \( {X_t/t} \). \`A présent, pour deux fonctions \( {f} \) et \( {g} \) et une trajectoire observée \( {X_{[0,t]}} \), le logarithme du rapport de vraisemblance vaut :

\[ \int_0^t\!(f-g)(s)\,dX_s – \frac{1}{2}\int_0^2\!(f^2-g^2)(s)\,ds. \]

On peut également exprimer \( {\log(Q)} \) encore plus simplement car la dérive \( {f(t)dt} \) dans l’EDS considérée est déterministe. Plus précisément, la formule d’Itô donne la formule d’intégration par parties suivante :

\[ \int_0^t\!f(s)\,dB_s = f(t) B_t – \int_0^t\!B_s f'(s)\,ds, \]

cf. Oksendal (théorème 4.1.5 page 46), et en utilisant l’EDS, la \( {\log} \)-vraisemblance \( {\log(Q)} \) s’écrit :

\[ f(t) X_t – \int_0^t\!X_s\,f'(s)\,ds – \frac{1}{2}\int_0^t\!f^2(s)\,ds. \]

Remarque à retenir : si \( {\mathcal{W}} \) is la mesure de Wiener standard et \( {\mathcal{W}_f} \) la mesure de Wiener translatée par une fonction \( {f} \), alors \( {\mathcal{W}_f} \) est absolument continue par rapport à \( {\mathcal{W}} \) si et seulement si \( {f} \) appartient à l’espace de Cameron-Martin, et la densité est donnée par la formule de Girsanov.

Ce billet est inspiré de questions posées par Anne-Laure Fougères et Béatrice Laurent-Bonneau.

Leave a Comment

Phi-entropies

I have updated my brief survey article in the EVOL ANR encyclopedia on $latex \Phi$ entropy and $latex \Phi$ Sobolev inequalities.

Leave a Comment

Sherman inverse problem for Markov matrices

Let $latex X$ be an $latex n\times n$ complex matrix. The eigenvalues $latex \lambda_1(X), \ldots, \lambda_n(X)$ of $latex X$ are the roots in $latex \mathbb{C}$ of its characteristic polynomial. We label them in such a way that

$latex \displaystyle |\lambda_1(X)|\geq\cdots\geq|\lambda_n(X)|$

with growing phases. The spectral radius of $latex X$ is $latex \rho(X):=|\lambda_1(X)|$. The singular values

$latex \displaystyle s_1(X)\geq\cdots\geq s_n(X)$

of $latex X$ are the eigenvalues of the positive semi-definite Hermitian matrix $latex \sqrt{XX^*}$ where $latex X^*$ is the conjugate-transpose of $latex X$. We have thus $latex s_k(X)=\sqrt{\lambda_k(XX^*)}$. The operator norm of $latex X$ is $latex \Vert X\Vert_{2\to2}=s_1(X)$. Geometrically, the matrix $latex X$ maps the unit sphere to an ellipsoid, and the half lenghts of the principal axes of this ellipsoid are exactly the singular values of $latex X$.

H. Weyl has shown in 1949 that for every $latex k\in\{1,\ldots,n\}$, we have

$latex \displaystyle \prod_{i=k}^ns_k(X)\leq\prod_{i=k}^n|\lambda_i(X)| \quad\text{and}\quad \prod_{i=1}^k|\lambda_i(X)|\leq\prod_{i=1}^ks_k(X). $

This expresses a two ways logarithmic majorization. Note that we recover the radius/norm bound $latex \rho(X)\leq\Vert X\Vert_{2\to2}$. Note also that one may deduce the second Weyl inequalities from the first ones by using them for the inverse of $latex X+\varepsilon I$ (and conversely).  Note moreover that

$latex \displaystyle\prod_{i=1}^n|\lambda_i(X)|=\prod_{i=1}^ns_i(X)=|\det(X)|$.

In 1954, A. Horn has shown that any sequences of numbers in $latex \mathbb{C}$ and $latex \mathbb{R}_+$ satisfying to the Weyl inequalities and the ordering that we used are actually the eigenvalues and singular values of a complex matrix. This  solves positively a problem formulated by S. Sherman.

We say that $latex X$ is Markov (or stochastic) if $latex X$ has entries in $latex [0,1]$ and each row sums up to $latex 1$. The spectrum of $latex X$ is then included in the unit disc of the complex plane, contains $latex 1$, and is symmetric with respect to the real axis. With the Weyl-Sherman-Horn inverse problem in mind, one can ask about the possible set of singular values for a Markov matrix with prescribed  eigenvalues. One may also reverse the question. One has to take into account the additional symmetries due to the periods. Actually, instead of the singular values of $latex M$, it is maybe more natural, from a Markovian point of view, to consider the spectrum of $latex \sqrt{MM^{*\mu}}$ where $latex M^{*\mu}$ is the adjoint of $latex M$ for $latex \ell^2(\mu)$ where $latex \mu$ is the invariant measure of $latex M$ (when $latex M$ is irreducible). This remark leads to many other questions.

The content of this post is inspired from informal discussions with Laurent Miclo during the EVOL workshop held in Hammamet in May 2010.

Leave a Comment