Random Variate Generation and Markoc Vhain Monte Carlo

Stochastic simulation is a tool of well known and appreciated importance in many fields of research and application. To use stochastic simulation the generation of random variates from different distributions is a necessary prerequisite. Therefore the first considerations how to generate random numbers started already in the fifties of the last century. Many methods for sampling from standard distributions have been proposed. The design goals for these algorithms are speed and little memory requirements. If random variates from non-standard distributions or for special simulation problems are required new algorithms are necessary. In the last decade so- called automatic methods have been developed that allow to sample from a large class of distributions with a single piece of code. These algorithms are efficient and have some advantages that makes them attractive even for sampling from standard distributions. The price for using such algorithms is that a setup is required that might be quite expensive for some methods/distributions. Although some research was done there are still a lot of open generation problems. In the framework of Markov Chain Monte Carlo (MCMC) sampling routines with a fast setup are needed. Methods for sampling independent points from multivariate distributions are important but existing algorithms are slow or work only for low dimensions. For quasi-Monte Carlo methods (QMC) the development of fast automatic algorithms to generate non-uniformly distributed low-discrepancy sequences (quasi-random variates) is required. Another problem is that the mathematical theory behind such automatic methods is based on real numbers, whereas the environment in wich the algorithms are implemented uses so-called floating point numbers which have a limited precision, usually 16 decimal digits. The aim of this project is to find some solutions to these and similar problems.

Many observations we make in real world can be described by so called stochastic processes: results of gambling, weather forecast, stock prices, development of sales figures, evolution of species, passenger volume at an airport, and many more. For the description of these phenomena probability theory and statistics provide us with very powerful tools to "handle the unpredictable". The observed variables are then described by their random distributions that are themselves depicted by some characteristic figures, usually mean values and variances. For complex models, however, computing these figures can be quite a challenging task. Stochastic simulation is then a surprisingly simple solution for this problem: Draw a random number for each random variable in your model and look what happens; repeat this procedure many times and average over all your results. Thus we get a good estimate for our figures of interest. The result is valid with a high probability (which we are free to choose ourselves). This simple approach is even used for problems which do not have any intrinsic randomness. So called "randomized algorithms" replace the difficult original problem by a stochastic one where we can use stochastic simulation. Both applications are often called "Monte Carlo methods". The crucial point of all these algorithms is that we need a procedure for drawing random samples. In practice, one uses so called pseudo-random numbers (that look like truly random numbers from a statistical point of view) or quasi-random numbers (highly uniform point sets, that are used like random numbers but promise more accurate results). This task is usually split into two parts: First a uniformly distributed point set is generated. In a second step this set is transformed into a set of points that follows the desired distribution. For commonly used distributions there already exist many algorithms to perform the latter. However, there exists an increasing number of problems where new methods for this transformation step are required. The project`s goal was to provide easy-to-use tools for such situations. The resulting algorithms work in an almost automatic way, i.e. a user of these has to provide some information about the distribution in question and gets a random sample. We have improved this tool set by improving the performance of some existing algorithms by reducing memory requirements, setup time or by increasing accuracy of numerical approximations. We also reduced some burden of providing high quality information, i.e. difficult to compute data are now calculated during the setup of the sampling routines and need not be provided by the user. Additionally we have created new automatic methods for high-dimensional problems. Since it is our opinion that numerical methods should be easily applicable for other researchers and practitioners we have developed an open source library that provides an interface to our new algorithms. It can be used in a compiled simulation program but it also can be made available in interactive working environments.