Press "Enter" to skip to content

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

How to speed up MCMC algorithms

Markov-Chains-Monte-Carlo (MCMC for short) methods are widely used in practice for the approximate computation of integrals on various types of spaces. More precisely, let \(\mu\) be a probability measure on \(E\), known only up to a multiplicative constant. Let \(K\) be an irreducible Markov kernel on \(E\). Then by using a classical Metropolis-Hastings type construction, one cook up a computable ergodic Markov kernel \(M\) on \(E\) which admits \(\mu\) as a unique reversible invariant law. One can then simulate a Markov chain \((X_n)_{n\geq1}\) with state space \(E\) and kernel \(M\). When \(n\) is large, the law of the random variable \(X_n\) is approximately \(\mu\). The construction of \(K\) relies in general on the knowledge of the local structure of \(E\). The quantitative control of the speed of convergence is a delicate problem. Many research articles are devoted to specific models. You may take a look at the expository article of Laurent Michel and of Persi Diaconis.

It is well known that nonreversible ergodic Markov chains can avoid diffusive effects and may converge faster than reversible ergodic Markov chains. It is thus tempting to think about nonreversible MCMC algorithms. This program is currently under developpement. You may take a look at the recent work of Diaconis, Miclo, and Zuñiga on the spectral analysis of second order Markov chains i.e. \(\mathcal{L}(X_{n+1}|X_n,X_{n-1},\ldots)=\mathcal{L}(X_{n+1}|X_n,X_{n-1})\).

Leave a Comment

Books on combinatorial optimization, information, and algorithms

Leave a Comment

Free software

If you are looking for a free software clone of Matlab (numerical matrix computation), give a try to GNU Octave/QtOctave or to FreeMat or to Scilab. If you are looking for a free software clone of Maple (computer algebra system), give a try to Giac/Xcas or  to Maxima/wxMaxima. You may also take a look at SAGE. If you are looking for a free software clone of S-Plus (statistical data analysis and graphical representation), give a try to GNU R. If you want to install GNU/Linux on your desktop or laptop computer, try Ubuntu, which is based on Debian GNU/Linux. If your laptop is a MacBook, you may also take a look at the MacBook Ubuntu Community Documentation. If you like Unix but feel that GNU/Linux is too gregarious, give a try to FreeBSD (powers Mac OS X).

Leave a Comment

Mean of a random variable on a manifold

Let $ X$ be a random variable on a manifold $latex M$. Is there a nice (intrinsic?) definition of the mean of $latex X$ and of its variance? This funny question comes from concrete motivations (imaging). What can be done with a chart? The problem here is that the mean is  a global notion.

If $latex M$ has global coordinates or almost global, like stereographical projections for spheres, one may use them. This is ugly and non canonical. If $latex M$ is a Lie group, one may use the exponential map. When $latex M$ is equipped with a Riemannian metric $latex d:M\times M\to\mathbb{R}_+$ one may think about using a variational approach, and simply define the mean $latex m$ of $latex X$ as

$latex \displaystyle m:=\arg\min_{x\in M}\mathbb{E}(d(x,X)^2)$.

The value of the minimum is the variance of $latex X$. This definition  does not always provide a unique point on $latex M$, as shown by the  example of the uniform law on spheres for which every point is a mean! This is not a bug, it is a feature, a geometrical feature due to the invariance of the law by isometries in this example. One can ask about an empirical estimator of the mean, and its asymptotic fluctuations. For some answers, see e.g. the work of Pennec and Bhattacharya and Bhattacharya. The variational expression of $latex d$ in terms of geodesics is valid up to the cut-locus/injectivity-radius of the exponential map.

Beyond the mean, the law of $latex X$ may be viewed as the linear form

$latex f\in\mathcal{C}_b(M,\mathbb{R})\mapsto\mathbb{E}(f(X)).$

This does not rely on the manifold nature of $latex M$ since we only use the fact that $latex M$ is a topological space. Note that if $latex M$ is an open subset of $latex \mathbb{R}^d$ then we recover the usual $latex \mathbb{E}(X)$ by approximation via dominated convergence. The integrability of $latex X$  is the class of functions for which the map above is finite. In some sense, $latex \mathbb{E}(X)$ is an element of the bidual $latex M”$ of $latex M$, provided that we view $latex M’:=\mathcal{C}_b(M,\mathbb{R})$ as a sort of dual of $latex M$. Of course, $latex M\subset M”$ via the canonical injection but the converse does not hold in general.

If $latex (X_n)_{n\geq0}$ is an irreducible positive recurrent aperiodic Markov chain with state space $latex M$ and unique invariant law $latex \mu$ then the law of large numbers states that with probability one, and regardless of the initial law of the chain, we have

$latex \displaystyle \frac{1}{n}\delta_{X_1}+\cdots+\frac{1}{n}\delta_{X_n} \underset{n\to\infty}{\overset{\mathcal{C}_b(M,\mathbb{R})}{\longrightarrow}}\mu.$

The asymptotic fluctuations of this convergence are described by a central limit theorem, which involves the variance for $latex \mu$ of the solution of the Poisson equation associated to the dynamics.

1 Comment
Syntax · Style · Tracking & Privacy.