        Perfect Simulation Scheme For Processes With Long Memory :
           A ``Coupling Into And From The Past'' Algorithm
    
      author: Aurélien Garivier
     ............................................................

# DESCRIPTION:

This package contains a matlab implementation of the algorithm described in [1].
This algorithm performs perfect simulation for stationary processes described by a transition kernel. 
These includes, in particular, variable length Markov Chains and Context Trees.

It uses object oriented programming, and thus requires a not-too-old version of matlab.

The term "CIAFTP" comes from [D. B. Wilson, How to couple from the past using a read-once source of randomness, Random Structures Algorithms 16 (2000), no. 1, 85–113].


# CONTENT: 

Files included in the current release:

	README 										this file
	demoPerfectSim.m    			demonstration file for the package
	+Context/									the package in itself
	  +Context/dist2str.m			internal: tweaked version of num2str specially dedicated to discrete distributions
	  +Context/Example1.m 		matlab class for the kernel of Section 7.1	(see the second example of demoPerfectSim.m)
	  +Context/Kernel.m				matlab class for the transition kernels (contains function CIAFTP for perfect simulation)
	  +Context/mynum2str.m 	 	internal: personal version of num2str for integers between 0 and 9
	  +Context/part2str.m			internal: modification of num2str specially dedicated to partitions of [0,1]
	  +Context/PCfunction.m 	matlab class for piecewise constant function on the set of semi-infinite sequences
	  +Context/Trie.m					matlab class for trees with edges labelled by integers
	  +Context/VLMC.m					matlab class for constructing a kernel via a VLMC representation (see the first example of demoPerfectSim.m)
	 	  	  	  

# HOWTO: 

run 'demoPerfectSim' to illustrate the Coupling Into And From The Past (CIAFTP) algorithm on the example of a simple Variable Length Markov Chain (press a key to trigger each iteration).

run 'demoPerfectSim(2)' to illustrate the Coupling Into And From The Past (CIAFTP) algorithm on the example of Section 7.1 in the paper (press a key to trigger each iteration).

run 'demoPerfectSim(3)' to illustrate the Coupling Into And From The Past (CIAFTP) algorithm on the example of a deep, sparse Variable Length Markov Chain (press a key to trigger each iteration).


# REFERENCE:
	[1] Perfect Simulation Scheme For Processes With Long Memory :
  A `Coupling Into And From The Past' Algorithm, by Aurélien Garivier 
