Nous sommes tous des faussaires

June 27th, 2015 No comments

Guy Ribes - Autoportrait d'un faussaire

« Comme pour n’importe quel tableau, chaque faux suppose une recherche. Un peintre, qu’il soit faussaire ou non, est, toute sa vie, un étudiant qui se met à l’école de l’art. Je n’ai pas fait un seul Matisse ou un seul Renoir, je les ai faits en dix exemplaires, jusqu’à ce que je comprenne leur nature et leur sens. On ne peut pas créer une œuvre de cette importance du premier coup. On commet des erreurs, on détruit, on recommence… » Guy Ribes (1948 – ) in Autoportrait d’un faussaire, p. 120, 2015.

La lecture de l’autoportrait de Guy Ribes est passionnante ! On y trouve le récit d’une vie romanesque, une description sans fard du marché de l’art, mais aussi, au fil des pages, une réflexion pleine de fraîcheur sur la création et l’originalité. Peut-on classer les artistes en créateurs et interprètes ? La réalité est beaucoup plus complexe, en peinture comme en musique ou en mathématiques. D’une certaine manière, les mathématiciens sont eux aussi des faussaires, créant bien souvent des œuvres à la manière de, comme le faisait Guy Ribes.

« Qu’est-ce que, au fond, un peintre ? C’est un collectionneur qui veut se constituer une collection en faisant lui-même les tableaux qu’il aime chez les autres. C’est comme ça que je commence et ça devient autre chose. … C’est par ce qu’on ne réussit pas à imiter un maître qu’on fait quelque chose d’original. » Pablo Picasso (1881 – 1973), in Daniel-Henry Kahnweiler Huit entretiens avec Picasso, Le Point, Mulhouse, n°XLII, oct. 1952, p. 22-30.

Share
Categories: Mathematicians, Society

Kirchhoff determinant and Markov chain tree formulas

June 21st, 2015 No comments
Gustav Robert Kirchhoff

Gustav Robert Kirchhoff (1824 – 1887)

This post is devoted to the Gustav Kirchhoff formula which expresses the invariant measure of an irreducible finite Markov chain in terms of spanning trees. Many of us have already encountered the name of Gustav Kirchhoff in Physics classes when studying electricity.

Let \( {X={(X_t)}_{t\geq0}} \) be a continuous time Markov chain with finite state space \( {V=\{1,\ldots,n\}} \), and with infinitesimal generator or Q-matrix \( {Q} \), meaning that

\[ Q_{i,j}=\partial_{t=0^+}\mathbb{P}(X_t=j|X_0=i), \quad \mathbb{P}(X_t=j|X_0=i)=\left(e^{tQ}\right)_{i,j}. \]

The off-diagonal entries of \( {Q} \) are non-negative and the rows of \( {Q} \) have zero sum:

\[ \forall i,j\in V, \quad i\neq j, \quad Q_{i,j}\geq0, \quad Q_{i,i}=-\sum_{k\neq i}Q_{i,k}. \]

The skeleton graph \( {G=(V,E)} \) of \( {Q} \) is the oriented graph defined by

\[ (i,j)\in E\quad\mathrm{iff}\quad Q_{i,j}>0. \]

Let us assume that \( {Q} \) is irreducible, which means that \( {G} \) is connected. The Perron-Frobenius theorem states then that there exists a unique invariant probability measure, in other words \( {\mathrm{ker}(Q^\top)} \) contains up to scaling a unique vector with positive coordinates. We will provide an explicit formula for it!

Since the sum of the columns of \( {Q} \) is zero, it follows that for every \( {i,j\in V} \),

\[ (\mathrm{cof}(-Q))_{i,j}:=(-1)^{i+j}\det(-Q^{(i,j)})=\det(-Q^{(i,i)})=:\mu_i. \]

In other words the cofactors matrix of \( {-Q} \) has constant rows (identical columns). Now by expanding the determinant along an arbitrary column \( {j\in V} \) we get

\[ 0=\det(-Q)=-\sum_{i=1}^nQ_{i,j}(-1)^{i+j}\det(-Q^{(i,j)}) =-\sum_{i\in V}Q_{i,j}\mu_i \]

which shows that the vector \( {{(\mu_i)}_{i\in V}} \) is invariant for \( {Q} \). The fact that \( {{(\mu_i)}_{i\in V}} \) has positive coordinates follows from the Kirchhoff formula

\[ \mu_i:=\det(-Q^{(i,i)})=\sum_{T\in\mathcal{T}_i}\prod_{(j,k)\in T}Q_{j,k} \]

where the sum runs over the set \( {\mathcal{T}_i} \) of spanning trees of \( {G} \) rooted at \( {i} \). Recall that a spanning tree or covering tree of \( {G} \) rooted at \( {i\in V} \) is a sub-graph of \( {G} \) with edge set \( {V} \) which is a tree rooted at \( {i} \). Note that \( {\mathcal{T}_i} \) is non-empty since \( {G} \) is connected. Note that \( {\mathcal{T}_1,\ldots,\mathcal{T}_n} \) do not have necessarily the same cardinal due to the fact that the edges are oriented: a covering tree rooted at \( {i} \) contains any \( {j} \) as a vertex but not necessarily as a possible root due to the arrows.

To prove the Kirchhoff formula, one can first label from \( {1} \) to \( {m=|E|} \) the edges of \( {G} \), and define an \( {n\times m} \) matrix \( {L} \) called the incidence matrix as follows: if \( {(i,j)} \) is the \( {k} \)-th edge of \( {G} \) then \( {L_{i,k}=Q_{i,j}^{1/2}} \), \( {L_{j,k}=-Q_{i,j}^{1/2}} \), and \( {L_{\cdot,k}=0} \) otherwise. Now

\[ -Q=LL^\top. \]

We also have \( {Q^{(i,i)}=L^{(i)}(L^{(i)})^\top} \). Next we use the Cauchy-Binet formula

\[ \det(-Q^{(i,i)}) =\sum_{s}\det(L^{(i,s)})^2 \]

where \( {s} \) runs over the subsets of cardinality \( {m-(n-1)} \). Every \( {s} \) specifies \( {n-1} \) edges of \( {G} \). It can then be shown that these edges induce a spanning tree iif \( {\det(L^{(i,s)})\neq0} \).

Random walk. Suppose now that \( {Q_{i,j}\in\{0,1\}} \) for every \( {i,j\in V} \) with \( {i\neq j} \). Then \( {X} \) is the nearest neighbors random walk on \( {G} \), the diagonal of \( {-Q} \) is formed by the degree sequence of \( {G} \), and \( {Q} \) is the Laplacian \( {\Delta_G} \) of \( {G} \). In this case \( {Q_{j,k}=1} \) for every \( {(j,k)\in G} \) and thus the Kirchhoff formula above boils down to

\[ \forall i\in V,\quad \mu_i=|\mathcal{T}_i|. \]

Suppose now that \( {Q} \) is additionally symmetric, meaning that \( {G} \) is not oriented in the sense that \( {(j,k)\in E} \) iff \( {(k,j)\in E} \). In this case the invariant probability measure of \( {Q} \) is then the uniform law on \( {V} \). Due to the absence of orientation, the sets \( {\mathcal{T}_1,\ldots,\mathcal{T}_n} \) have the same cardinal \( {\kappa} \), which is the number of spanning trees of \( {G} \) (without rooting). We have

\[ \forall i,j\in V,\quad \mu_i=(\mathrm{cof}(-Q))_{i,j}=(-1)^{i+j}\det(-Q^{(i,j)}) =|\mathcal{T}|_i=\kappa. \]

In other words the cofactors matrix of the Laplacian of a non-oriented graph has constant entries equal to the number of spanning trees of the graph.

Let us connect \( {\kappa} \) with the eigenvalues of the the symmetric matrix \( {-Q} \), numbered as

\[ 0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_n. \]

Here \( {\lambda_1} \) is simple since \( {Q} \) is irreducible. The characteristic polynomial of \( {-Q} \) is

\[ P_{-Q}(x)=\det(xI_n+Q)=x(x-\lambda_2)\cdots(x-\lambda_n). \]

By looking at the coefficient of \( {x} \) in this polynomial we get (Jacobi formula)

\[ (-1)^{n-1}\lambda_2\cdots\lambda_n =(-1)^{n-1}\mathrm{Tr}(\mathrm{cof}(-Q)) \]

which gives finally the remarkable Kirchhoff formula

\[ \lambda_2\cdots\lambda_n=n\kappa. \]

(note that the left hand side is thus necessarily an integer!). Let us show how to recover from this formula the so-called Cayley formula which states that the complete graph \( {K_n} \) possesses \( {n^{n-2}} \) covering trees. In this case \( {G=K_n} \) and \( {-Q=nI-J} \) where \( {J} \) is the \( {n\times n} \) matrix full of \( {1} \). The matrix \( {-J} \) has rank \( {1} \), its eigenvalues are \( {0} \) with multiplicity \( {n-1} \) and \( {-n} \) with multiplicity \( {1} \), and thus it follows that the eigenvalues of \( {-Q} \) are \( {0} \) with multiplicity \( {1} \) and \( {n} \) with multiplicity \( {n-1} \). Hence \( {\lambda_2=\cdots=\lambda_n=n} \) and finally \( {\kappa=n^{n-2}} \).

Wilson algorithm. David Wilson invented an exact algorithm to generate a spanning tree of \( {G} \) which follows the uniform distribution on the set of spanning trees of \( {G} \). Starting from vertex \( {1} \), the algorithm consists in setting \( {A_1=\{1\}} \), and to simulate a path of the simple random walk on \( {G} \) started from vertex \( {2} \) until it reaches \( {A_1} \). Then \( {A_2} \) is the union of \( {A_1} \) and of the loop erased version of this path. If \( {A_2=V} \), the algorithm is stopped. If not, then we redo the same starting this time the path from smallest vertex not in \( {A_2} \), stopping the path when it reaches \( {A_2} \), and so on. The Wilson algorithm can be naturally related to the Green function of the random walk on \( {G} \) with Dirichlet boundary conditions on a subset of \( {V} \).

Markov matrix tree theorem. The Kirchhoff formula provides an exact and non-asymptotic formula for the invariant probability measure of a finite Markov chain (this is sometimes referred to as the Kirchhoff Markov matrix tree theorem). This is remarkable, and constitutes an alternative to the asymptotic formula

\[ \forall i,j\in V,\quad \mu_j=\left(\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{k=0}^{m-1} e^{kQ}\right)_{i,j}. \]

Further reading.

Share

Quelques aspects du temps présent

June 20th, 2015 No comments
Categories: Society

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