Simulation
- Chp 12 : Markov Chain Monte Carlo Methods
12.1 Markov Chains
Consider a collection of random variables . If there exists a set
of numbers , such that whenever the process is in state then, independent of the past states,
the probability that the next state is is , then we say that the collection
constitutes a
Markov chain having transition probabilities .
A Markov chain is said to be irreducible if for each pair of states
and there is a positive probability,
starting in state , that the
process will ever enter state .
For an irreducible Markov chain, let denote the long-run proportion of
time that the process is in state .
The are often called
the stationary probabilities of the Markov chain.
An irreducible Markov chain is said to be aperiodic if for some and some state ,
When , the Markov chain is said to be time
reversible.
12.2 The Hastings-Metropolis
Algorithm
Let be
positive numbers, and . Suppose that is
large and is difficult to
calculate, and that we want to simulate a random variable (or a sequence
of random variables) with probability mass function
One way of simulating a sequence of random variables whose
distributions converge , is to find a Markov chain that is easy to simulate and whose
limiting probabilities are the . The Hastings-Metropolis
algorithm provides an approach for accomplishing this task.
Let be an irreducible Markov
transition probability matrix on the integers , with , representing the row , column element of . Now define a Markov chain as follows. When , a random variable such that , is
generated. If , then is set equal to with probability and is set equal to with probability . Under these
conditions, it is easy to see that the sequence of states will
constitute a Markov chain with transition probabilities given by
Now this Markov chain will be time reversible and have stationary
probabilities if
which is equivalent to
It is now easy to check that this will be satisfied if we take
Note that if then , and vice versa. We should note that the value of is not needed to define the Markov
chain, as the values
suffice.
The following sums up the Hastings-Metropolis algorithm for
generating a time-reversible Markov chain whose limiting probabilities
are .
Choose an irreducible Markov transition probability matrix with transition probabilities . Also, choose
some integer value between and .
Let and .
Generate a random variable
such that
and generate a random number .
If then ; else .
.
Go to .
12.3 The Gibbs Sampler
The most widely used version of the Hastings-Metropolis algorithm is
the Gibbs sampler.
12.4
Continuous time Markov Chains and a Queueing Loss Model