Markov Chain Mento Carlo (MCMC) 2
马尔科夫链蒙特卡罗方法（Markov Chain Monte Carlo，以下简称MCMC），是用于得到服从某一特定分布的随机采样的方法。很多复杂算法求解的基础，都使用到了 MCMC 算法。
随机数产生方法
服从某一特定分布的随机变量的抽样值称为随机数，我们通常采用数学方法来产生随机数。
这种方法是利用一定的数学递推公式来产生随机数，即在给定一个任意的初值后，就可由此递推公式产生任意多的随机数，这种方法非常容易在计算机上实现。这种方法最大的缺陷在于给定初值后，以后所有的随机数便被唯一地确定下来了，而且这些随机数还存在周期现象，即随机序列达到一定长度后会出现重复，因此严格来说这些随机数并不是真正的随机数，故一般称之为伪随机数 (pseudo random number)。但由于初值可随机确定，因此其后的一系列数也可看作是随机的。
0-1均匀分布随机数的产生
[0,1]均匀随机数是在[0,1]区间上均匀分布随机变量的抽样值，其是产生其他一切分布随机数的基础。也就是说，任何其他分布的随机数都可通过对[0,1]均匀随机数进行某种转换得到。
目前产生[0,1]均匀随机数的最广泛的方法是线性同余法，也称为线性同余发生器 (linear congruential generator) 。
线性同余法
Lehmer (1951) 提出这种方法，它利用数论中的同余运算原理产生随机数，其递推公式为
$$ x_i = (a x_{i-1} + c) (\text{MOD} m) \\ r_i = \frac{x_i}{m}, i=1,2, \cdots $$
其中 是事先给定的参数，均为非负整数； 是在 [0,m] 区间取值的一个随机整数； 是在 [0,1] 区间取值的一个随机实数。
在给定一个任意非负整数的初值 后，由上式求出整数序列 和实数序列 。
若 ，则称为乘同余法；若 ，则称为混同余法。