SSJ  3.2.1
Stochastic Simulation in Java
 All Classes Namespaces Functions Variables Pages
umontreal::ssj::markovchainrqmc Namespace Reference

Classes for the simulation of Markov chains with RQMC and Array-RQMC. More...


class  ArrayOfComparableChains< T extends MarkovChainComparable >
 This class provides tools to simulate an array of MarkovChainComparable objects with the array-RQMC method of [124], [127] . More...
class  ArrayOfDoubleChains
 Similar to ArrayOfComparableChains, except that instead of working with \(n\) clones of a MarkovChain, we use a single MarkovChainDouble object for all the chains. More...
class  MarkovChain
 This class defines a generic Markov chain and provides basic tools to simulate it for a given number of steps or until it stops and recover the performance measure. More...
class  MarkovChainComparable
 A subclass of Markov chain for which there is a total ordering between the states in each dimension induced by the implementation of the MultiDimComparable interface in package umontreal.ssj.util. More...
class  MarkovChainDouble
 A special kind of Markov chain whose state space is a subset of the real numbers. More...

Detailed Description

Classes for the simulation of Markov chains with RQMC and Array-RQMC.

This package provides tools to implement and use discrete-time Markov chains (DTMC) and simulate them with RQMC methods.

A DTMC is an important class of Markovian processes with time index \(I=\{0,1,2,…\}\). It is defined as a sequence \(\{X_i, i\in I\}\) of random variables ( \(X_i\) represents the state at index \(i\)), all defined on the same probability space. The evolution of the states is determined by the stochastic recurrence

\[ X_0 = x_0, \qquad X_j = \varphi(X_{j-1},U_j), \]

where the \(U_j\) are independent random variables uniformly distributed over \([0,1)^d\). Here, the dimension \(d\) is usually 1, but can be larger.

A performance mesure \(Y_i\) is defined over this sequence as

\[ Y_i = \sum_{j=1}^i c_j(X_j). \]

The \(c_j\) are some cost (or revenue) function at step \(j\). The objective is to estimate \(\mu=\mathbb E[Y_{\tau}]\), where \(\tau\) is a stopping time (fixed or stochastic). It is possible that \(c_j(\cdot)=0\) for all \(j<\tau\).

The basic class is umontreal.ssj.markovchainrqmc.MarkovChain which contains methods to simulate steps of the Markov chains or several runs and store the performance mesure in a statistical collector. Simulation can be done using Monte Carlo or quasi-Monte Carlo.

To use these methods, one must implement a class inheriting from umontreal.ssj.markovchainrqmc.MarkovChain and implementing its three abstract methods: initialState() resets the chain to its initial state \(x_0\); nextStep(stream) advances the chain by one step from the current state using a random stream, it represents function \(\varphi(\cdot)\); getPerformance() returns the performance mesure of the chain, the value of \(Y_i\) where \(i\) is the current step.

However, it is recommended to inherit from umontreal.ssj.markovchainrqmc.MarkovChainComparable (if the chains can be sorted) or umontreal.ssj.markovchainrqmc.MarkovChainDouble (special case for one dimensional state) which are subclasses of umontreal.ssj.markovchainrqmc.MarkovChain, rather than directly from this class. Some other methods are then needed. See examples below for more details.

The classes umontreal.ssj.markovchainrqmc.ArrayOfComparableChains and umontreal.ssj.markovchainrqmc.ArrayOfDoubleChains can be used to work with multiple Markov chains in parallel. The chains can then be sorted using method umontreal.ssj.markovchainrqmc.ArrayOfComparableChains.sortChains. These classes also provide methods to simulate using the array-RQMC method of [124] .


The following examples demonstrate how to implement and use a Markov chain using this package.

First, the class displayed in Listing  Brownian shows a very simple implementation of a umontreal.ssj.markovchainrqmc.MarkovChainComparable. It represents a Brownian motion over the real line. The starting position x0 as well as the time step dt are given in the constructor. Each step represents a move which is represented by the addition of a normal variable of mean \(0\) and variance dt to the current position. The performance mesure here is just the positive distance between the current position and the initial position, but it could be anything else.

A simple implementation of MarkovChainComparable  [Brownian]

The program displayed in Listing  BrownianTest shows different ways to use the Markov chain.

1- How to simulate the trajectory and print the state of the chain at each step and the performance at the end.

2- How to simulate using Monte Carlo to get an unbiased estimator of the expectation of the performance and an estimation of its variance. If stream is a umontreal.ssj.hups.PointSetIterator, use umontreal.ssj.markovchainrqmc.MarkovChain.simulRunsWithSubstreams instead of umontreal.ssj.markovchainrqmc.MarkovChain.simulRuns. The umontreal.ssj.stat.Tally is a statistical collector; see package umontreal.ssj.stat for how to use it.

3- Same as 2 but with randomized quasi-Monte Carlo. Basically, it takes a umontreal.ssj.hups.PointSet where the dimension of the points is the number of steps and the number of points is the number of trajectories. The umontreal.ssj.hups.PointSetRandomization must be compatible with the point set. See package umontreal.ssj.hups more information on these classes.

4- Same as 2 but with the array-RQMC method (see [125] ). The umontreal.ssj.markovchainrqmc.ArrayOfComparableChains is used to simulate chains in parallel. It uses a umontreal.ssj.hups.PointSetRandomization to randomize the point sets and a umontreal.ssj.util.MultiDimSort to sort the chains. Here, as the chain is one-dimensional, the sort used is a umontreal.ssj.util.OneDimSort. It is important to call umontreal.ssj.markovchainrqmc.ArrayOfComparableChains.makeCopies(int) in order to set the number of chains. See package umontreal.ssj.util for more information on sorts.

5- How to simulate the trajectories with array-RQMC and do something with the chains at each step. The Do something with mc comment should be replaced by anything, using the umontreal.ssj.markovchainrqmc.MarkovChain mc. For example to store or print the state x of each chain for a later use.

Tests using a MarkovChainComparable  [BrownianTest]

The output of this program is displayed in Listing  BrownianTestOutput. For this example, the variance of the estimator with RQMC is 6.25 times less than MC, and 388 times less with array-RQMC compared to MC.

Output of  [BrownianTestOutput]