How to couple from the past using a read-once source of randomness (Q4943355)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1416164
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | How to couple from the past using a read-once source of randomness |
scientific article; zbMATH DE number 1416164 |
Statements
4 January 2001
0 references
coupling from the past
0 references
Poisson arrivals see time average
0 references
PASTA-type theorems
0 references
perfect sampling algorithms
0 references
How to couple from the past using a read-once source of randomness (English)
0 references
0.8224700689315796
0 references
0.8216637372970581
0 references
0.8101779222488403
0 references
0.8087812066078186
0 references
The author gives a new method for generating perfectly random samples from the stationary distribution of a Markov chain. His method is related to ``coupling from the past'' (CFTP), but only runs the Markov chain forwards in time, and never restarts it at previous times in the past. The method is also related to an idea known as PASTA (``Poisson arrivals see time average'') in the operations research literature. One of the mantraps of CFTP, a class of algorithms for perfectly generating random samples from Markov chain, is that one needs to be prepared to re-use old random coins. The method is based on the principle that a Markov chain that has already been running for an infinitely long time has already reached its stationary distribution. To obtain a random sample, CFTP ``figures out'' what state the Markov chain is in at a given time, by looking at a finite but unbounded number of randomizing operations used prior to that time. The main result is stated as follows: Every version of CFTP for which: (i) i.i.d. randomizing operations are used to do the updates, (ii) the algorithm produces the random sample, in its entirely and with full precision, after composing finitely many random maps, (iii) the random maps can be evaluated at a given starting state without affecting coalescence detection, can be done with a read-once stream of random coins. Furthermore, the expected running time and memory usage are never worse by more than a (small) constant factor. Open problems are the existence of a better read-once version of CFTP, and the existence of further connections between PASTA-type theorems and perfect sampling algorithms.
0 references