Labo ID

Laboratoire Informatique et Distribution

Athapascan-0 Athapascan-1 Athapascan-tr Pajé Givaro PEPS PSI Takakaw Ka-Tools NFSP

PSI Team

Florent Morata   ID-IMAG
Corine Marchand   ID-IMAG
Jean Marc Vincent   ID-IMAG

PSI Presentation

PSI (Perfect Simulator) is a simulation software of markovian models. It be able to simulate discrete and continuous time models to provide a perfect sampling of the stationary distribution or directly a sampling of functional of this distribution.
The simulation kernel is based on the CFTP algorithm, and the internal simulation of transitions on the Aliasing method.

Theorical Background


The Coupling From The Past algorithm, designed by Propp & Wilson (1996), gives a method to directly generate a sample acording to the stationary distribution of Markov chains.
The sheme is to consider all possible initial values and observe their trajectories. Nevertheless, to obtain an exact sample, we must run the simulation from a distant point in the past until the present. The stopping criteria is simply the coalesce of different trajectories at time 0.


Aliasing method, designed by Walker (1974), is a reject simulation technique for discrete distributions. This technique is different to classical reject method, because all the values are considered.
The main advantage is to fast simulate any arbitrary distributions : its needs a (pseudo) random called, one comparison, and at most two memory references.

PSI Versions

PSI 1.0 release 1 is written in C++ language, and exists in two versions :

    - Unix : classical use of shell commands.
    - Textual interface : utilization of user interface.

PSI Home Page