EECS应用概率论——1.2　马尔可夫链

想象一下你正在浏览网页：假设你在网页i上浏览了一个单位时间，然后随机点击进入了网页i指向的一个网页．在这个过程中，从网页i到网页j的概率正好为P(i, j)，与前面的例子相同． 1.2.1　定义 考虑一个包含节点X = {1, 2, …, N}和有向边的有限图．假设其中有些节点具有指向自己的边．图中每条边(i, j)，都有一个权重P(i, j) > 0．这些权值使得每个点外向边的权和为1．根据习惯，如果图中没有从i到j的边，则P(i, j)为0． 以上述方式得到的矩阵P = P[(i, j)]叫作随机矩阵．这种矩阵的每个元素均为非负，并且每行的和为1．现在，我们定义以下过程{X(n), n≥0}：在时刻0的时候用X(0)表示系统所处的状态；随后的每一个时刻n，系统由状态X(n1) = i跳到状态X(n) = j的概率为P(i, j)，即系统所处在的状态仅由X(n1)与P决定．这样定义的过程{X(n), n≥0}被称为马尔可夫链．该有限图则被称为马尔可夫链的状态转移图． 图1-4　安德雷•马尔可夫（1856—1922） 图1-5展示了3个马尔可夫链的状态转移图． 图1-5　3个具有不同转移概率的3状态马尔可夫链（状态为｛1, 2, 3｝） 上面的描述可以用以下公式来表述： （1.3） 从状态i移动到状态j的概率与先前状态无关．这种“健忘”的性质叫作马尔可夫性质．这也正是X(n)被称为“状态”的原因：它包含了所有预测该过程未来状态所需要的相关信息． 1.2.2　n步后的分布和稳态分布 假如马尔可夫链在第n步（n≥0）处于状态j的概率为πn(j)，则它在第n+1步处于状态i的概率πn+1(i)可由下面的公式得到 . （1.4） 事实上，马尔可夫链在第n+1步处于状态i的事件可以表示为马尔可夫链在第n步处于状态j，但在第n+1步时处于i事件的集合．由于这些事件为互斥事件（即每次只能处在一个状态j），联合事件发生的概率正好为各个时间的概率之和，且马尔可夫链在第n步处于状态j而第n+1步处于状态i的概率是πn (j)P(j, i)． 在矩阵记法下， , 所以， . （1.5） 这里我们注意到，对于n≥0和i∈X的所有情况，当且仅当π0满足式（1.1）的平衡方程时有πn(i) = π0(i)．在这种情况下，称π0为稳态分布．因此，稳态分布就是式（1.1）的非负解π，并满足分量之和为1．