二叉树指标随机场关于分枝马氏链的一类强偏差定理

闵 帆,杨卫国

(江苏大学理学院,江苏镇江212013)

1 引言

本文主要研究二叉树TC,2(二叉树TC,2的根点o 与2 个支点相连, 其他的支点与3 个支点相连(见图1)). 为了方便, 将TC,2简记为T2. 对于T2上的任一顶点t, 记|t| 表示根点o 和顶点t 之间的距离. 若|t|=n, 则称t 位于树的第n 层. Ln表示T2的第n 层上所有顶点的集合, T(n)表示二叉树T2从0 层(根) 到n 层的所有顶点的子图. |T(n)| 记为子图T(n)所含顶点数. 对于二叉树上任一顶点t, 记t1和t2为t 的两个子代.

设(Ω,F) 为一可测空间, {Xt,t ∈T2} 是定义在(Ω,F) 上且取值于G={0,1,··· ,b −1}(b 是正整数) 的随机变量集合, 设B 为T2的子图, 记XB= {Xt,t ∈B}, xB表示XB的实现. 设P 是可测空间(Ω,F) 上的概率测度, 我们称P 为树T2上的随机场. 令{Xt,t ∈T2}在P 下的分布为P(XT(n)=xT(n))=P(xT(n)).

定义1.1[二叉树指标分枝马氏链][1]设T2为二叉树, {Xt,t ∈T2} 是定义在概率空间(Ω,F,Q) 上在G = {0,1,··· ,b −1} (b 是正整数) 中取值的随机变量集合, 设p ={p(x),x ∈G} 是G 上一概率分布, P = (P(y1,y2|x)) 是定义在G×G2上的一随机矩阵(满足P(y1,y2|x)≥0,∀x,y1,y2∈G 及如果对n ≥1, 有

图1:二叉树TC,2

及

则称{Xt,t ∈T2} 为具有初始分布p 与随机矩阵P 并在G 中取值的二叉树指标分枝马氏链.

注1.2[1]若{Xt,t ∈T2} 在概率测度Q 下为二叉树指标齐次分枝马氏链, 则

为避免技术问题, 总假定p(x) 和P(y1,y2|x) 是正的.

定义1.3[2]设T2为二叉树, {Xt,t ∈T2} 是定义在可测空间(Ω,F) 上取值于G 的随机变量族, ∀x,y1,y2∈G, 设p(x)>0 且P =(P(y1,y2|x)) 为正的随机矩阵, 设Q,P 为(Ω,F)上的两个概率测度, 其中{Xt,t ∈T2} 在概率测度Q 下为具有初始分布p 与随机矩阵P 的二叉树指标分枝马氏链. 设P(xT(n))>0, 令

则称h(P|Q) 为P 关于Q 的样本相对熵率或渐近对数似然比.

类似于参考文献[2] 中引理1 的证明可知

故h(P|Q) 可作为T2上的任意随机场与分枝马氏链之间偏差的一种度量.

树指标随机过程是近年来发展起来的概率论的一个新的研究方向. 文献[1] 研究了二叉树上分枝马氏链的等价性质; 文献[3] 研究了二叉树有限状态分枝马氏链的强大数定律和Shannon-McMillan 定理; 文献[4] 研究了二叉树上有限状态分枝马氏链的强大数定理; 文献[5] 研究了二叉树非齐次分枝马氏链的等价定义、强大数定理和熵遍历定理; 文献[6] 研究了关于齐次树上随机场的一类强偏差定理; 文献[2] 研究了关于Cayley 树上任意随机场和马氏链场的强偏差定理; 文献[7] 研究了齐次树指标齐次马氏链随机场的一类强偏差定理; 文献[8] 研究了Bethe 树指标随机场关于非齐次马氏链的一类强偏差定理.

本文通过引入渐近对数似然比作为二叉树指标任意随机场与分枝马氏链之间偏差的一种度量, 进而构造鞅的方法, 得出了二叉树指标随机场关于分枝马氏链的一类强偏差定理, 作为推论得到了二叉树指标分枝马氏链的强大数定理和渐近均分性.

2 强偏差定理

强偏差定理是由不等式表示的一类强极限定理, 是由等式表示的一类强极限定理的推广.本节将建立二叉树指标任意随机场关于分枝马氏链的一类强偏差定理.

引理2.1设T2为二叉树, {Xt,t ∈T2} 是定义在可测空间(Ω,F) 上的随机变量族. P与Q 是(Ω,F) 上的两个概率测度, 其中{Xt,t ∈T2} 在Q 下是具有严格正的随机矩阵P =(P(y1,y2|x)) 的二叉树指标分枝马氏链. P(XT(n))>0, 设{gt(x,y1,y2),t ∈T2} 是定义在G3上的函数族, L0={0}, Fn=σ(XT(n)), n ≥1, 令

其中λ 为实数, EQ表示在Q 下的数学期望, 则{tn(λ,ω),Fn,n ≥1} 为在概率测度P 下的非负鞅.

证由式(1.1), (2.1) 可知

令

则

由式(2.2), (2.4) 可知

又易知EP[t1(λ,ω)]=1, 因此

故{tn(λ,ω),Fn,n ≥1} 为在概率测度P 下的非负鞅.

引理2.2设T2为二叉树, {Xt,t ∈T2} 为二叉树指标分枝马氏链, 设{gt(x,y1,y2),t ∈T2} 是定义在G3上的函数族, {an,n ≥1} 为正随机变量序列. 设α>0,

则

定理2.3设T2为二叉树, {Xt,t ∈T2} 为定义在可测空间(Ω,F) 上且取值于G ={0,1,··· ,b −1}(b 是正整数) 的随机变量族, P 与Q 是定义在F 上的两个概率测度, 并且{Xt,t ∈T2} 是在概率测度Q 下的二叉树指标分枝马氏链, 也即式(1.2) 成立. 令h(P|Q) 如(1.3) 式定义, 且{gt(x,y1,y2),t ∈T2} 是定义在G3上的函数族. 设c ≥0 是一个常数, 令

假设存在α>0, ∀i ∈G, 有

令

特别地, 有

证令tn(λ,ω) 如(2.1) 式定义. 由引理2.1 知, {tn(λ,ω),Fn,n ≥1} 是非负P - 鞅. 则由Doob 鞅收敛定理可知

因此有

由式(2.1), (2.9) 可知

由式(1.3) 及(2.10) 可知

由式(2.11) 可知

令|λ|≤β. 由不等式ln x ≤x −1 (x>0) 和并注意到

则对于所有的ω ∈Ω, 有

其中为了方便, 将用gt代替gt(Xt,Xt1,Xt2), 由式(2.6), (2.12) 和(2.13) 知

由式(2.5) 与(2.14) 可知

当0<λ ≤β <α 时, 将式(2.15) 左右两边同时除以λ 可知

容易看出, 当0 < c < β2Hαβ时, 函数时获得最小值可知

当c=0, 由式(2.16) 可知

令式(2.18) 中λ →0+, 可知

因此当c=0 时, 公式(2.17) 成立. 当−α<−β ≤λ<0 时, 由式(2.15) 类似可知

由式(2.17), (2.20) 可知式(2.7), 继而可知式(2.8). 故此定理2.3 得证.

3 强大数定理及渐近均分性(AEP)

本节研究二叉树指标随机场关于分枝马氏链的强大数定理与渐近均分性(AEP), 作为推论得到了二叉树指标分枝马氏链的强大数定理和渐近均分性.

设T2为二叉树, {Xt,t ∈T2} 是定义在可测空间(Ω,F) 上在G 中取值的随机变量族, 可得结论如下.

定义3.1[3]设P 是(Ω,F) 上的一个概率测度, xT(n)为XT(n)的实现. 记{Xt,t ∈T2}在概率测度P 下的分布为P(XT(n)=xT(n))=P(xT(n))>0. 设

则称fn(ω) 为XT(n)在概率测度P 下的熵密度. 如果{Xt,t ∈T2} 在概率测度Q 下是具有初始分布p(x) 和随机矩阵P 的二叉树指标分枝马氏链, 则

熵密度fn(ω) 收敛(L1收敛, 依概率收敛, a.e. 收敛) 到一个常数的性质在信息论中被称为渐近均分性(AEP) 或者是Shannon-McMillan 定理.

定义3.2[3]设Sk(T(n))(k ∈G) 是随机变量集{Xt,t ∈T(n)} 中k 出现的次数,Sn(k,l1,l2) = Sk,l1,l2(T(n)) 是随机序偶集{(Xt,Xt1,Xt2),t ∈T(n−1)} 中序偶(k,l1,l2)(k,l1,l2∈G) 出现的次数, 即

显然

定理3.3设P 与Q 是定义在F 上的两个概率测度, 并且{Xt,t ∈T2} 是由定义1.1 定义的二叉树指标分枝马氏链如定义3.2 所定义, 令

设转移矩阵P1=(P1(y1|x)),P2=(P2(y2|x)), 令转移矩阵则

其中(π(0),··· ,π(b −1)) 为由矩阵R 决定的平稳分布.

证首先转移矩阵是遍历的, 这是因为P(y1,y2|x)>0, 可知P1(y1|x)>, 所以. 即R 是遍历的.

令gt(x,y1,y2)=Ik(y1), 则

故由式(2.8) 可知

同理令gt(x,y1,y2)=Ik(y2). 类似可知

用R(m|k) 乘以式(3.7), 将对k ∈{0,1··· ,b −1} 求和, 并再次利用式(3.7) 可知

由归纳法可知

注意到

定理3.4在定理3.3 的条件下, 令如定义3.2 所述, 则

其中(π(0),··· ,π(b −1)) 为由矩阵R 决定的平稳分布.

证令则

由式(2.8) 可知

因此式(3.10) 得证.

定理3.5在定理3.3 的条件下, fn(ω) 是如(3.1) 所定义的熵密度, 则

其中(π(0),··· ,π(b −1)) 为由矩阵R 决定的平稳分布.

证因为

由式(3.2) 与式(3.10)、(3.13) 可知

由式(1.3), (3.1), (3.2) 可知

故综合式(3.14), (3.15) 可知式(3.12) 得证.

定理3.6设{Xt,t ∈T2} 在概率测度Q 下是具有严格正的随机矩阵P =(P(y1,y2|x))的二叉树指标分枝马氏链, {Xt,t ∈T2},Sn(k),Sn(k,l1,l2), fn(ω) 如定义3.2 所述, 令

设转移矩阵P1=(P1(y1|x))P2=(P2(y2|x)), 假设转移矩阵则

其中(π(0),··· ,π(b −1)) 为由矩阵R 决定的平稳分布.

证令定理3.3 中P ≡Q, 则gn(ω)=fn(ω), 进而知D(0)=Ω. 因此由式(3.4), (3.10),(3.12) 可知式(3.16), (3.17), (3.18) 得证.