September 29, 2012 at 9:21 pm (Monte Carlo)
Tags: Sequential monte carlo, SMC, SMC sampler
Sequential Monte Carlo (SMC) methods are usually designed to deal with probability distributions of increasing dimensions. The canonical example is the sequence of distributions where is a hidden Markov chain and is an observation process. The notation is a shortcut for . This is usually called a Hidden Markov Model in the literature. If the Markov chain evolves on in then the distribution is a probability on .
It turns out that one can use the same kind of ideas to study a single distribution . If is difficult to sample directly from and that it is difficult to use traditional MCMC methods (because of the dimensionality, multi-modality, poor mixing properties, etc…), one can try to use SMC methods to study the distribution . To this end, one can introduce a sequence of bridging distributions
where is typically very easy to sample from and . A traditional choice is where . The bigger the index , the more intricate the distribution is. The problem is that each distribution has the same dimensionality as the original distribution so that it is difficult to use all the machinery of SMC methods. For the sake of concreteness, let us suppose that is a distribution on . A fundamental remark that is the base of what is now known as Sequential Monte Carlo samplers is that can be seen as the marginal distribution of the probability
where are Markov kernels in the sense that for any we have . The distribution lives on and one can use the traditional SMC methods to explore the sequence of distributions . This algorithm was devised a few years ago by Pierre Del Moral, Arnaud Doucet and Ajay Jasra. It is extremely powerful and several other algorithms can be seen as particular cases of it. Because I had never implemented the algorithm before, I tried yesterday to see how this worked on a very simple example. My target distribution was an equal mixture of seven Gaussian distributions in with unit covariance matrices and centred at the vertices of a regular heptagon with radius . I started with particles at the centre of the heptagon and let them evolved according to a random walk. When the Effective Sampling Size (ESS) was too small (less than ), the whole particle system was regenerated. In order to obtain a sweet movie, I used bridge distributions .
The result is clear and quite impressive. Indeed, this could have been made much more efficient by taking much less bridge distributions. Some recent theory has been developed to analyse the stability of the algorithm in high dimensional situations. The analysis described in the article uses a scaling limit approach very similar to some ideas used to analyse MCMC algorithms and some more recent developements along the same lines that we have done with Andrew and Natesh. Very exciting stuff!
[EDIT: 2 October 2012]
I received several emails asking me to describe how to obtain the short animation showing the evolution of the particles system. The code is available here. This is a quick python script producing a bunch of .png files. It then suffices to stick them together to obtain an animated .gif file. This can for example easily be done using the free (and very good) photoshop-like software GIMP. Open all the png files as different layers. Export the result as a .gif file with the option ‘animated gif’ checked. Voila!
September 22, 2012 at 9:12 pm (markov chain, probability, Uncategorized)
Tags: coin toss, first step analysis, markov chain, martingale
Start flipping a coin. How long should you wait (on average) before observing the pattern !? Easy you might say, that’s simply the hitting time of the state starting from state of the following Markov chain.
Indeed, one can solve this kind of problem using a first step analysis. In other words, if is the expected number of steps before reaching starting from , is the expected number of steps before reaching starting from , is the expected number of steps before reaching starting from , etc… one can readily see that verify the system of equations
After a finite amount of time and coffee one then come up with the answer . That was a little bit tedious and I don’t really want to know how long one should wait on average before observing the sequence .
It turns out that there is a very neat way to approach this kind of problems without solving any linear system. Apparently, this trick was discovered in the 80s by Shuo-Yen Robert Li. As often in probability, this boils down to introducing a clever martingale. Suppose that one wants to know how long it takes on average before observing the magic coin pattern of length with for all . To this end, one will introduce an army of gamblers, a casino, a game of chance and a martingale. The martingale describes the amount of money earned by the casino. At each round (starting at round ) the casino tosses a coin and the gamblers can make bets. If a gambler starts betting just before round , he wins if the coin shows . If he decides to bet again at round , he wins if the coin shows , etc… Suppose that there are infinitely many gamblers and that gambler starts betting just before round . The game is fair in the sense that if a gambler bets an amount , with probability he gets and with probability he losses his bet. One supposes that gambler starts betting dollar just before round and keeps reinvesting his total capital until he either losses everything (total loss equals dollar) or observes the magic coin pattern (total earning equals ). Indeed, the amount of money earned by the casino is a martingale and . For example, if the first gambler loses his bet and if the wins. Consider the time when the magic coin pattern first appears. This is a stopping time and the optional stopping theorem for martingales shows that . Indeed, one can also compute this quantity another way. By time , all the losers have given dollar to the casino. Also, if the gambler is still in the game he has won a total amount . in other words,
where if the gambler is still in the game after the round and otherwise. The fundamental remark is that the quantity is not random so that . Indeed, right after round one can know with certainty whether is still in the game or not. Gambler is in the game only if the last letters of the magic word are the same as the first letters. For example, if the magic word is then the gamblers who have seen the pattern , and at time are still in the game when the magic word first appear. In this case this shows that .
For example, this immediately shows that we have to wait on average coin tosses before observing the pattern .