Page 126 - A First Course In Stochastic Models

118 DISCRETE-TIME MARKOV CHAINS

For the generated sequence of successive states X 0 , X 1 , . . . , it holds that
n N
1
lim f (X k ) = f (j)π j with probability 1
n→∞ n
k=0 j=1
for any given function f . Thus the Metropolis—Hastings algorithm can be used to
find performance measures of the Markov chain {X n } such as the long-run average
cost per time unit when a cost structure is imposed on the Markov chain.
The most widely used version of the Metropolis—Hastings algorithm is the
Gibbs sampler. Suppose that (N 1 , . . . , N d ) is a d-dimensional stochastic vector
whose probability distribution

p(x 1 , . . . , x d ) = P {N 1 = x 1 , . . . , N d = x d }
is known up to a multiplicative constant. This situation will be encountered in
Section 5.6 in the context of a closed queueing network. In this particular applica-
tion the univariate conditional distribution

P {N k = x k |N j = x j for j = 1, . . . , d with j = k} (3.4.17)
is explicitly known for each k = 1, . . . , d. In order to apply the Gibbs sampler,
it is required that the univariate conditional distributions in (3.4.17) are known.
The Gibbs sampler generates a sequence of successive states (x 1 , . . . , x d ) from a
Markov chain whose equilibrium distribution is given by p(x 1 , . . . , x d ).

Gibbs sampler
Step 0. Choose an initial state x = (x 1 , . . . , x d ).
Step 1. For the current state x choose a coordinate which is equally likely to be
any of the coordinates 1, . . . , d. If coordinate k is chosen, then generate a random
variable Y whose probability distribution is given by
P {Y = y} = P {X k = y|X j = x j for j = 1, . . . , d with j = k}.

If Y = y, let the candidate state y = (x 1 , . . . , x k−1 , y, x k+1 , . . . , x d ).
Step 2. The next state x = (x 1 , . . . , x d ) is set equal to y. Repeat step 1 with this
new state x.
The Gibbs sampler uses the Metropolis—Hastings algorithm with the choice
1
m x,y = P {X k = y|X j = x j for j = 1, . . . , d with j = k}
d
for the Markov matrix M. It is not difficult to verify that for this choice the
acceptance probability α x,y is given by

p(y)p(x)
α x,y = min , 1 = 1.
p(x)p(y)
Hence the candidate state is always accepted as the next state of the Markov chain.