{menu secondaire item-03}

Résumé Séminaire -- VINCENT

The famed perfect sampling method of Propp and Wilson (1996) uses   a backward coupling scheme 
to compute unbiased samples of the  stationary distribution of Markov chains. It has been implemented
 in a software tool, called PSI2,  that proved very efficient for monotone chains coming  from  queuing
networks.

However, when the  system includes at least one non-monotone event, the backward simulation scheme
has to  consider all possible states as starting points. This can be avoided by taking a new point of view
that consists in bounding all possible trajectories of the Markov chain  by envelopes.  The new approach
presents these latest improvements, including  envelope techniques and splitting. Envelopes have been
introduced  in Valuetools (2008). As soon as envelopes couple, then all trajectories must have coupled,
so that an unbiased sample is obtained. As for splitting, it consists in  generating all the trajectories of
the Markov chains inside the envelopes to run a classical backward coupling technique from that point on.

Combining these two techniques in PSI2 makes it a more efficient tool that covers a  wider class of queuing
networks than previously. This includes networks with non-monotone events such as negative customers,
arrivals by batches,  forks and  joins as well as Cox-distribution for services.