92
5 Sampling
5.2.4 Master Equation and the Principle of Detailed Balance
In this subsection, we derive the principle of detailed balance, a sufficient
condition for a Markov chain to converge to a probability distribution. The previous
subsection introduced a Markov chain for two states, and this subsection deals with
N states. (States labeled by continuous variables are not described here.) For later
purposes, we change the label of the number of steps from n to t.
Given a state, the probability of giving it should be defined, so we define the
probability as a function of the state:
[Probability that state s i is realized at step t of Markov chain] ≡ P (s i ; t).
(5.50)
Since we are at least in one of the states at each step t, we require the following:
1 =
i
P (s i ; t).
(5.51)
Let P (s j |s i ) be the transition probability from state s i to s j . 18 Let us require
that all probabilities at the step t and the next step t + t satisfy the following
conservation law of probability. Recalling the conservation law of energy and that
of charge in fluid mechanics and electromagnetism in a unit spatial volume, since
the change of s i = the amount flowing out of −s i + the amount coming in s i , the
conservation law should be
P (s i ; t + t) − P (s i ; t)
t
= −
j =i
P (s i ; t)P (s j |s i ) +
j =i
P (s j ; t)P (s i |s j ).
(5.52)
By slightly modifying this, we get the probability of realizing the state s i at the step
t +
P (s i ; t + t) = P (s i ; t) −
j =i
P (s i ; t)P (s j |s i ))t +
j =i
P (s j ; t)P (s i |s j ))t.
(5.53)
The second term on the right-hand side is the probability of exiting the state s i , and
the third is the probability of becoming the state s i .
Next, we introduce a probability vector for the N states,
P(t) =
⎛
⎜
⎜
⎜
⎝
P (s 1 ; t)
P (s 2 ; t)
. . .
P (s N ; t)
⎞
⎟
⎟
⎟
⎠
.
(5.54)
18 This is a conditional probability, but in this context it is called a transition probability.
5 Sampling
5.2.4 Master Equation and the Principle of Detailed Balance
In this subsection, we derive the principle of detailed balance, a sufficient
condition for a Markov chain to converge to a probability distribution. The previous
subsection introduced a Markov chain for two states, and this subsection deals with
N states. (States labeled by continuous variables are not described here.) For later
purposes, we change the label of the number of steps from n to t.
Given a state, the probability of giving it should be defined, so we define the
probability as a function of the state:
[Probability that state s i is realized at step t of Markov chain] ≡ P (s i ; t).
(5.50)
Since we are at least in one of the states at each step t, we require the following:
1 =
i
P (s i ; t).
(5.51)
Let P (s j |s i ) be the transition probability from state s i to s j . 18 Let us require
that all probabilities at the step t and the next step t + t satisfy the following
conservation law of probability. Recalling the conservation law of energy and that
of charge in fluid mechanics and electromagnetism in a unit spatial volume, since
the change of s i = the amount flowing out of −s i + the amount coming in s i , the
conservation law should be
P (s i ; t + t) − P (s i ; t)
t
= −
j =i
P (s i ; t)P (s j |s i ) +
j =i
P (s j ; t)P (s i |s j ).
(5.52)
By slightly modifying this, we get the probability of realizing the state s i at the step
t +
P (s i ; t + t) = P (s i ; t) −
j =i
P (s i ; t)P (s j |s i ))t +
j =i
P (s j ; t)P (s i |s j ))t.
(5.53)
The second term on the right-hand side is the probability of exiting the state s i , and
the third is the probability of becoming the state s i .
Next, we introduce a probability vector for the N states,
P(t) =
⎛
⎜
⎜
⎜
⎝
P (s 1 ; t)
P (s 2 ; t)
. . .
P (s N ; t)
⎞
⎟
⎟
⎟
⎠
.
(5.54)
18 This is a conditional probability, but in this context it is called a transition probability.