中国科学院大学学报  2017, Vol. 34 Issue (1): 1-7   PDF    
变化环境中分枝树上有偏随机游动的状态分类
张志洋, 胡晓予     
中国科学院大学数学科学学院, 北京 100049
摘要: 考虑变化环境中分枝树上的广义有偏随机游动,分别得到随机游动为暂留的、正常返的和零常返的充分条件,为进一步研究这类随机游动的中心极限定理等性质做了铺垫。
关键词: 树上随机游动     变化环境中分枝过程     常返性     暂留性    
Classification of states for a biased random walk on a branching tree in the varying environment
ZHANG Zhiyang, HU Xiaoyu     
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
Abstract: In this study we investigate biased random walk on branching trees in the varying environment. We have obtained the sufficient conditions for transience, positive recurrence, and null recurrence. Our main result enables the further study on the central limit theory for this kind of random walks.
Key words: random walk on a tree     branching process in the varying environment     recurrence     transience    

随机游动是随机过程中的一个经典模型。早在概率论发展初期,就有人曾经考虑过直线上的简单随机游动和有偏随机游动等问题[1]。如今这方面的研究对象已经从直线上的随机游动扩展到随机图和网络上的随机游动, 以及随机环境中的随机游动和各种代数结构上的随机游动[2-4]

随机游动研究中的一个基本问题是状态分类问题。历史上Kolmogorov, Polya, Kakutani等都曾经讨论过这一问题, Polya还给出了${{\mathbb{N}}^{n}}$上随机游动常返性判别的经典结果[5]。1984年Doyle与Snell[6]系统性地总结前人的结果, 将随机游动与电网络联系起来, 利用电导函数描述随机游动的常返性和暂留性。其后, Lyons[7]得到树上随机游动的状态分类结果;在他的工作基础上, Peres和Zeitouni[8]运用经典分枝树上的λ-有偏随机游动的可逆性和耦合方法得到这种随机游动的中心极限定理。

2006年Collevecchio[9]利用另一种方法, 在Lyons工作的基础上得到经典分枝树上的λ-有偏随机游动的状态分类结果。我们则考虑变化环境中的分枝树上的广义有偏随机游动, 得到其状态分类的结果,文献[9]中的结果恰为我们的结论的特例。

1 背景知识

设(Ω, $\mathscr{F}$, P)为一个概率空间, 本文以下涉及的随机变量均定义在此空间上, 由P决定的期望记为E。记$\mathbb{N}^*$为全体正整数构成的集合,$\mathbb{N}$={0}∪$\mathbb{N}^*$。若存在正常数c1c2>0使得当x充分大时, 有

$ {c_1}g\left( x \right) \le f\left( x \right) \le {c_2}g\left( x \right), $

则记f(x)≈g(x), x→∞。

定义1.1   (树)设U为由如下形式的有限正整数序列所构成的集合: < i1, i2, …, in > , 其中ik$\mathbb{N}^*$, 1≤kn, n$\mathbb{N}$(当n=0时,表示空序列)。对于任一个U的子集T,若它满足如下条件:

(a)空序列ϕT;

(b)若对某个jN*, < i1, i2, …, ik, j > ∈T,则必有 < i1, …, ik > ∈T;

(c)若u= < i1, i2, …, ik > ∈T, νu(T)是依赖于uT的某正整数(也称νu(T)为T上节点u的分枝数),则对于所有的1≤jνu(T),总有 < i1, i2, …, ikj > ∈T;

则称T为一棵树,空序列称为树的根, 以o记之。称T中全体序列长度的上确界为树T的高度。若v= < i > ∈T,则称

$ {T^v}:{\rm{ = }}\{ < i, {i_1}, {i_2}, \cdots, {i_n} > < i, {i_1}, {i_2}, \cdots, {i_n} > \in T{\rm{\} }} $

T中根为v的子树。任取n≥1,记树T在高度n处的截断为

$ T{|_n}{\rm{: = \{ }} < {i_1}, {i_2}, \cdots, {i_k} > \in T;k \le n\} . $

对任意的n,称 < i1, i2, …, in > ∈TT的顶点,以v记之。设u, vT上的2个顶点,若存在i1, i2, …, inj使v= < i1, i2, …, in > , u= < i1, i2, …, in, j > ,则称vu的父亲,记为$v=\overleftarrow u $;或称uv的儿子,也可记为$u=\overrightarrow v $。记顶点v的儿子个数为dv(T)(或dv);记顶点v的第n代子孙的全体为Dn(T, v)(或Dn(v));根o的第n代子孙的全体记为Dn(T);以|Dn(T)|记第n代子孙的个数;记v为顶点vTT的根o的距离,即从根ov最短路径上边的总数,有时也称节点v具有高度|v|。

$\mathscr{T}$为全体树构成的集合,则在度量$d\left ({T, T'} \right)=\frac{1}{{1 + \mathop {\sup }\limits_n \left\{ {n:T{{\left| {_n=T'} \right|}_n}} \right\}}}\left ({T, T' \in \mathscr{T}} \right)$下,($\mathscr{T}$d)构成一个度量空间。

定义1.2(G-W过程和分枝树)令Z0=1且对于任意的n≥0,

$ {z_{n + 1}} = \left\{ {\begin{array}{*{20}{c}} {\sum\limits_{j = 1}^{{Z_n}} {{X_{n, j}}, } }&{{Z_n} \ne 0, }\\ {0, \;\;\;\;\;\;\;\;}&{{Z_n} = 0, } \end{array}} \right. $

其中{Xn, j, n≥0, j≥1}为独立同分布的随机变量序列,其共同分布为{p(j), j≥0}, {Zn:n≥0}称为经典的Galton-Watson分枝过程,简称为GW过程,记$m=\sum\nolimits_{j=1}^\infty {jp\left (j \right)} $。本文中总假设p(0)=0,0 < p(1) < 1。若m>1,则称该分枝过程为上临界的。以分枝连接每一代的个体, 得到的图称为经典分枝树。

定义1.3   (G-W测度)设{p(k), k≥0}为某Galton-Watson过程的分布律,${\rm{\mathscr{B}(\mathscr{T})}}$为度量空间${(\mathscr{T}, d)}$的Borel σ-代数,根据文献[10]中的结论,在$(\mathscr{T}, \mathscr{B}(\mathscr{T}{\rm{ }}))$上存在一个唯一的概率测度,为GW,它满足:任取n个非负整数kj, 1≤jn,再取n个任意的顶点v1, v2, …, vn, n≥1,

$ \begin{array}{c} GW\left\{ {T \in F:{v_j} \in T, 1 \le j \le n, \mathop \cap \limits_{j = 1}^n \left\{ {{d_{{v_j}}} = {k_j}} \right\}} \right\}\\ = \prod\limits_{j = 1}^n p \left( {{k_j}} \right). \end{array} $

本文中由测度GW决定的期望记为EGW

类似地,可以定义变化环境中的分枝过程,以及变化环境中的分枝树。

定义1.4   令Y0=1且对于任意的n≥0,

$ {Y_{n + 1}} = \left\{ {\begin{array}{*{20}{c}} {\sum\limits_{j = 1}^{{Y_n}} {{U_{n + 1, j}}, \left( x \right)} }&{{y_n} \ne 0;}\\ {0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}&{{Y_n} = 0, } \end{array}} \right. $

其中{Un, j:n≥1, j≥1}是相互独立的随机变量序列,对任意给定的n≥1, {Un, j:j≥1}有相同的概率分布{p(n)(j), j$\mathbb{N}$},称{Yn:n≥0}为变化环境中的分枝过程,记${m_n}=\sum\nolimits_{j=1}^\infty {j{p^{(n)}}\left (j \right)} $。当mn>1, n≥1时,称该分枝过程为上临界的。以分枝连接每一代的个体, 得到的图称为变化环境中的分枝树。本文总假设

$ {p^{(n)}}(0) = 0, 0 < {p^{(n)}}(1) < 1, n \ge 1. $

定义1.5   设{p(l)(j), l≥1, j≥0}为某一个变化环境中的分枝过程的分布律,${\rm{\mathscr{B}(\mathscr{T})}}$为度量空间${(\mathscr{T}, d)}$上的Borel σ-代数, 定义集合函数VGW如下:任取n≥1以及n个非负整数kj, 1≤jn,再取n个任意的顶点分别记为v1, v2, …, vn,令

$ \begin{array}{c} VGW\left\{ {T \in F:{v_j} \in T, 1 \le j \le n, \;\mathop \cap \limits_{j = 1}^n \left\{ {{d_{{v_j}}} = {k_j}} \right\}} \right\}\\ = \prod\limits_{j = 1}^n {{p^{\left( {\left| {{v_j}} \right|} \right)}}\left( {{k_j}} \right).} \end{array} $

可以证明VGW可唯一扩张为${\rm{\mathscr{B}(\mathscr{T})}}$上的一个概率测度, 详见下节命题2.1。

定义1.6   给定一棵由上临界的G-W树T,其分布律为{p(k), k≥0}, 设{Xn:n≥0}为定义在${\rm{(}}\Omega, \mathscr{F}, P)$上取值于T且从根o出发的马氏链, 其转移概率为

$ {P_T}\left( {{X_{n + 1}} = w|{X_n} = v} \right) = \left\{ \begin{array}{l} \frac{\lambda }{{\lambda + {d_v}}}, v = \overrightarrow w, \\ \frac{1}{{\lambda + {d_v}}}, w = \overrightarrow v, v \ne o, \\ \frac{1}{d}, v = o, w = \overrightarrow o . \end{array} \right. $

其中w, vT, λ为正常数, 我们称{Xn:n≥0}为GWT上的λ-有偏随机游动。

类似地,可以定义变化环境中分枝树上的{λn, n≥1}-有偏随机游动如下。

定义1.7   给定一棵上临界的变化环境中的分枝树T,其后代分布律为{p(n)(j), n≥1, j≥0},又给定一列正实数{λl, l≥1},若{Vn:n≥0}为定义在${\rm{(}}\Omega, \mathscr{F}, P)$上取值于T且从根o出发的马氏链, 其转移概率为

$ {P_T}\left( {{V_{n + 1}} = w|{V_n} = v} \right) = \left\{ \begin{array}{l} \frac{{{\lambda _{\left| v \right|}}}}{{{\lambda _{\left| v \right|}} + {d_v}}}, v = \overrightarrow w, \\ \frac{1}{{{\lambda _{\left| v \right|}} + {d_v}}}, w = \overrightarrow v, v \ne o, \\ \frac{1}{{{d_o}}}, v = o, w = \overrightarrow {o.} \end{array} \right. $

其中w, v∈T,对任意的uT, |u|=l, du的分布律为{p(l+1)(k), k≥0},我们称{Vn:n≥0}为变化环境中分枝树T上的{λn, n≥1}-有偏随机游动。

根据Lyons[7]关于树上有偏随机游动状态分类的结论可得

对于一个个体平均生殖个数为m>1的G-W树上的λ-有偏随机游动{Xn:n≥0}而言:当λ>m时,对几乎所有的GW-树Tλ-有偏随机游动{Xn:n≥0}是正常返的;当λ=m时,对几乎所有的GW-树T, λ-有偏随机游动{Xn:n≥0}是零常返的;当λ < m时,对几乎所有的GW-树T, λ-有偏随机游动{Xn:n≥0}是暂留的。

关于变化环境中分枝树上的{λn, n≥1}-有偏随机游动,我们的主要结果如下:

定理1.1   设{Yn, n≥0}是一个上临界的变化环境中的分枝过程,设{mn, n≥1}如前所定义。给定一列实数λn>0(n≥1)及一棵由{Yn, n≥0}决定的分枝树T,{Xn, n≥0}是取值于T的{λn, n≥1}-有偏随机游动,则有如下结论:

1)若{λn, n≥1}与{mn, n≥1}满足:存在正整数n>1,使得

$ \frac{{{m_2} \cdots {m_n}}}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{n-1}}}} > 1 $

$ \frac{{{m}_{(k-1)n+1}}-{{m}_{kn}}}{1+\sum\limits_{l=1}^{n}{\prod\limits_{j=1}^{l}{{{\lambda }_{\left( k-1 \right)n+j-1}}}}}>1,k\ge 2, $ (1)

则存在${\mathscr{T}_0} \subset \mathscr{T}$满足VGW$({\mathscr{T}_0})$>0且任取T$({\mathscr{T}_0})$, PT({Xn, n≥0}不返回根节点)>0;

2)若{λn, n≥1}与{mn, n≥1}满足

$ \sum\limits_{n=2}^{\infty }{\frac{{{m}_{1}}\cdots {{m}_{n}}}{1\text{+}\sum\limits_{l=1}^{n-1}{\prod\limits_{j=1}^{l}{{{\lambda }_{j}}}}} < \infty ,} $ (2)

则对VGW-a.s.T,随机游动{Xn, n≥0}是正常返的(关于PT);

3)若对VGW-a.s.T,随机游动{Xn, n≥0}关于PT是常返的,而且

$ \sum\limits_{n=2}^{\infty }{\frac{\left| {{D}_{n}}(T) \right|}{1+\sum\nolimits_{l=1}^{n-1}{(\prod\nolimits_{j=1}^{l}{{{\lambda }_{j}}})}}=\infty ,} $ (3)

则对VGW-a.s.T,随机游动{Xn, n≥0}是零常返的(关于PT)。

2 主要定理的证明

命题2.1   VGW可唯一扩张为${\rm{\mathscr{B}(\mathscr{T})}}$上的一个概率测度。

证明   考虑乘积空间${\mathscr{T}^*}$=${\mathbb{N}^U}$,其中U如定义1.1设,现在任取uU, |u|=n, 记q(u)={p(n+1)(j):j=0, 1, …}, 对任意的u1, u2, …, unU, |ui|=ki, 1≤in,存在唯一一个${\mathbb{N}^{*n}}$上的乘积测度×i=1nq(ui),使得对${\mathbb{N}^{*n}}$中任意一个单点集{ < i1, …, in > }有

$ \times _{i = 1}^n{q^{\left( {{u_i}} \right)}}(\{ < {i_1}, {i_2}, \cdots, {i_n} > \} ) = \prod\limits_{j = 1}^n {{p^{\left( {{k_i} + 1} \right)}}\left( j \right)} . $

容易验证这些形如×i=1nq(ui)的测度满足Kolmogrov相容性条件。

给定uU,设$v_u^*:{\mathscr{F}^*} \to \mathbb{N}$。定义ψ:${\mathscr{T}^*} \to \mathscr{T}$如下: ψ(ω*)=T,其中树T上的每个节点u= < j1, …, jp>, p$\mathbb{N}$满足

$ {j_{k + 1}} \le v_{ < {j_1}, \cdots, {j_k} > }^*({w^*}), 0 \le k \le p. $

由文献[10]中的结论知ψ可测。根据Kolmogrov相容性定理,前面满足相容性条件的测度族唯一确定${\mathscr{T}^*}$上的一个概率测度,记为pq*,定义${p_q}=p_q^* \circ {\psi ^{-1}}$,则pq${\mathscr{T}^*}$上的一个概率测度。pq即为VGW的唯一扩张。

通篇假定对于任意的n≥1,

$ {m_n} = {\sum\limits_{k \ge 1} {kp} ^{(n)}}\left( k \right) > 1, $

则变化环境中的分枝树关于上述测度VGW几乎必然不是有限树。本文中将概率测度VGW决定的数学期望记为EVGW

受文献[9]中方法的启发,我们用变化环境中的分枝树的生殖规律与有偏随机游动的有偏参数的性质讨论状态分类。沿用文献[11]中使用的测度定义体系, 严格给出了状态分类定理的证明。

为证明定理1.1,首先需要下面一个引理。因为我们没有在文献中找到这一结果的证明,所以将详细的证明陈述如下。

引理2.1   设{St:t≥0}是取值于$\mathbb{N}$上的时齐马氏链, 给定0 < pt < 1, t≥1, St转移概率如下:

$ P\left( {{S_{t + 1}} = 1|{S_t} = 0} \right) = 1 = {p_0}, $
$ P\left( {{S_{t + 1}} = n + 1|{S_t} = n} \right) = {p_n}, $
$ P\left( {{S_{t + 1}} = n + 1|{S_t} = n} \right) = 1-{p_n}: = {q_n}. $

B$\mathbb{N}$的非空子集, 定义

$ {\tau _B} = {\rm{inf}}\left\{ {k \ge 0:{S_k} \in B} \right\}, $

特别地, 记

$ {\tau _j} = {\tau _{\left\{ j \right\}}}, j \in \mathbb{N}, $

又记

$ {\delta _j} = \frac{{{q_j}}}{{{p_j}}}, j \ge 1, $

则有

$ P\left( {{\tau _0}.{\tau _{n + 1}}|{S_0} = 1} \right) = 1/[\sum\limits_{k = 1}^n {(\prod\limits_{j = 1}^k {{\delta _j}} ) + 1}], n \ge 1, $

特别地, 当pn=qn=1/2(其中n≥1)时, p(τ0>τn+1|S0=1)=1/(n+1),pnp, qnq=1-p, pq时,这就是一个经典的赌徒输光问题,$P ({\tau _0} > {\tau _{n + 1}}|{S_0}=1)=\frac{{q/p-1}}{{{{(q/p)}^{n + 1}}-1}}$,这些结果均与经典结果吻合[1]

证明

$\tau _i^{(j)}=\inf \left\{ {t \ge j:{S_t}=i} \right\}$,则τi(0)=τi

ak=P(τ0>τn+1|S0=k), k≥0。

首先有

$ {a_0} = P({\tau _0} > {\tau _{n + 1}}|{S_0} = 0) = 0, $
$ {a_0} = P({\tau _0} > {\tau _{n + 1}}|{S_0} = 0) = 0, \;\;{a_{n + 1}} = P\left( {{\tau _0} > {\tau _{n + 1}}|{S_0} = n + 1} \right) = 1, n \ge 1. $

对于任意的0 < kn,有

$ P({\tau _0} > {\tau _{n + 1}}|{S_0} = k) = P\left( {\tau _0^{(1)} > \tau _{n + 1}^{(1)}|{S_1} = k} \right), $

进而用马氏性进行递推得

$ \begin{array}{l} {a_k} = P({\tau _0} > {\tau _{n + 1}}|{S_1} = k + 1)P\left( {{S_1} = k + 1|{S_0}{\rm{ = }}k} \right) + \\ P({\tau _0} > {\tau _{n + 1}}|{S_1} = k-1)P({S_1} = k-1|{S_0} = k) = \\ {P_k}{a_{k + 1}} + {q_k}{a_{k-1}}, \end{array} $

由上式得

$ \begin{array}{c} {a_{k + 1}}-{a_k} = \frac{{{q_k}}}{{{p_k}}}\left( {{a_k}-{a_{k-1}}} \right) = {\delta _k}({a_k} - {a_{k - 1}}), \\ 0 < k < n + 1. \end{array} $

进而

$ {a_{k + 1}}-{a_k} = (\prod\limits_{j = 1}^k {{\delta _j}} ){a_1}, 0 < k < n + 1, $

于是

$ 1 = {a_{n + 1}}-{a_0} = \sum\limits_{k = 0}^n {({a_{k + 1}}-{a_k}) = \sum\limits_{k = 1}^n {(\prod\limits_{j = 1}^k {{\delta _j}} ){a_1} + {a_1}, } } $

最后

$ [\sum\limits_{k = 1}^n {(\prod\limits_{j = 1}^k {{\delta _j}} ) + 1}]{a_1} = 1 $

引理得证。

定理1.1的证明:

先证明1)。设:

$ {\overline X _n}(T, \omega ):(\mathscr{T} \times \Omega, \mathscr{B}(\mathscr{T}) \times \mathscr{T}) \to (U, \mathscr{G}), n \ge 1, $

$\overline {{X_{\left (0 \right)}}}=o, o$为T的根。${\overline X _n}(T, \omega)$取值于T上的节点而且每经过一个时刻移动至T上与之相邻的节点,固定T, {Xn(T), n≥0}是T上的{λn}-有偏随机游动(关于PT)。定义

$ \tau (T, \omega ) = inf\{ j \ge 1:{\overline X _j}(T, \omega ) = o\} ; $

其中oT的根,对于vo定义

$ {{T}_{v}}(T,\omega )=\left\{ \begin{matrix} \inf \{k\ge 0:{{\overline{X}}_{k}}=v\}, & v\in T, \\ \infty ,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & v\notin T; \\ \end{matrix} \right. $
$ {{H}_{v}}(T,\omega )=\left\{ \begin{matrix} \inf \{k\ge {{T}_{v}}:{{\overline{X}}_{k}}=\overleftarrow{v}\}, & v\in T, \\ \infty ,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & v\notin T. \\ \end{matrix} \right. $

$\mathscr{B}(\mathscr{T}) \times \mathscr{T}$上定义概率测度如下

$ \bar P(A) = \int\limits_\mathscr{F} {{P_T}(A(T))dVGW(T)}, $

其中A∈$\mathscr{B}(\mathscr{T}) \times \mathscr{T}$, A (T)是截集。

为证结论1), 只需证明:对于VGW-a.s.T, {Xn, n≥0}是暂留的(关于PT),亦即,对VGW-a.s.T, {Xn, n≥0}在时间τ(T)之前以正概率访问了无穷多个T上的节点。

谬设P(τ < ∞)=1,此即对VGW-a.s.T, PT(τ(T) < ∞)=1。

n是满足(1)的正整数,n>1。给定树T,满足PT(τ(T) < ∞)=1。对于树T上第n层的任一节点v,若过程{ Xn(T), n≥0}于时刻τ(T)之前访问它, 则将之涂成白色,以Γ1记第n层全体白点的个数。对于k≥2,若T上(k-1)n层的白点依次标记为v1, v2, …, vj,以Vk, ivi,位于第kn层的白色后代的个数(vi位于第kn层的某后代被涂为白色当且仅当{ Xn(T), n≥0}于时刻Hvi之前访问它)。我们还假定T上其他层的节点绝不涂成白色。

由上述规则知道, kn层的白色节点的位于(k-1)n层的祖先一定是白色的(k≥2)。以Γk记第kn层全体白点的个数。于是

$ {\mathit{\Gamma }_{k + 1}} = \sum\limits_{j-1}^{_{{\mathit{\Gamma }_k}}} {{V_{k + 1, j}}, k \ge 0, } $

Γ0=1, Γ1T上第n层的白点个数。

上式定义的{Γk, k≥0}是$\mathscr{T}$×Ω上一个依赖于代的分枝过程。现在考虑Vk+1, j的均值(关于P)。设vT的根o的某一个孩子,即|v|=1,又设PT(Tv(T) < ∞)>0。由于PT(τ(T) < ∞)=1, 故

$ {P_T}({H_v}(T) < \infty |{T_v}(T) < \infty ) = 1. $

uv的位于树T上第n层的后代,且于Hv之前被{Xn(T), n≥0}访问过。记{Xn(T), n≥0}从vu的最短路径为u1u2un,其中ui+1ui的孩子,u1=v, un=u。我们称{Xn(T), n≥0}从ui有效下行至ui+1当且仅当在Hv之前{Xn(T), n≥0}从ui一步移至ui+1或从ui一步移至与ui+1同层的其他某节点w,然后沿w的后代逐步下移并于Hv之前再回到ui, 然后从ui一步移至ui+1, 类似地可以定义{Xn(T), n≥0}从ui有效上行至ui-1。将T上与ui+1同层的其他节点编号为: u1, …, udui-1。以p(ui, uj)记{Xn(T), n≥0}从ui出发沿uj之后代节点先向下移然后上移于Hv之前回到ui的概率。根据有偏随机游动的定义p(ui, uj)与uj无关, 而且{Xn(T), n≥0}位于ui时或者上行或者下行, 总之若记下行概率为pi,上行概率为qi,则

$ {p_i} + {q_i} = 1, $

$ {p_i} = \frac{1}{{\lambda + {d_{{u_i}}}}}(1 + ({d_{{u_i}}}-1)p({u_i}, {{\bar u}_j})), $
$ {q_i} = \frac{\lambda }{{\lambda + {d_{{u_i}}}}}(1 + ({d_{{u_i}}}-1)p({u_i}, {{\bar u}_j})), $

于是${p_i}=\frac{1}{{1 + \lambda }}$, ${q_i}=\frac{\lambda }{{1 + \lambda }}$

u0记根节点o, {Xn(T), n≥0}沿u0u1un移动可以看成一个广义的赌徒输光问题, 此时引理2.1所定义的{Sn, n≥0}从i移至i+1可看成{Xn(T), n≥0}从ui有效下行至ui+1, {Sn, n≥0}从i移至i-1可看成{Xn(T), n≥0}从ui有效上行至ui-1,而输光概率P(τ0>τn|S0=1)即是{Xn(T), n≥0}于Hv之前击中u的概率, 故由引理2.1知

PT[{Xn(T)}于Hv前击中u|Tv < ∞]=$\frac{1}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{n-1}}}}:{\eta _n}$.

以|Dn(T, v)|记v的位于T上第n层的全体后代个数, 则

EP(v在第n层的后代个数|Tv < ∞)=

$ \begin{array}{l} {E_{VGW}}(\left| {{D_n}(T, v) \cdot {\eta _n}} \right|) = \\ \frac{{{m_2} \cdots {m_n}}}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{n-1}}}}. \end{array} $

而根的后代至少有一个(以概率1), 且于τ之前被{Xn(T), n≥0}击中的至少有一个(以概率1), 故

$ {{E}_{{\bar{P}}}}\left( {{\mathit{\Gamma }}_{1}} \right)\ge \frac{{{m}_{2}}\cdots {{m}_{n}}}{1+{{\lambda }_{1}}+{{\lambda }_{1}}{{\lambda }_{2}}+\cdots +{{\lambda }_{1}}\cdots {{\lambda }_{n-1}}}. $ (4)

现在任取T上第(k-1)n层的一个节点v′(k≥2), 设P(Tv < ∞)>0。又任取vT上位于第kn层的一个后代u′。从v′到u′的最短路径为v1v2vn+1,其中vi+1vi的孩子,v1=v′, vn+1=u′。类似于前面的讨论, 我们得到: { Xn, n≥0}在Hv′之前击中u′的概率即是输光概率P(τ0 > τn+1|S0=1), 亦即$\frac{1}{{1 + \sum\limits_{l=1}^n {\prod\limits_{j=1}^l {{\lambda _{(k-1) n + j-1}}} } }}$,故v′位于T的第kn层在Hv′之前被击中的后代的总个数之期望(关于P)为

$ \frac{{{m}_{(k-1)n+1}}\cdots {{m}_{kn}}}{1+\sum\limits_{l=1}^{n}{\prod\limits_{j=1}^{l}{{{\lambda }_{\left( k-1 \right)n+j-1}}}}}, $ (5)

事实上, 这正是EP(Vk, j)。

现在根据1)可知,EP(Γ1)>1, EP(Vk, j)>1, ∀ k, ∀j.这说明过程{Γk, k≥0}是一个上临界的依赖于代的分枝过程, 因此

$ \bar P\left( {\mathop {\lim }\limits_{k \to \infty } {\mathit{\Gamma }_k} = \infty } \right) > 0, $ (6)

给定T,设B={{Xn(T), n≥0}在τ(T)之前访问了树T上的无穷多个节点}。根据式(6),存在$\mathscr{T}$的可测子集${\mathscr{T}_0}$使得VGW(${\mathscr{T}_0}$)>0且对每个TT0,总有

$ {{P}_{T}}(B)>0, $

此即P(τ=∞)>0,矛盾,1)得证。

其次证明2)。给定k≥2,对于第k层的任一节点v,事件{Tv < τ}发生,必然使得X1v之祖先且{Xn(T), n≥0}于τ之前击中v,根据前面的计算有

$ {P_T}({T_v} < \tau ) \le \frac{1}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{k-1}}}}, $

因此第k层于时刻τ之前被击中的节点数的期望(关于P)至多为

$ \frac{{{m_1} \cdots {m_2}}}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{k - 1}}}}. $

给定T,设L={Xn, n≥0}在τ(T)之前所抵达的最大层数,注意

$ {E_T}(L|\tau (T)) = \frac{1}{2}\tau (T), $

由于对VGW-a.s.T, |Dn(T)|≥1,故

$ {E_T}(L|\tau (T)) \le {E_T}(\{ {X_n}, n \ge 0\} 在\tau (T)前击中的节点数|\tau (T)), $

总之

$ \begin{array}{l} {E_{\bar p}}\left( \tau \right) \le 2{E_{\bar p}}(\{ {{\bar X}_n}, n \ge 0\} 在\tau 前击中的节点数)\\ \le 2{m_1} + 2\sum\limits_{k = 2}^\infty {\frac{1}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{k-1}}}}, } \end{array} $

由2)知EP(τ) < ∞,因此对VGW-a.s.T, ET(τ) < ∞,此即对VGW-a.s.T, {Xn, n≥0}在T上关于PT是正常返的。

最后证明3)。事实上要证3), 只需要证明对VGW-a.s.T, ET[τ(T)]=∞。根据第一部分的证明知:对于VGW-a.s.T,在τ之前第k层(k≥2)被{Xn, n≥0}击中的节点个数的期望(关于PT)是

$ \frac{{\left| {{D_k}(T)} \right|}}{{1 + \sum\nolimits_{l = 1}^{k-1} {(\prod\nolimits_{j = 1}^l {{\lambda _j}} )} }}, $

给定T,对每个ωτ(T, ω)大于或等于{Xn, n≥0}在τ(T, ω)之前于树T上击中的节点数,故

$ {E_T}(\tau (T)) \ge \sum\limits_{k = 2}^\infty {\frac{{\left| {{D_k}(T)} \right|}}{{1 + \sum\nolimits_{l = 1}^{k-1} {(\prod\nolimits_{j = 1}^l {{\lambda _j}} )} }}, } $

由3)知, 对VGW-a.s.T, ET(τ(T))=∞。因此随机游动{Xn, n≥0}在T上关于PT是零常返的。

注2.1   当${E_{VGW}}\left ({{{\left[{\frac{{{m_1} \cdots {m_n}}}{{\left| {{D_n}(T)} \right|}}} \right]}^2}} \right) \le C < \infty $, λn=mn+1, n≥1,而且对VGW-a.s.T,随机游动{Xn, n≥0}在T上是常返的, 则对于VGW-a.s.T, {Xn, n≥0}在T上有可能是零常返的。事实上, 对任意的0 < $\epsilon$ < 1,

$ \begin{align} & VGW(\left| {{D}_{k}}\left( T \right) \right|)\le \frac{{{m}_{1}}\cdots {{m}_{k}}}{{{k}^{\frac{1}{2}\left( 1+\epsilon \right)}}}\le \\ & \frac{1}{{{k}^{1+\epsilon}}}{{E}_{VGW}}{{\left[\frac{{{m}_{1}}\cdots {{m}_{k}}}{\left| {{D}_{k}}(T) \right|} \right]}^{2}}, \le \frac{C}{{{k}^{1+\epsilon}}}, \\ \end{align} $

由Borel-Cantelli引理可知, 对于VGW-a.s.T,当kk0=k0(T)时,$\left| {{D}_{k}}(T) \right|\ge \frac{{{m}_{1}}\cdots {{m}_{k}}}{{{k}^{\frac{1}{2}(1+\epsilon)}}}$, 故

$ \begin{align} & \sum\limits_{n=2}^{\infty }{\frac{\left| {{D}_{n}}(T) \right|}{1+\sum\nolimits_{l=1}^{n-1}{(\prod\nolimits_{j=1}^{l}{{{\lambda }_{j}}})}}}\ge \\ & K\sum\limits_{n=2}^{\infty }{\left( \frac{{{m}_{1}}\cdots {{m}_{n}}}{1+{{m}_{1}}+\cdots +{{m}_{1}}\cdots {{m}_{n-1}}}\cdot \frac{1}{{{n}^{\frac{1}{2}\left( 1+\epsilon \right)}}} \right),} \\ \end{align} $ (7)

其中K是依赖于T的正数。现在取${{m}_{n}}=\left (1+\frac{1}{n{{\left (\log \ n \right)}^{2}}} \right) m$, $\frac{3}{2}$m>1, 则m1mn-1mn-1lognn→∞,因此

$ \begin{align} & \sum\limits_{n=2}^{\infty }{\frac{\left| {{D}_{n}}\left( T \right) \right|}{1+\sum\nolimits_{l=1}^{n-1}{\left( \prod\nolimits_{j=1}^{l}{{{\lambda }_{j}}} \right)}}}\ge \\ & \tilde{K}\sum\limits_{n=2}^{\infty }{{{n}^{\frac{1}{2}\left( 1+\epsilon \right)}}},=\infty , \\ \end{align} $ (8)

上式中${\tilde{K}}$仅依赖于T,故由定理1.1之3)知此时随机游动{Xn, n≥0}在T上是零常返的(上述随机游动不满足1)、2), 构造是合理的)。

注2.2   考虑经典分枝树上的λn-有偏随机游动{Xn, n≥0},假设分枝树的平均生殖个数为m∈(1, $\frac{3}{2}$], ${{\lambda }_{n}}=(1+\frac{1}{n}) m$, ${{E}_{GW}}\left ({{\left[\frac{{{m}^{n}}}{\left| {{D}_{n}}(T) \right|} \right]}^{2}} \right)\le D < \infty $, ∀n≥1, 此时1)和2)均不满足, 因此在不会引起矛盾的情况下, 我们可以找到满足上述条件的λn-有偏随机游动{Xn, n≥0},对于G-W-a.s.T, 随机游动在T上是常返的, 进一步经过类似于式(7)和式(8)的计算, 可知{Xn, n≥0}是零常返的。

注2.3   根据注2.1和注2.2, 当λn=mn+1(n≥1)时或λnm时,可以考虑变化环境中分枝树上的中心极限定理。我们猜测有类似于文献[11]中的结论。

参考文献
[1] 威廉·费勒.概率论及其应用[M]. 3版.胡迪鹤译.北京:人民邮电出版社, 2006.
[2] Zeitouni O. Random walks in random environment, XXXI Summer school in probability, St Flour[J]. Lecture notes in Math , 2004, 1837 :193–312.
[3] Révész P. Random Walk in Random and Non-Random Environments[M]. 2nd ed. Hackensack and New York:World Scientific Publishing Co Pte Ltd, 2005.
[4] Wolfgang W. Random walk on infinite graphs and groups[M]. Cambridge: Cambridge University Press, 2000 .
[5] Polya G. Vber eine Anfgabe der Wahrscheinlichkeitsrechnung betref fend die Irrfahrt im Strassennetz[J]. Mathematische Annalen , 1921, 84 :149–160. DOI:10.1007/BF01458701
[6] Doyle P, Snell J L. Random walks and electric networks[J]. American Mathematical Monthly , 2000, 26 (4) :595–599.
[7] Lyons R. Random walks and percolation on trees[J]. Ann Probab , 1990, 18 :931–958. DOI:10.1214/aop/1176990730
[8] Peres Y, Zeitouni O. A central limit theorem for biased random walks on Galton-Watson trees[J]. Probab Theory Realated Fields , 2008, 140 (3/4) :595–629.
[9] Collevecchio A. On the Transience of processes defined on Galton-Watson trees[J]. Ann Probab , 2006, 34 :870–878. DOI:10.1214/009117905000000837
[10] Neveu J. Arbres et processus de Galton-Watson[J]. Ann Inst H Poincaré Probab Stastist , 1968, 22 :199–207.
[11] Lyons R, Peres Y. Probability on trees and networks[M]. Cambridge: Cambridge University Press, 2016 .