88
5 Sampling
Weakness of the rejection sampling
Equation (5.31) is required for rejection sampling to work. Also, even if (5.31)
is satisfied, if the value of M is very large, the possibility of rejection increases,
and sampling cannot be performed. Furthermore, in the rejection sampling, the
calculated x candidate may be simply discarded, so if it takes time for one sampling
from Q(x), it is not very efficient to collect samples. In order for the rejection
sampling to be practical, we need to find a good Q(x) for the desired P (x).
For example, consider x = s i as a spin configuration, and let P (x) = P (s i ) be
the Ising model 10 in statistical mechanics. The Ising model is a classical model of
a magnet, in which each point labeled i on the lattice has a variable (spin) that can
take the value of 1 or −1. In the case of a two-dimensional Ising model whose lattice
size is L x × L y , the label i runs from 1 to 2 L x L y . Specifically, for example, even
with L x = L y = 10, we have 2 10×10 ≈ 1.27 × 10 30 , and so we have to consider
the probability distribution in a huge region. Also, the higher the dimensions, the
more the label i can run, in the exponential form. 11 This phenomenon is called the
curse of dimensionality. In such a case, it is very difficult to come up with a good
proposal distribution Q(s i ).
5.2.3 Markov Chain
A useful sampling technique even in such cases is to use Markov chains. In this
subsection, we will explain the basics of Markov chain using concrete examples
[65]. In particular, we will introduce the Markov chain with two examples, the
Gothenburg weather model and the Los Angeles weather model. These examples
here do not have the curse of dimensionality as described above, but do not lose the
essence of the argument.
Markov chain
From now on, we will introduce the Markov chain through concrete examples. In
particular, let us focus on the day’s weather at a certain location, and for simplicity,
assume that the weather is only rainy or sunny. The weather here is what is called a
“state.” According to the literature, we take s 1 = rainy, s 2 = sunny. In addition, let
us introduce a vector P that represents the probability distribution for the two states.
If the probability of rainy weather is P rainy and the probability of sunny weather is
P sunny , we align them as
P =
P rainy
P sunny
.
(5.36)
10 Readers unfamiliar with the Ising model should refer to the column.
11 If L is the length of one side of the d-dimensional square lattice, the range of i is 2 L d . For
example, if one side of the 3-dimensional cube has 10 lattice points, the range of i is 2 10 3 ≈
1.07 × 10 301 .
5 Sampling
Weakness of the rejection sampling
Equation (5.31) is required for rejection sampling to work. Also, even if (5.31)
is satisfied, if the value of M is very large, the possibility of rejection increases,
and sampling cannot be performed. Furthermore, in the rejection sampling, the
calculated x candidate may be simply discarded, so if it takes time for one sampling
from Q(x), it is not very efficient to collect samples. In order for the rejection
sampling to be practical, we need to find a good Q(x) for the desired P (x).
For example, consider x = s i as a spin configuration, and let P (x) = P (s i ) be
the Ising model 10 in statistical mechanics. The Ising model is a classical model of
a magnet, in which each point labeled i on the lattice has a variable (spin) that can
take the value of 1 or −1. In the case of a two-dimensional Ising model whose lattice
size is L x × L y , the label i runs from 1 to 2 L x L y . Specifically, for example, even
with L x = L y = 10, we have 2 10×10 ≈ 1.27 × 10 30 , and so we have to consider
the probability distribution in a huge region. Also, the higher the dimensions, the
more the label i can run, in the exponential form. 11 This phenomenon is called the
curse of dimensionality. In such a case, it is very difficult to come up with a good
proposal distribution Q(s i ).
5.2.3 Markov Chain
A useful sampling technique even in such cases is to use Markov chains. In this
subsection, we will explain the basics of Markov chain using concrete examples
[65]. In particular, we will introduce the Markov chain with two examples, the
Gothenburg weather model and the Los Angeles weather model. These examples
here do not have the curse of dimensionality as described above, but do not lose the
essence of the argument.
Markov chain
From now on, we will introduce the Markov chain through concrete examples. In
particular, let us focus on the day’s weather at a certain location, and for simplicity,
assume that the weather is only rainy or sunny. The weather here is what is called a
“state.” According to the literature, we take s 1 = rainy, s 2 = sunny. In addition, let
us introduce a vector P that represents the probability distribution for the two states.
If the probability of rainy weather is P rainy and the probability of sunny weather is
P sunny , we align them as
P =
P rainy
P sunny
.
(5.36)
10 Readers unfamiliar with the Ising model should refer to the column.
11 If L is the length of one side of the d-dimensional square lattice, the range of i is 2 L d . For
example, if one side of the 3-dimensional cube has 10 lattice points, the range of i is 2 10 3 ≈
1.07 × 10 301 .