This project extends and improves Monte Carlo sampling techniques. The main idea is to incorporate ideas that originated in quasi-Monte Carlo sampling into Monte Carlo sampling. In particular this project embeds quasi-Monte Carlo sampling into Markov chain Monte Carlo simulations, a combination that until recently was not known to be possible. The combination can be very effective, bringing variance reductions of over 100 fold in some problems. The project personnel are identifying when quasi-Monte Carlo brings a large improvement in Markov chain Monte Carlo, as well as finding new ways to combine the methods. Another area in which this project is improving Monte Carlo sampling is in integration of unbounded functions. There are versions of randomized quasi-Monte Carlo sampling that attain a better convergence rate than the original quasi-Monte Carlo sampling, at least for well behaved integrands. Unfortunately, problems with unbounded integrands don't see much improvement. This project extends the benefit of randomized quasi-Monte Carlo sampling to unbounded integrands by applying a change of variable formula to bound the integrand while endeavoring to prevent the integrand from becoming too spiky. This project is also investigating tempering methods for speeding up the mixing of Markov chain Monte Carlo as well as applications of Monte Carlo and quasi-Monte Carlo ideas to problems in bioinformatics.
Monte Carlo sampling is used in just about every branch of science and engineering. At its simplest it involves simulating a system using random number generators, and recording what happens. In practice Monte Carlo methods are used to solve by brute force computation some problems that are too hard to do mathematically. Real world complications that can easily be introduced into a simulation often make a problem too hard for exact mathematical treatment. Quasi-Monte Carlo methods can be used to drive a simulation byt replacing the random number sequence by very carefully chosen numbers that are much more balanced than random numbers are. The result is often a tremendous speedup for a given level of accuracy, or a tremendous increase in accuracy for a given computation time. This project pushes quasi-Monte Carlo methods into simulations that had hitherto been thought incapable of benefiting from them. Those simulation techniques, known as Markov chain Monte Carlo, are used in many areas including materials science, analysis of educational testing data sets, biomedical research, robotics, computer graphics, and marketing. This project is also looking at other ways to improve Monte Carlo methods with similarly broad potential for benefit.
