数学定义

基本概念

设马尔可夫链 ${X_n, n \geq 0}$ 的状态空间为 $S$，如果存在状态 $i \in S$ 满足：

  • $P_{ii} = 1$（一旦进入就永远停留）
  • $P_{ij} = 0$ 对于所有 $j \neq i$（无法转移到其他状态）

则状态 $i$ 称为吸收状态, 其余状态则为瞬时状态。

标准形式

吸收马尔可夫链的转移概率矩阵可以写成如下标准形式：

$$ P = \begin{bmatrix} Q & R \\ 0 & I \end{bmatrix} $$

其中：

  • $Q$: 瞬态之间的转移概率子矩阵 ($t \times t$)
  • $R$: 瞬态到吸收态的转移概率子矩阵 ($t \times r$)
  • $I$: 吸收态之间的转移概率子矩阵 ($r \times r$)，为单位矩阵
  • $0$: 吸收态到瞬态的转移概率子矩阵 ($r \times t$)，为零矩阵

基本性质

$P^1$ 为转移 $1$ 次的转移概率 $P^2$ 为转移 $2$ 次的转移概率 …… $P^\infty$ 为转移 $\infty$ 次的转移概率，可以表示为：

$$ P^\infty = \begin{bmatrix} 0 & (I-Q)^{-1}R \\ 0 & I \end{bmatrix} $$

基本矩阵

$$ N:=\sum_{k=0}^{\infty}Q^{k}=(I_{t}-Q)^{-1} $$

基本矩阵 $N$ 定义为：

$$ N = (I - Q)^{-1} $$

基本矩阵 $N = [n_{ij}]$ 的元素 $n_{ij}$ 表示从瞬态 $i$ 出发，在吸收前访问瞬态 $j$ 的期望次数。

吸收概率

从瞬态 $i$ 出发被吸收态 $j$ 吸收的概率矩阵为： $$B = NR$$

其中 $B = [b_{ij}]$，$b_{ij}$ 表示从瞬态 $i$ 出发最终被吸收态 $j$ 吸收的概率。

Morphing 应用

$P$ 构建规则

  • 对于 handle 点，定义为吸收状态，其余点为瞬时状态
  • 对于 edge 点，只能转移到相邻的 edge 点
  • 其余点可以向拓扑邻接的点进行转移
  • 转移的概率为邻接网格几何权重
  • 所有约束都能够在 $P$ 上被定义，保持 $P$每列的和 $1$, 若不为 $1$, 则需对该列归一化，或在对角线上增加缺少的值。

几何权重的计算需要求解平衡方程，规定多边形内的一点到多边形顶点的权重和为 $1$，权重x长度向量投影到任一方向后的和为 $0$，方程的最小范数解即时对应的几何权重。

行为

  • 状态包含具有哪些 handle 点，哪些是 edge 点，哪些点具备额外的约束，节点间的邻接关系以及每个节点的空间位置
  • 每次在确定移动前的状态前需要先构建出 $P^{\infty}$，并存储矩阵 $B$
  • 每次移动 hanlde 点，可以根据 $B$ 计算出所有自由点的移动矢量