I am studying simulated annealing, and simulated annealing involves a Boltzmann distribution.
Typically I see the Boltzmann distribution written like:
$P(E_i) = e^{-E_i/(kT)}/Z$
where $Z$ is the sum of all of the energy in all of the states, and $P(E_i)$ is the energy in just one of the states.
The thing is in simulated annealing I see the pdf written with an integral:
$P(x) = \frac{e^{-f(x)/T}}{\int_{S}e^{-f(z)/T}dz}$
I understand from many sources that the Boltzmann distribution is reportedly very difficult to sample from because it involves this $f(z)$ as you can see above. I have two questions about that:
1) Why does the $f(z)$ not appear in the first equation I gave for the Boltzmann distribution? (e.g., it does not appear here on wikipedia: https://en.wikipedia.org/wiki/Maxwell–Boltzmann_distribution)
2) I'm able to fire up python and use scipy to easily sample from a Boltzmann distribution just by doing
import scipy
from scipy import stats
import numpy as np
import matplotlib.pyplot as plt
r = scipy.stats.boltzmann.rvs(lambda_=1.4, N=4, size=10)
without trouble. (source: https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.stats.boltzmann.html#id23)
So what is the big deal with sampling from a Boltzmann distribution? There are all these fancy methods in Simulated Annealing like Hit and Run, Metropolis sampling, etc.
Why are they necessary when I was able to sample from a Boltzmann distribution with ease?
Best Answer
In the first equation, $f(z)$ is represented by $E_i $. This term is used to represent the energy repartition. It is just a continuous version of the Boltzmann disitribution (and not Maxwell-Boltzmann, which is a different law).
In addition, the main problem is the computation of $Z$.
In most pratical problems requiring such distribution, the number of states is enormous, and each of them has his proper energy.
Imagine you want to find the shortest way to travel through $N$ cities, you have to pass only once by city and finish by the one you started from. Then, you have $0.5(N-1)!$ possibilities. For $N=20$ only, you already have about $6\times10^{16}$ different states to consider.
This is why we need algorithms such as Metropolis, to avoid having to compute $Z$.