An adventure with Google search

May 11th, 2015 No comments

googleI had an interesting experience with Google recently, related to Electronic Journal of Probability (EJP) and Electronic Communications in Probability (ECP). As a managing editor of EJP and ECP, I check from time to time how EJP and ECP do appear in Google Search. Bizarrely, more than one year ago, the URLs http://ejp.ejpecp.org/ and http://ecp.ejpecp.org/, which are the main URLs of the journals, have completely lost their rank in Google searches. The first result given by the Google search engine for the search “Electronic Journal of Probability” was the mirror site http://www.emis.ams.org/journals/EJP-ECP, while the main URL http://ejp.ejpecp.org/ was not present in the first pages of results.  A scandal! The problem seemed specific to the Google search engine, and Microsoft Bing for instance was not affected.

It took me more than a year to solve this ranking problem. My first attempt was to contact some people that I know in San Francisco to obtain a contact at Google. This approach gave nothing. Google is huge. My second attempt consisted in using Google Webmaster Tools, a service provided by Google to fine tune the interaction between a website and the Google search engine. This approach gave me some interesting information on the websites but no clue on the source of the initial problem.

Finally, after few months of various attempts, I decided to explain my problem in the Webmaster Central Help Forum of the Google Product Forums. Several contributors provided very quickly various tentative explanations, leading at the end to the solution of the problem. In fact, the domain ejpecp.org was considered by Google as being parked! That is why its rank was so low! The reason was first the presence of an HTTP 302 temporary redirection (instead of an HTTP 301 permanent redirection) of the URL http://www.ejpecp.org/ to http://journals.ejpecp.org/, and second the presence of advertisement front-pages on non-used sub-domains such as www.ejp.ejpecp.org set by the DNS  provider (which is NetworkSolutions as one can check in the whois database). The solution was then easy to implement: modify the HTTP redirection and the DNS tables. It works now!

Share
Categories: Computers

Recueil de modèles aléatoires

April 21st, 2015 3 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 (PDF) 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 !

Ce recueil de modèles aléatoires nécessite un niveau de Master en probabilités et statistique. Il puise sa source dans les cours de Master de mathématiques et de préparation à l’agrégation de mathématiques, que nous avons dispensés, pendant plusieurs années, aux étudiants des universités de Toulouse, Rennes, Marne-la-Vallée, Paris-Dauphine, et Tours. Le parti pris est de polariser la rédaction par les modèles plutôt que par les outils, et de consacrer chaque séance ou chapitre à un modèle. Bien que parfois reliés, les chapitres sont essentiellement autonomes. Ils ne contiennent pas de rappels de cours sur les outils fondamentaux comme les théorèmes limites, les martingales à temps discret, et les chaînes de Markov à espace d’état au plus dénombrable, pour lesquels d’excellentes références sont disponibles. Chaque chapitre commence par une liste de mots-clés et se termine par quelques notes et commentaires pour aller plus loin. La liste des thèmes abordés n’a rien de canonique ni d’exhaustif, mais constitue un panorama varié, que nous espérons enrichissant.

Ce livre n’est pas fait pour être lu linéairement et ne constitue en aucune manière un cours, ni une liste de leçons d’agrégation. Son format condensé est un parti pris. Les chapitres ne sont pas tous du même niveau de difficulté. La grande étendue thématique des modèles sélectionnés a pour but d’encourager les lecteurs à élargir leur horizon probabiliste en excitant leur curiosité. Voici la 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