马尔科夫链蒙特卡罗 MCMC
1. accept-reject sampling
The samples we are getting from this accept-reject method are uncorrelated with each other.
3. MCMC(Markov Chain Monte Carlo)
.1 Markov Chain
马尔科夫链:一种随机过程,具有无记忆性,即未来状态只与当前状态有关,与过去状态无关。
马尔科夫链的状态:马尔科夫链的状态是指系统处于的具体状态。
马尔科夫链的状态空间:马尔科夫链的状态空间是所有可能状态的集合。
马尔科夫链的轨迹:从初始状态开始,经过一系列状态转移后所形成的状态序列,称为马尔科夫链的轨迹。
Once the Markov Chain reaches the stationary distribution, it remains there, and subsequent samples drawn from the chain can be considered as samples from the target distribution. This property is known as the ergodicity of the Markov Chain.
.2 Monte Carlo
.3 MCMC
MCMC works by designing some kind of Markov Chain whose steady state is the distribution we want to sample from. If the Markov Chain gets to that distribution, it's going to stays there, so that from that point forward, we are sampling from the target distribution.
MCMC 通过构建一个马尔可夫链来模拟从目标分布中抽样。
MCMC 的主要思想是:设计一个马尔可夫链,其稳态分布与目标分布一致。一旦马尔可夫链达到稳态,它将在该分布中停留,即该点之后的样本都服从目标分布。
MCMC 通过迭代生成一系列样本,每次迭代时,从当前状态转移到新的状态,然后计算接受该新状态的概率,根据一定的准则决定是否接受新状态,如果接受新状态,则转移到新状态;如果拒绝新状态,则保持当前状态。
MCMC is a general idea and the way people go about designing Markov Chain differs from method to method.
MCMC 的核心在于马尔科夫链的构建。常见的 MCMC 算法有 Metropolis-Hastings 和 Gibbs 采样算法。这些算法通过定义合适的转移概率,使得马尔科夫链在长时间运行后收敛到目标分布。
Detailed-Balance Condition
对于一个具有有限状态集 S 的马尔科夫链,假设其转移概率矩阵为 P,并且存在一个稳态分布 π,细致平衡条件 Detailed-Balance Condition 表示:对任意 x 和 y,π(x) P(y|x) = π(y) P(x|y) ,其中 π(x) 和 π(y) 分别表示状态 x 和 y 在稳态下的概率。
这个条件说明,在平稳状态下,流入某个状态的概率等于流出该状态的概率。换句话说,从状态 x 到状态 y 的平均流量与从状态 y 回到状态 x 的平均流量相等,这种平衡使得整个系统处于一种动态平衡状态。如果将条件等式左右两边对 x 求和,并表示为矩阵形式,则有:πP = π。
Metropolis-Hasting
Gibbs Sampling