设$T$是一个无限树, $\sigma$, $t(\sigma\neq t)$是$T$中任两个顶点, 则存在唯一的以$\sigma$到$t$的路径, $\sigma=z_1, z_2, \cdots, z_m=t$, 其中$z_1, z_2, \cdots, z_m$互不相同且$z_i, z_{i+1}$为相邻两顶点, $m-1$称为$\sigma$到$t$的距离.为给$T$中的顶点编号, 我们选定一个顶点作为根顶点(简称根), 并记之为$o$.如果一个顶点$t$位于根$o$到顶点$\sigma$的唯一路径上, 则记$\sigma\leq t$.若$\sigma, t$为$T$上不同的两个顶点, 记$\sigma\wedge t$为同时满足$\sigma\wedge t\leq t$和$\sigma\wedge t\leq \sigma$且离根$o$最远的顶点.

本文中$T$表示任意局部有限无穷树.若$t$为$T$中的任一顶点, 记$|t|$为顶点$t$到根$o$的距离.若$|t|=n$, 则$t$位于树的第$n$层.记$T^{(n)}$表示从根$o$到第$n$层所有顶点的子图, $L_n$表示第$n$层所有顶点的集合, $L_m^n$表示含有$T$的从$m$层到$n$层所有顶点的集合.对于任一个顶点$t$, 从根$o$到顶点$t$的路径上存在唯一一个离顶点$t$最近的顶点称为$t$的父代, 记为$1_t$, 且称$t$为$1_t$的子代. $1_t$的父代记为$2_t$, $(n-1)_t$的父代记为$n_t$, 也称$n_t$为$t$的第$n$代父代.令$X^A=\{X_t, t\in A\}$, $x^A$为$X^A$的实现, 且记$|A|$为$A$中顶点的个数.

定义1  设$T$为局部有限无穷树, 且$S=\{1, 2, \cdots, m\}$.令

$ P_t=(P_t(x_t|x_{1_t}, x_{2_t}, \cdots, x_o)), \quad P_t(x_t|x_{1_t}, x_{2_t}, \cdots, x_o)\geq0, $

其中$t\in T\backslash \{o\}, x_t, x_{1_t}, x_{2_t}, \cdots, x_o\in S$.如果$\sum\limits_{x_t\in S}P_t(x_t|x_{1_t}, x_{2_t}, \cdots, x_o)=1, $则称$P_t$为树$T$上路径条件概率矩阵族.

定义2  设有限状态空间$S=\{1, 2, \cdots, m\}$, $\{X_t, t\in T\}$为定义在概率空间$(\Omega, {\cal F}, P )$上的$S$值变量族.设

$ p=(p(x), x\in S), $

(1)

$ P_t=(P_t(x_t|x_{1_t}, x_{2_t}, \cdots, x_o)), x_t, x_{1_t}, x_{2_t}, \cdots, x_o\in S, \ \ t\in T\backslash \{o\} $

(2)

分别为$S$上的概率分布和路径条件概率矩阵族.如果对于任何顶点$t(t\neq o)$,

$ \begin{aligned}& P(X_{t}=x_t|X_{{1}_t}=x_{{1}_t}, X_{{2}_t}=x_{{2}_t}, \cdots, X_o=x_o \ \ \mbox{和} \ \ X_{\sigma} \ \ \mbox{满足} \ \ t \wedge \sigma\leq {1}_t)\\ =&P(X_{t}=x_t|X_{{1}_t}=x_{{1}_t}, X_{{2}_t}=x_{{2}_t}, \cdots, X_o=x_o)\\ =& P_t(x_t|x_{{1}_t}, x_{{2}_t}, \cdots, x_o), \ \ \forall x_t, x_{1_t}, x_{2_t}, \cdots, x_o\in S, \end{aligned} $

(3)

且

$ P(X_{o}=x)=p(x), \ \ \forall x \in S, $

(4)

则称$\{X_t, t\in T\}$为具有初始分布(1) 和路径条件概率矩阵族(2) 的树指标$S$值路径过程.

注1  如果树$T$上的每个顶点仅与其父代有关, 而与其他顶点无关, 则上述树上路径过程就是树指标非齐次马氏链.对于树指标非齐次马氏链的详细定义, 读者可参考文献[14].特别地, 如果树指标非齐次马氏链的每个顶点只有一个子代, 此时树指标马氏链即为非齐次马氏链.

设$P_t(x_t|x_{1_t}, x_{2_t}, \cdots, x_o)=P_t(X_t=x_t|X_{1_t}=x_{1_t}, X_{2_t}=x_{2_t}, \cdots, X_o=x_o)$, 则称$P_t(X_t|X_{1_t}, X_{2_t}, \cdots, X_o)$为树上路径过程的随机路径条件概率. Benjamini和Peres^[1]给出了树指标马氏链的定义并研究了其常返性和射线常返性. Berger和叶中行^[2]研究了齐次树图上平稳随机场熵率的存在性.叶中行和Berger^{[3, 4]}利用Pemantle在文献[5]中的结果及组合方法, 在依概率收敛意义下研究了齐次树图上PPG不变和遍历随机场的Shannon-McMillan定理.杨卫国和刘文^[6]研究了齐次树图上马氏链场(这实际上是树指标马氏链和PPG不变随机场的特殊情形)状态发生频率的强大数定律.杨卫国^{[7, 8]}研究了齐次树上齐次和非齐次马氏链的状态发生频率的强大数定律.近年来, 刘文^{[9, 10, 11]}应用了条件矩母函数的方法, 研究了随机转移概率的若干极限性质和调和平均.石志岩和杨卫国^[12]研究了树上路径过程随机条件概率的极限性质.王华山和杨卫国、石志岩^[16]研究了树指标非齐次马氏链随机转移概率的几何平均强极限定理.

设$\{X_{t}, t\in T\}$为在$S$中取值的树指标随机过程, $x^{T^{(n)}}$为$X^{T^{(n)}}$的实现.记

$ P(x^{T^{(n)}})=P(X^{T^{(n)}}=x^{T^{(n)}}). $

当树$T$为树指标路径过程时, 易知

$ P(x^{T^{(n)}})=P(X^{T^{(n)}}=x^{T^{(n)}})=P(X_{o}=x_{o})\Pi_{t\in T^{(n)}\backslash\{o\}}P_{t}(x_{t}|x_{1_{t}}, x_{2_{t}}, \cdots, x_{o}). $

(5)

令

$ f_n(\omega)=-\frac{1}{|T^{(n)}|}\ln P(X^{T(n)}), $

称$f_n(\omega)$为$X^{T^{(n)}}$的熵密度.如果$\{X_{t}, t\in T\}$如定义$2$定义的树上路径过程, 由式$(5)$可得

$ f_n(\omega)=-\frac{1}{|T^{(n)}|}[\ln P(X_{o})+\sum\limits_{t\in T^{(n)}\backslash \{o\}}\ln P_t(X_t|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})] . $

(6)

$f_n(\omega)$在某种意义下($L_{1}$收敛, 依概率收敛, 几乎处处收敛)收敛于常数, 称为Shannon-McMillan定理, 或信源的渐近均分割性$(AEP)$以及熵定理, 它是信息论的基本定理, 也是各种编码定理的基础.对于渐近均分割性$(AEP)$或Shannon-McMillan定理的研究: Barron^[17]和Orey^[18]给出了连续值遍历过程的几乎处处收敛的渐近均分割性. Algoet和Cover^[19]应用“三明治”方法给出了一般渐近均分割性的证明.

本文主要研究了树上路径过程的几何平均强极限定理和树上路径过程关于状态出现频率的强极限定理.首先得到了树上路径过程的随机路径条件概率用不等式表示的几何平均强极限定理, 给出了树上路径过程熵密度的一个上确界.其次研究了树上路径过程关于状态序偶出现频率的用不等式表示的强极限定理, 同时推广了一些已有的结果.

引理1  设$\{X_t, t\in T\}$是定义在测度空间$(\Omega, {\cal F})$上在S中取值的随机变量族, $\mu_{1}$与$\mu_{2}$是可测空间$(\Omega, {\cal F})$上的两个不同的概率测度, 记

$ \mu_{i}(X^{T^{(n)}}=x^{T^{(n)}})=\mu_{i}(x^{T^{(n)}}), \ \ i=1, 2. $

(7)

则

$ \limsup\limits_{n\to\infty}\frac{1}{|T^{(n)}|}\ln\frac{\mu_{2}(X^{T^{(n)}})}{\mu_{1}(X^{T^{(n)}})}\leq0, \ \ \ \mu_{1}-{\hbox{a.e.}}. $

(8)

证  证明的方法类似于文献[16]中引理$1$, 这里省略证明.

定理1   设$P$为$(\Omega, {\cal F})$上的概率测度, $\{X_{t}, t\in T \}$在$P$下为定义$2$中的在$S$中取值的树指标路径过程, 其概率分布和路径条件概率矩阵族分别为式$(1)$与$(2), $则随机路径条件概率$\{P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o}), t\in T^{(n)}\backslash \{o\}\}$的几何平均的下极限在概率测度$P$下几乎处处不小于$\frac{1}{m}$, 即

$ \liminf\limits_{n\to \infty}(\prod\limits_{t\in T^{(n)}\backslash \{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o}))^{\frac{1}{|T^{(n)}|}}\geq \frac{1}{m}, \ \ P-{\hbox{a.e.}}. $

(9)

证  设$Q$为$(\Omega, {\cal F})$上另一概率测度, 且$\{X_{t}, t\in T\}$在$Q$下是独立同分布的, 且$X_{t}$在$S$上是均匀分布, 即$Q(X_{t}=x)=\frac{1}{m}, x\in S, $则$Q(x^{T^{(n)}})=(\frac{1}{m})^{|T^{(n)}|}, $由引理$1$可得

$ \begin{eqnarray*} &\, \,&\limsup\limits_{n\to \infty} (\frac{Q(X^{T^{(n)}})}{P(X^{T^{(n)}})})^{\frac{1}{|T^{(n)}|}}\\ &=&\limsup\limits_{n\to \infty}\frac{\frac{1}{m}}{(P(X_{o})\prod _{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o}))^{\frac{1}{|T^{(n)}|}}}\\ & \leq&1, \ \ P-{\hbox{a.e.}}, \end{eqnarray*} $

所以

$ \liminf\limits_{n\to \infty}(\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o}))^{\frac{1}{|T^{(n)}|}}\geq \frac{1}{m}, \ \ P-{\hbox{a.e.}}. $

故结论成立.

注2  在式(9) 两边取对数可得

$ \liminf\limits_{n\to \infty}{\frac{1}{|T^{(n)}|}}\sum\limits_{t\in T^{(n)}\backslash \{o\}}\ln P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})\geq -\ln m, \ \ P-{\hbox{a.e.}}. $

(10)

由式(6) 和(10) 可知

$ \limsup\limits_{n\to \infty}f_n(\omega)\le\ln m, \ \ P-{\hbox{a.e.}}, $

(11)

因此上式给出了树指标路径过程的熵密度的上确界不超过状态数的对数.

注3   显然, 对于树上非齐次马氏链的类似结果(见文献[16]), 我们由定理1即得.

定理2  设$P$为$(\Omega, {\cal F})$上的概率测度, $\{X_{t}, t\in T\}$在$P$下为定义$2$中的树上路径过程, 其初始概率分布和路径条件概率矩阵族分别为式$(1)$与$(2)$.设$i\in S, S_{n}(i, \omega)$是$\{X_{t}: t\in T^{(n)}\}$中$i$的个数, 即$S_{n}(i, \omega)=\sum\limits_{t\in T^{(n)}}\delta_{i}(X_{t}), $其中$\delta_{i}(\cdot), (i\in S)$是$S$上的Kronecher-$\delta$函数.

(1) 如果存在一个常数$r\in [\frac{1}{m}, 1)$使得

$ \limsup\limits_{n\to \infty}(\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o}))^{\frac{1}{|T^{(n)}|}}\leq r, \ \ P-{\hbox{a.e.}}, $

(12)

那么就有

$ \limsup\limits_{n\to \infty}\frac{1}{|T^{(n)}|}S_{n}(i, \omega)\leq p, \ \ P-{\hbox{a.e.}}, $

(13)

其中$P$是关于$\lambda(0<\lambda<1)$的方程

$ \lambda^{\lambda}[{(1-\lambda)}/{(m-1)}]^{1-\lambda}=r $

(14)

在区间$[\frac{1}{m}, 1)$的唯一解.

(2) 如果存在一个常数$r\in [\frac{1}{m}, \frac{1}{m-1})$使得式$(12)$成立, 那么

$ \liminf\limits_{n\to \infty}\frac{1}{|T^{(n)}|}S_{n}(i, \omega)\geq q, \ \ P-{\hbox{a.e.}}, $

(15)

其中$q$是方程$(14)$在区间$(0, \frac{1}{m}]$上的唯一解.

证  设$Q$为$(\Omega, {\cal F})$上另一概率测度, 且$\{X_{t}, t\in T\}$在$Q$下是独立同分布的, $X_{t}$的分布为$Q(X_{t}=i)=\lambda, $ $Q(X_{t}\neq i)=(1-\lambda)/(m-1), $则

$ Q(X^{T^{(n)}})=\lambda^{S_{n}(i, \omega)}(\frac{1-\lambda}{m-1})^{|T^{(n)}|-S_{n}(i, \omega)}, $

由引理$1$有

$ \limsup\limits_{n\to \infty}(\frac{Q(X^{T^{(n)}})}{P(X^{T^{(n)}})})^{\frac{1}{|T^{(n)}|}}\leq 1, \ \ P-{\hbox{a.e.}}, $

即

$ \limsup\limits_{n\to \infty}[\frac{\lambda^{S_{n}(i, \omega)}(\frac{1-\lambda}{m-1})^{|T^{(n)}|-S_{n}(i, \omega)}} {P(X_{o})\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})}]^{\frac{1}{|T^{(n)}|}}\leq 1, \ \ P-{\hbox{a.e.}}. $

由于

$ \begin{array}{l} \;\;\;\;\;\limsup\limits_{n\rightarrow\infty}[\frac{\lambda(m-1)}{1-\lambda}]^{\frac{S_{n}(i, \omega)}{|T^{(n)}|}}(\frac{1-\lambda}{m-1}) = \limsup\limits_{n\rightarrow\infty}[\lambda^{S_{n}(i, \omega)}(\frac{1-\lambda}{m-1})^{|T^{(n)}|-S_{n}(i, \omega)}]^{\frac{1}{|T^{(n)}|}}\\ = \limsup\limits_{n\rightarrow\infty}\frac{[\lambda^{S_{n}(i, \omega)}(\frac{1-\lambda}{m-1})^{|T^{(n)}|-S_{n}(i, \omega)}]^{\frac{1}{|T^{(n)}|}}} {[P(X_{o})\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})]^{\frac{1}{|T^(n)|}}}\\ \;\;\;\;\;\times [P(X_{o})\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})]^{\frac{1}{|T^{(n)}|}}\\ \leq \limsup\limits_{n\rightarrow\infty}\frac{[\lambda^{S_{n}(i, \omega)}(\frac{1-\lambda}{m-1})^{|T^{(n)}|-S_{n}(i, \omega)}]^{\frac{1}{|T^{(n)}|}}} {[P(X_{o})\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})]^{\frac{1}{|T^{(n)}|}}}\\ \;\;\;\;\;\times \limsup\limits_{n\rightarrow\infty}[P(X_{o})\prod\limits_{t\in T^{(n)}\backslash\{o\}}P_{t}(X_{t}|X_{1_{t}}, X_{2_{t}}, \cdots, X_{o})]^{\frac{1}{|T^{(n)}|}} \leq r, \ \ P-{\hbox{a.e.}}, \end{array} $

所以

$ \limsup\limits_{n\to \infty}[\frac{\lambda(m-1)}{1-\lambda}]^{\frac{S_{n}(i, \omega)}{|T^{(n)}|}}\leq \frac{r(m-1)}{1-\lambda}, \ \ \ P-{\hbox{a.e.}}, $

(16)

于是

$ \limsup\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\ln \frac{\lambda(m-1)}{1-\lambda}\leq \ln \frac{\lambda(m-1)}{1-\lambda}, \ \ \ \ P-{\hbox{a.e.}}. $

(17)

(1) 假设$\frac{1}{m}<\lambda<1, $由式$(17)$得

$ \limsup\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\leq \frac{\ln \frac{r(m-1)}{1-\lambda}}{\ln\frac{\lambda(m-1)}{1-\lambda}}, \ \ P-{\hbox{a.e.}}. $

(18)

令

$ \varphi(\lambda)=\frac{\ln\frac{r(m-1)}{1-\lambda}}{\ln\frac{\lambda(m-1)}{1-\lambda}}, \ $

(19)

由$\varphi^{\prime}(\lambda)=0$得

$ \lambda^{\lambda}[(1-\lambda)/(m-1)]^{1-\lambda}=r, $

(20)

令

$ \phi(\lambda)=\lambda^{\lambda}[(1-\lambda)/(m-1)]^{1-\lambda}, $

(21)

易证$\phi(\lambda)$在$[\frac{1}{m}, 1)$上是单调递增的, 且$\phi(\frac{1}{m})=\frac{1}{m}, \lim\limits_{\lambda\to 1^{-}}\phi(\lambda)=1.$因此, 对于$\frac{1}{m}<r<1, $式$(20)$在区间$(\frac{1}{m}, 1)$上有唯一解, 记为$p, $易见$\varphi(\lambda)$在区间$(\frac{1}{m}, 1)$上在$\lambda=p$处取得最小值, 且$\varphi(p)=p.$对于式$(19), $令$\lambda=p, $可得到

$ \limsup\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\leq p, \ \ P-{\hbox{a.e.}}, $

(22)

在区间$[\frac{1}{m}, 1)$上, 当$r=\frac{1}{m}$时, $\frac{1}{m}$显然是式$(20)$的唯一解.这时, 选$\lambda_{k}\in \left(\frac{1}{m}, 1\right), k=1, 2, \cdots, $使得$\lambda_{k}\to \frac{1}{m}(k\to \infty).$那么对所有$k\geq 1, $由式$(18)$和式$(19)$可得

$ \limsup\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\leq \varphi(\lambda_{k}), \ \ P-{\hbox{a.e.}}, $

(23)

又由于$\lim\limits_{\lambda_{k}\to \frac{1}{m}}\varphi(\lambda_{k})=\frac{1}{m}, $所以

$ \limsup\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\leq \frac{1}{m}, \ \ P-{\hbox{a.e.}}. $

(24)

由式$(22)$和$(24)$即可知式$(13)$成立.

(2) 假设$0<\lambda<\frac{1}{m}, $根据式$(18), $有

$ \liminf\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\geq \frac{\ln \frac{r(m-1)}{1-\lambda}}{\ln \frac{\lambda(m-1)}{1-\lambda}}, \ \ P-{\hbox{a.e.}}. $

(25)

令$\varphi(\lambda)$和$\phi(\lambda)$分别如式$(19)$和$(21)$所定义.易证$\phi(\lambda)$在$\left(0, \frac{1}{m}\right)$上是单调递减的, 且$\lim\limits_{\lambda\to 0^{+}}\phi(\lambda)=\frac{1}{m-1}.$进而, 当$\frac{1}{m}<r<\frac{1}{m-1}$时, 式$(20)$在$\left(0, \frac{1}{m}\right)$上有唯一解, 记为$q.$易见在区间$\left(0, \frac{1}{m}\right)$上, $\varphi(\lambda)$的最大值在$\lambda=q$处达到, 且

$ \varphi(q)=q, $

(26)

在式$(25)$中令$\lambda=q, $根据式$(26), $可得到

$ \liminf\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\geq q, \ \ P-{\hbox{a.e.}}, $

(27)

显然当$r=\frac{1}{m}$时, $\frac{1}{m}$也是式$(20)$在区间$\left(0, \frac{1}{m}\right]$上的唯一解.选取$\tau_{k}\in \left(0, \frac{1}{m}\right), k=1, 2, \cdots, $使得$\tau_{k}\to \frac{1}{m}(k\to \infty).$仿照式$(22), $可证明当$r=\frac{1}{m}$时, 有

$ \liminf\limits_{n\to \infty}\frac{S_{n}(i, \omega)}{|T^{(n)}|}\geq \frac{1}{m}, \ \ P-{\hbox{a.e.}}. $

(28)

成立.由式$(27)$和$(28)$可知式$(15)$成立.

显然, 对于树指标非齐次马氏链和非齐次马氏链的类似结果(见文献[16]), 我们由定理2即得.