马氏链

Markov 链
}0:{≥n n ξ称为有限状态Markov 链,若n ξ只有有限个取值且 =====--+),,,|(0011i i i j P n n n k n ξξξξ )|(i j P n k n ==+ξξ. 将其记为 ),(k n n p ij +.
转移概率矩阵
记 )),((),(k n n p k n n P ij +=+,
P ),(k n n +就称为从n 出发的k 步转移矩阵.
显然
P =),(n n I , P ),(m n 1T =1T , 而且
P =),(l n P ),(m n P ),(l m (C-K 方程)
时齐性: P =+),(m n n P m
记成 )(m P , ()()
()(m ij m p =P
设初始分布为)(0)
0(i P i ==ξμ，转移为P=)(ij p ，则
n
n i i i i i i i n n p p p i i i P 121100)
0(1100),,,(-==== μξξξ
绝对概率
设)()(i P n n i ==ξμ，行向量)(n μ=):()
(S i n i ∈μ，
则 )(n m +μ=)(m μ)(n P .
例
1.DNA序列中的删除、插入、错读、及正确阅读
由于DNA序列中每次错误的发生是独立的，而且可以
近似地认为某一个bp是删除（插入）的可能只依赖其
前一个bp 是否是删除（插入），所以它近似地可以看
作一个Markov链。

这个数学模型在multiple alignment
(MA) 时,是一个很好的模型。

2.在基因(编码CDNA)序列中, 正确的阅读框下,三联子
码(codon)序列就可看作一个Markov链.这是因为氨基
酸之间具有不同的结合能,因此有不同的稳定性.在长
期的自然选择下,较稳定的连接对应的三联子码(codon)连接,就会比不稳定的三联子码(codon)连接以更大的可
能出现. 所以将三联子码(codon)序列看作Markov链比
通常采用的独立模型更为合理.
3. 一个平稳随机序列(其有限个随机变量的联合分布平移不变: 例如
(X(1),X(2),X(3)) 和(X(1+n),X(2+n ),X(3+n)) 具有
相同的联合分布), 通常可以近似地认为X(n)的分布
只依赖于它前面足够多的有限个(例如s个), 这时,
{(X(n),X(n+1),X(n+2),…,X(n+s-1) )|n=0,1,2,… }
就是一个Markov链.
Poisson 过程
Poisson 过程是一个连续时间的,取整数值的独立增量过程, 所以它有Markov 性. 它是时间连续的Markov 链。

Poisson 过程的转移矩阵依赖于连续时间参数t . 此时有
⎪⎩⎪⎨⎧≥-==--)
(0)()!()()(),()(其它情形i j i j t e t p p t P i
j t ij ij λλ. 即转移矩阵是一个上三角形无穷矩阵. 这时转移速率阵（))0('(ij p ）为
Q =)(ij q =⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--- 0000
λλλλλλ. 注意, 这里Q 的每一行的和都是0.
在基因组测序过程中,shotgun 方法得到片断的点断序列近似地就可作为Poisson 过程来处理.对于要使测得的序列拼接后能够覆盖90%(99%),需要多少版本; 给定版本数的序列,经过拼接,可以指望得到的岛长,…都需要用Poisson 过程 来计算.
复合Poisson 过程的转移矩阵与转移速率阵
设t N 为强度λ的Poisson 过程， }{k Y 为与之独立的独立同分布随机序列， 则
t N t Y Y ++=∆ 1ξ
为复合Poisson 过程。

因为它也是是独立增量过程, 所以它有Markov 性. 假定
)1(,21~21∑=⎪⎪⎭⎫ ⎝⎛j
j j k f f f f j Y 。

那么t ξ是时间连续的Markov 链。

我们来求它的转移转矩阵
与转移速率阵。

对于 t s <
)(,0),(k i t s p ik >=，)()0(),(s t t ii e N N P t s p --==-=λ，
)|(),(i j P t s p s t ij ===ξξ
)|(11i Y Y i j Y Y P t t s N N N =++-=++=+ （独立增量性）
)(1i j Y Y P t s N N -=++=+ （同分布性）
)(1i j Y Y P s t N N -=++=- （全概公式）
)()|(11
k N N P k N N i j Y Y P s t s t k k =-=--=++=∑≥ （独立性） )()(11
k N N P i j Y Y P s t k k =--=++=∑≥ 。

归纳地记概率向量f ),,,(1 i f f =的k 次卷积(它们代表k 个独立同分布的随机变量的和的分布)为
∑=--==l
j k k l j l f j f l f f l f 111**1)()()(,)(。

那么，
∑≥---⋅-=1)(*!))(()(),(k k s t k ij k s t e i j f
t s p λλ。

这说明转移矩阵是时齐的， 而且是上三角形无穷矩阵。

其转移速率阵为
Q =)(ij q =⎪⎪
⎪
⎪
⎪⎪⎪
⎪
⎪
⎭
⎫
⎝⎛--- 21212100f f f f f f λλλλλλλλλ。

(6. 13) 由此可见复合Poisson 过程也是保守的。