HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
ON SIMULATING A MARKOV CHAIN STATIONARY DISTRIBUTION WHEN TRANSITION PROBABILITIES ARE UNKNOWN
Abstract

DAVID ALDOUS

We present an algorithm which, given a n-state Markov chain whose steps can be simulated, outputs a random state whose distribution is within of the stationary distribution, using O(n) space and O( ² ) time, where is a certain ``average hitting time" parameter of the chain.

Back to Discrete Probability and Algorithms Table of Contents


Go