5.2 Various Sampling Methods
95
Then, from convergence and k 1, we expect that P
(k)
eq,app is sufficiently close to
P eq . 20 In other words, the state obtained at this point is considered as a sampling
from the equilibrium states. In practice, it is difficult to judge, but if one calculates
the expectation value at each step and observes that it starts to fluctuate around a
certain central value, it is considered that the equilibrium has been reached after
that.
A state that is updated only once from a state that seems to have reached
equilibrium is almost the same as the original state, so cannot be considered as an
independent sample. Therefore, we keep updating and suppose we reach k k. 21
The state at that time can be regarded as an independent sample from the previous
sample. We repeat this procedure.
Taking an average over the resulting set of the states means that, due to the law
of large numbers, we can calculate the average for states of high probabilities in the
equilibrium distribution. In other words, we can do the following:
i
P eq (s i )O(s i ) ≈
1
N smp
MC
k
O(s k ) .
(5.67)
Here, k represents the steps of a long separated Markov chain (MC) as described
above. And N smp indicates how many states were used. Including the error of the
deviation from the equilibrium distribution, we have
i
P eq (s i )O(s i ) =
1
N MC
MC
k
O(s k ) + O
1
√
N MC
(5.68)
It is essentially important that this error does not depend on the range of i on the
left-hand side. Namely, no matter how large the dimensionality of state space is, if
the states can be updated using Markov chains and many states can be obtained,
the expectation value can be precisely evaluated. This method, used to randomly
assemble the states that are likely to be realized with high probability using Markov
chains, is called the Markov chain Monte Carlo (MCMC) method.
Finally, we make a comment on the origin of the condition k 1. As we have
seen, the convergence destination is unique due to the Perron-Frobenius theorem for
the transition matrix T. And the convergence destination is the eigenvector itself for
the maximum eigenvalue 1. The other way of saying it is that the eigenvector can
be obtained from an appropriate initial vector by multiple matrix products, 22 and its
convergence is determined by the second largest eigenvalue of T. 23
20 The first k which satisfies P eq ≈ T k P 0 is called burn-in time or thermalization time.
21 The autocorrelation time is a measure to give a suitable |k − k|. See [67, 68] for details.
22 This is so-called power method.
23 Detailed discussions are found in [69].
95
Then, from convergence and k 1, we expect that P
(k)
eq,app is sufficiently close to
P eq . 20 In other words, the state obtained at this point is considered as a sampling
from the equilibrium states. In practice, it is difficult to judge, but if one calculates
the expectation value at each step and observes that it starts to fluctuate around a
certain central value, it is considered that the equilibrium has been reached after
that.
A state that is updated only once from a state that seems to have reached
equilibrium is almost the same as the original state, so cannot be considered as an
independent sample. Therefore, we keep updating and suppose we reach k k. 21
The state at that time can be regarded as an independent sample from the previous
sample. We repeat this procedure.
Taking an average over the resulting set of the states means that, due to the law
of large numbers, we can calculate the average for states of high probabilities in the
equilibrium distribution. In other words, we can do the following:
i
P eq (s i )O(s i ) ≈
1
N smp
MC
k
O(s k ) .
(5.67)
Here, k represents the steps of a long separated Markov chain (MC) as described
above. And N smp indicates how many states were used. Including the error of the
deviation from the equilibrium distribution, we have
i
P eq (s i )O(s i ) =
1
N MC
MC
k
O(s k ) + O
1
√
N MC
(5.68)
It is essentially important that this error does not depend on the range of i on the
left-hand side. Namely, no matter how large the dimensionality of state space is, if
the states can be updated using Markov chains and many states can be obtained,
the expectation value can be precisely evaluated. This method, used to randomly
assemble the states that are likely to be realized with high probability using Markov
chains, is called the Markov chain Monte Carlo (MCMC) method.
Finally, we make a comment on the origin of the condition k 1. As we have
seen, the convergence destination is unique due to the Perron-Frobenius theorem for
the transition matrix T. And the convergence destination is the eigenvector itself for
the maximum eigenvalue 1. The other way of saying it is that the eigenvector can
be obtained from an appropriate initial vector by multiple matrix products, 22 and its
convergence is determined by the second largest eigenvalue of T. 23
20 The first k which satisfies P eq ≈ T k P 0 is called burn-in time or thermalization time.
21 The autocorrelation time is a measure to give a suitable |k − k|. See [67, 68] for details.
22 This is so-called power method.
23 Detailed discussions are found in [69].