补充一下Markov process的概念，马尔可夫过程是一个无记忆的过程，即未来的状态只与当前状态有关，而与过去的状态无关。假设存在一个随机过程$X_t \in S$, $t \in (0,1)$, 满足：

需要知道的是，ODE和SDE都是Markov process，因为由公式可知，下一个时间点的概率分布可以由当前的概率分布、当前的向量场、当前的的噪声和score函数唯一确定，而与之前的状态无关。对于离散空间的Markov process, 我们称之为Markov chain, 故命名为Continuous-Time Markov Chain (CTMC)。

我们称$p(X_{t+h}|X_t)$为transition probabilities, 由马尔可夫性质知道，一个CTMC过程完全由$X_0 \sim p_0$和transition probabilities唯一确定。因此，后面提到CTMC，我们默认就是transition probabilities了。

此外，这个rate matrix还必须满足如下两个性质：

(1) $\quad $ Outgoing rates are positive: $Q_t(y|x) \geq 0$ $\quad$ for all $x \neq y$.

(2) $\quad $ Rate staying equals negative outgoing rate: $Q_t(x|x) = -\sum_{y \neq x} Q_t(y|x)$ $\quad$ for any x.

这两个性质说明，从x变化到其他状态的rate必然是非负的，如果不可能switch到某个状态，那么Q就是0；同时，对于x状态，它自己的rate必然和其他状态switch到x的rate之和抵消。故对角线上的元素是非正的，非对角线元素是非负的。

证明如下：

对于第一条，当h=0时，显然$X_t$来不及变化，所以如果$y \neq x$, 那么此时概率为0，而当h>0时，概率必然是非负的，所以说明在0处导数非负。

对于第二条，推导如下：

其中$R_t(h)$是高阶误差项，当h很小时可以忽略。

于是，我们对S中所有的y进行上式计算得到$p_{t+h|t}(\cdot | x)$, $X_{t+h}$将按照不同x的概率进行采样。

A factorized CTMC model is given by a CTMC model $Q_\theta^t$ such that for all $y = (y_1, \ldots, y_d), x = (x_1, \ldots, x_d) \in S = V^d$ $\qquad$ it holds :

于是，我们可以把那些和x最多有一个token不同的y叫做Neighbors N(x) of x,故上面的公式可以改写成：

其中，$Q^\theta_t(v_i, j \mid x)$表示对于x的第j个token，我们把它变成vacabulary中的第i个token的rate, 得到$y = (x_1, \cdots, x_{j-1}, v_i, x_{j+1}, \cdots, x_d)$. 虽然是用神经网络预测的Q，但是我们仍然需要满足： (1) $\qquad$ $Q^\theta_t(v_i, j \mid x) \geq 0$ $\quad$ if $v_i \neq x_j$

(2) $\qquad$ $Q^\theta_t(x_j, j \mid x) = -\sum_{v \neq x_j} Q^\theta_t(v, j \mid x)$ $\quad$

很容易发现，使用factorized 后的next state的维度是$d \times V$, 和d，V都是成正比的，远远优于之前的$V^d$!!

note中提到 This approximation agrees with the full CTMC Euler step up to first order in h, but allows for a O(h2) probability of simultaneous updates to multiple tokens. 也就是说，上面的伪代码确实违反了neighbor原则，但是误差是二阶的，可以接受。 为什么是二阶的呢？

对于一个token来说，如果更新的$v \neq x$, 它的概率是$h q_j(v)$. 当有两个token同时发生变化时，概率就是$h^2 q_j(v) q_{i}(v_1)$, 其中q就是Q，默认是一个常数，所以这个概率就是$O(h^2)$的。在一阶精度可以接受，其实就是说误差都是二阶及以上。

Note中定义：Factorized mixture path (independent noising per token)

Let $S = V^d$ and let $p_{\text{init}}(x) = \prod_{j=1}^d p_{\text{init}}^{(j)}(x_j)$ be a factorized initial distribution. Fix a scheduler $0 \le \kappa_t \le 1$ such that $\kappa_0 = 0$, $\kappa_1 = 1$ with $\frac{d}{dt} \kappa_t \ge 0$. Define the conditional path by

这个公式是将x的d个token完全独立进行变化的结果，与我们前面提到的discrete diffusion model中每一个token的生成不遵循顺序，而是同时进行的思想是一致的。不过这里命名为Factorized mixture path, 这里的factorized应该是指每个token的变化都是独立的，和之前factorized CTMC model中每次最多改变一个token的factorized含义是不同的。

它和我们之前提到的Gaussian path的区别在于，Gaussian path是以一个概率分布为主体，从init状态，不断变形移动，最终变成data distribution; 而Factorized mixture path是有很多不同的state点z，我们从一个init点出发，每一步都根据概率选择跳转到哪个z上去，最终希望能跳到data distribution上去。总而言之，前者是一个分布连续变形过程，后者是一个离散随机跳转过程。 ps: 如果你能意识到这个点，那么说明你对整个课程的理解很不错哈🥰

Theorem 36 (Discrete marginalization trick). The marginal rate matrix defined by

where

is a valid rate matrix and fulfills the following condition:

Kolmogorov Forward Equation (KFE).

Let $p_t$ be a set of distributions on $S$ for every $0 \le t \le 1$. Further, let $X_t$ be a CTMC with matrix $Q_t$ and initial distribution $p_0$. Then $X_t \sim p_t$ for all $0 \le t \le 1$ if and only if the Kolmogorov Forward Equation (KFE) holds:

于是，我们只要证明先前定义的marginal rate matrix满足KFE就可以了。

有：

上面的证明用到了$\frac{d}{dt} p_t(x \mid z) = \sum_{y \in S} Q_t^z(x \mid y) , p_t(y \mid z)$, 由于一个conditional path($target=z$)必然也满足KFE，对比KFE的定义可知这个就是它的conditional版本，所以这个等式是成立的。这个证明过程基本和flow matching中的一样。

不过，还有一个问题，就是为什么满足KFE就说明这个CTMC过程的分布是$p_t$呢(或者说二者等价)，在flow matching中，我们似乎没有严谨证明这个事，只是直观理解。下面我们来证明一下：

首先证明KFE是必要条件： To show that the KFE is necessary, assume that $p_t(x)$ are the true marginals of the CTMC, i.e. $X_t \sim p_t$ for every $0 \le t \le 1$. Then we can compute:

where in (i) we simply use a time offset, in (ii) we use the definition of the transition probabilities, in (iii) we swap the sum and derivative, and in (iv) we use the definition of the rate matrix.

接下来证明KFE是充分条件： To show that the KFE is sufficient, we can rewrite the KFE in matrix form:

Note that the above is a linear ODE over vector space $R^S$. Its initial condition is fixed by $p_0$ as stated in the theorem.

$p_t$就是所有S中可能点x的概率分布（可以看成一个vector），而Q就是S中所有y到x的rate matrix的大矩阵，对于t时刻，右边直接就算出来了，所以这个ODE其实就是一个一阶线性微分方程，在初始$p_0$给定的条件下，这个ODE解出来的$p_t$必然是唯一的。

需要注意的是，之前定义中的等价的两个事件是：如果$p_t$是某个CTMC的边际分布$<=>$ $p_t$满足KFE。当前我们只证明了如果$p_t$满足KFE，那么这个$p_t$一定是唯一的，似乎没有说明它是某个CTMC的边际分布啊？产生这个疑惑的原因是，由于公式中掺杂了Q，导致我们无法直接看到一个CTMC的过程, 下面是我的一个理解：

如果$p_t$是一个CTMC过程的分布，则：

求导得到：

而$\frac{d}{dh} p_{t+h}(x) \big|_{h=0} = \frac{d}{dt} p_t(x)$, 替换得到：

而这个式子我们已经有了，再积分回去即能看出$p_t$是满足CTMC的定义了。

然而note的证明更绝： 设 $q_t$ 为 CTMC 的真正边际分布。
由必要性（之前证明过的部分），我们知道 $q_t$ 一定满足 KFE：

我们又构造了一个 $p_t$，并且它也满足：

由 ODE 解的唯一性（给定 $p_0$ 相同），所以：

因此 $p_t$ 就是那个 CTMC 的边际分布。 太美妙了，我的证明是🐷，之所以会捣鼓出这个🐷证明是因为我一开始没看到note中那个绝妙的证明😭

Example 37 (Conditional rate matrix for factorized mixture path). Set $\frac{d}{dt}\kappa_t = \dot{\kappa}_t$. The factorized mixture path has a factorized conditional rate matrix given by

上面这个公式就非常美妙，我们最终的目标是每一个$x_i$能变成$z_i$, 所以可以看到只有当$v_i = z_i \text{ and }x_j \neq z_j$时，rate是1；其他情况下，rate要么是0，要么是-1.

如何证明这个公式就是factorized mixture path的conditional rate matrix呢？根据前面的结论，我们需要证明它满足KFE等式，由于factorized mixture path每一个token都是独立的，所以我们不妨就考虑一个token的情况：

(i) uses the definition of the factorized mixture path for $d=1$

(ii) is obtained by taking derivatives and setting $\frac{d}{dt}\kappa_t = \dot{\kappa}_t$

(iii) follows by simple algebra

(iv) by the definition of the factorized mixture path

(v) by simple algebra

(vi) follows from the fact that $\sum_{y \in S} p_t(y \mid z) = 1$

(vii) by the definition of the rate matrix, and (viii) by simple algebra.

其中需要关注的步骤是(vii)，这一步我们用到了先前对factorized mixture conditional rate matrix的定义，对于第一项$y \neq x$，$Q_t^z(x \mid y)$, 只有当$x=z$时跳转，rate=1；当$x\neq z$时，不跳转，rate=0. 对于第二项$y = x$, $Q_t^z(x \mid x)$, 当$x=z$时，不跳转，rate=0；当$x \neq z$时，rate=-1. 每一种结果都和$\delta_z(x)$，$\delta_z(x) - 1$是一致的，所以(vii)是ok的。 于是，我们证明了这个定义下的conditional rate matrix满足KFE等式，所以它就是该factorized mixture path的conditional rate matrix了。

Theorem 38 (Marginalization trick for factorized mixture path). The marginal rate matrix of the factorized mixture path is factorized and has the form

where $p_{1|t}(z_j = v_i \mid x)$ is the conditional probability of the $j$-th position ($j$-th token in the sequence) being equal to $v_i$ given the full noisy sequence $x$. 它表示在时刻t，给定当前状态x，token位置j变成v_i的rate。

如何证明这个结论呢？

Example 39 (Masked Diffusion Language Model). A specific case of the above method is masked diffusion language models (MDLMs). The idea of MDLMs is that we can extend the vocabulary of tokens $V = {v_1, \ldots, v_V}$ with a new token $[\text{mask}]$ that indicates that this token is missing (or was masked). Specifically, we set $V = {v_1, \ldots, v_V, [\text{mask}]}$ and the initial point is simply $[\text{mask}]^d$, i.e. the sequence that is all-masked. Formally, this means setting $p_{\text{init}} = \delta_{[\text{mask}]^d}$ in the above framework. The sampling procedure is illustrated in Figure 20.

就是说在初始阶段，我们直接把所有token填充成mask，这样就不会包含任何随机信息了，训练会更简单。