SSJ
3.3.1
Stochastic Simulation in Java

Tools to simulate Markov chains with the ArrayRQMC method. More...
Classes  
class  ArrayOfComparableChains 
This class provides tools to simulate an array of MarkovChainComparable objects with the arrayRQMC method of [139], [141] . 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 to recover the performance measure. More...  
class  MarkovChainComparable 
A subclass of MarkovChain for which there is a total ordering between the states, induced by the implementation of the umontreal.ssj.util.MultiDimComparable interface. More...  
class  MarkovChainDouble 
A special kind of Markov chain whose state space is a subset of the real numbers. More...  
Tools to simulate Markov chains with the ArrayRQMC method.
This package provides facilities designed specifically to simulate discretetime Markov chains (DTMC) with the ArrayRQMC method [139], [141], [143] . With this method, several realizations of the Markov chain are simulated in parallel. At each step, the chains are sorted (in some way) based on the value of their current state, then all the chains are simulated for one more step using an RQMC point set. We now give more details on the setting.
A DTMC can be written as \(\{X_i, i\in I\}\) where \(I=\{0,1,2,…\}\), \(X_i \in \mathcal{S}\) represents the state at step \(i\), and the state space \(\mathcal{S}\) is arbitrary. Typically, \(\mathcal{S} \subseteq \mathbb{R}^\ell\) for some \(\ell\geq 1\). We assume that the state evolves according to the stochastic recurrence
\[ X_0 = x_0, \qquad\mbox{ and } X_j = \varphi(X_{j1},\mathbf{U}_j) \mbox{ for } j\ge 1, \]
where the \(\mathbf{U}_j\) are independent random variables uniformly distributed over \([0,1)^d\) for some integer \(d \geq 1\) (it is often 1, but can be larger). A performance mesure \(Y_\tau\) is defined over this sequence as
\[ Y = Y_{\tau} = \sum_{j=1}^\tau c_j(X_j), \]
where \(c_j\) is a cost (or revenue) function for step \(j\) and \(\tau\) is either a constant of a random stopping time. Often, \(c_j\) does not depend on \(j\). The goal is to estimate \(\mu=\mathbb E[Y_{\tau}]\). It is not rare that \(c_j(\cdot)=0\) for all \(j<\tau\), i.e., that the cost or revenue occurs only at the end.
The base class MarkovChain offers methods to simulate one or more copies of the Markov chain one step at a time, or over several steps, collect the realizations of $Y$ in statistical probes, make several independent replications of that, etc. The chains can be simulated by Monte Carlo, RQMC, or ArrayRQMC.
To use these tools, one must define a subclass of MarkovChain and implement its three abstract methods: initialState() which resets the chain to its initial state \(x_0\); nextStep(stream) which advances the chain by one step from the current state using a random stream (it represents function \(\varphi(\cdot)\)); and getPerformance() which returns the performance realization for the chain, i.e., the value taken by \(Y_{\tau}\), assuming that the chain has reached its stopping time $$.
If the chains have to be sorted as in the ArrayRQMC method, one must implement the MarkovChainComparable interface, unless the chain is a subclass of MarkovChainDouble,
in which case the state is just a real number and the chains are sorted by increasing order of their state in a trivial way. For a direct subclass of MarkovChain, other methods are then needed. See the examples below for more details.
The classes ArrayOfComparableChains and ArrayOfDoubleChains work with multiple Markov chains in parallel. They implement ArrayRQMC. The chains can be sorted using the method ArrayOfComparableChains.sortChains.
The following examples demonstrate how to use this package.
MarkovChainDouble
. The class displayed in Listing Brownian shows a 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 quasiMonte 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 arrayRQMC method of [139] . The 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 onedimensional, 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 arrayRQMC and do something with the chains at each step. The Do something with mc
comment should be replaced by anything, using the 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 arrayRQMC compared to MC.
Output of BrownianTest.java [BrownianTestOutput]