94
5 Sampling
And substituting the definition of a ij , we obtain
j =i
P (s i |s j )P eq (s j ) + (1 −
j =i
P (s j |s i ))P eq (s i ) = P eq (s i ) .
(5.63)
Then the equation that gives the convergence condition is found as
j =i
P (s i |s j )P eq (s j ) − P (s j |s i )P eq (s i )
= 0 .
(5.64)
This is called the master equation.
One of the solutions of this master equation is the principle of detailed balance,
as described below:
P (s i |s j )P eq (s j ) = P (s j |s i )P eq (s i ).
(5.65)
Note that this is a sufficient condition for the convergence of Markov chains.
The principle of detailed balance gives a sufficient condition for the convergence
of Markov chains, and there is a freedom in choosing the transition probability
P (s i |s j ) that appears there. In the following, we first explain the Markov chain
Monte Carlo method, which is one of the applications, and in the next section we
will introduce a typical choice of P (s i |s j ).
Here, let us mention the difference between the weather problem mentioned in
the previous section and the Markov chain Monte Carlo method. In the weather
model, given the transition matrix T, the convergence destination P eq was determined later. On the other hand, when using the Markov chain Monte Carlo method,
P eq is known, and T is designed accordingly. The guideline for the design is the
principle of the detailed balance.
5.2.5 Expectation Value Calculation Using Markov chains,
and Importance Sampling
From the above discussion, it was found that the equilibrium distribution P eq can be
obtained by using a Markov chain satisfying appropriate conditions. In the actual
calculations, it is not possible to take the exact limit n → ∞, so the calculation will
be performed in the following procedures.
First, we consider the probability distribution after starting from an appropriate
state and making enough transitions. In other words, for k 1, we consider
P eq ≈ T
k P 0 = P
(k)
eq,app .
(5.66)
5 Sampling
And substituting the definition of a ij , we obtain
j =i
P (s i |s j )P eq (s j ) + (1 −
j =i
P (s j |s i ))P eq (s i ) = P eq (s i ) .
(5.63)
Then the equation that gives the convergence condition is found as
j =i
P (s i |s j )P eq (s j ) − P (s j |s i )P eq (s i )
= 0 .
(5.64)
This is called the master equation.
One of the solutions of this master equation is the principle of detailed balance,
as described below:
P (s i |s j )P eq (s j ) = P (s j |s i )P eq (s i ).
(5.65)
Note that this is a sufficient condition for the convergence of Markov chains.
The principle of detailed balance gives a sufficient condition for the convergence
of Markov chains, and there is a freedom in choosing the transition probability
P (s i |s j ) that appears there. In the following, we first explain the Markov chain
Monte Carlo method, which is one of the applications, and in the next section we
will introduce a typical choice of P (s i |s j ).
Here, let us mention the difference between the weather problem mentioned in
the previous section and the Markov chain Monte Carlo method. In the weather
model, given the transition matrix T, the convergence destination P eq was determined later. On the other hand, when using the Markov chain Monte Carlo method,
P eq is known, and T is designed accordingly. The guideline for the design is the
principle of the detailed balance.
5.2.5 Expectation Value Calculation Using Markov chains,
and Importance Sampling
From the above discussion, it was found that the equilibrium distribution P eq can be
obtained by using a Markov chain satisfying appropriate conditions. In the actual
calculations, it is not possible to take the exact limit n → ∞, so the calculation will
be performed in the following procedures.
First, we consider the probability distribution after starting from an appropriate
state and making enough transitions. In other words, for k 1, we consider
P eq ≈ T
k P 0 = P
(k)
eq,app .
(5.66)