张志洋, 胡晓予
中国科学院大学数学科学学院, 北京 100049
2015年12月30日 收稿; 2016年05月20日 收修改稿
基金项目: 国家自然科学基金（11171342）资助
通信作者: 胡晓予, E-mail:xyhu@ucas.ac.cn

摘要: 考虑变化环境中分枝树上的广义有偏随机游动，分别得到随机游动为暂留的、正常返的和零常返的充分条件，为进一步研究这类随机游动的中心极限定理等性质做了铺垫。
关键词: 树上随机游动变化环境中分枝过程常返性暂留性
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 treebranching process in the varying environmentrecurrencetransience
随机游动是随机过程中的一个经典模型。早在概率论发展初期，就有人曾经考虑过直线上的简单随机游动和有偏随机游动等问题^[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}^*$。若存在正常数c₁和c₂>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为由如下形式的有限正整数序列所构成的集合: < i₁, i₂, …, i_n > , 其中i_k∈$\mathbb{N}^*$, 1≤k≤n, n∈$\mathbb{N}$(当n=0时，表示空序列)。对于任一个U的子集T，若它满足如下条件:
(a)空序列?∈T;
(b)若对某个j∈N^*, < i₁, i₂, …, i_k, j > ∈T，则必有 < i₁, …, i_k > ∈T;
(c)若u= < i₁, i₂, …, i_k > ∈T, ν_u(T)是依赖于u和T的某正整数(也称ν_u(T)为T上节点u的分枝数)，则对于所有的1≤j≤ν_u(T)，总有 < i₁, i₂, …, i_k，j > ∈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，称 < i₁, i₂, …, i_n > ∈T为T的顶点，以v记之。设u, v为T上的2个顶点，若存在i₁, i₂, …, i_n和j使v= < i₁, i₂, …, i_n > , u= < i₁, i₂, …, i_n, j > ，则称v为u的父亲，记为$v=\overleftarrow u $；或称u为v的儿子，也可记为$u=\overrightarrow v $。记顶点v的儿子个数为d_v(T)(或d_v)；记顶点v的第n代子孙的全体为D_n(T, v)(或D_n(v))；根o的第n代子孙的全体记为D_n(T)；以|D_n(T)|记第n代子孙的个数；记v为顶点v∈T到T的根o的距离，即从根o到v最短路径上边的总数，有时也称节点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过程和分枝树)令Z₀=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.$

其中{X_{n, j}, n≥0, j≥1}为独立同分布的随机变量序列，其共同分布为{p(j), j≥0}, {Z_n: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个非负整数k_j, 1≤j≤n，再取n个任意的顶点v₁, v₂, …, v_n, 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决定的期望记为E_GW。
类似地，可以定义变化环境中的分枝过程，以及变化环境中的分枝树。
定义1.4 ??令Y₀=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.$

其中{U_{n, j}:n≥1, j≥1}是相互独立的随机变量序列，对任意给定的n≥1, {U_{n, j}:j≥1}有相同的概率分布{p⁽ⁿ⁾(j), j∈$\mathbb{N}$}，称{Y_n:n≥0}为变化环境中的分枝过程，记${m_n}=\sum\nolimits_{j=1}^\infty {j{p^{(n)}}\left (j \right)} $。当m_n>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个非负整数k_j, 1≤j≤n，再取n个任意的顶点分别记为v₁, v₂, …, v_n，令

$\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}, 设{X_n: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, v∈T, λ为正常数, 我们称{X_n:n≥0}为GW树T上的λ-有偏随机游动。
类似地，可以定义变化环境中分枝树上的{λ_n, n≥1}-有偏随机游动如下。
定义1.7 ??给定一棵上临界的变化环境中的分枝树T，其后代分布律为{p⁽ⁿ⁾(j), n≥1, j≥0}，又给定一列正实数{λ_l, l≥1}，若{V_n: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，对任意的u∈T, |u|=l, d_u的分布律为{p^(l+1)(k), k≥0}，我们称{V_n:n≥0}为变化环境中分枝树T上的{λ_n, n≥1}-有偏随机游动。
根据Lyons^[7]关于树上有偏随机游动状态分类的结论可得
对于一个个体平均生殖个数为m>1的G-W树上的λ-有偏随机游动{X_n:n≥0}而言：当λ>m时，对几乎所有的GW-树T，λ-有偏随机游动{X_n:n≥0}是正常返的；当λ=m时，对几乎所有的GW-树T, λ-有偏随机游动{X_n:n≥0}是零常返的；当λ < m时，对几乎所有的GW-树T, λ-有偏随机游动{X_n:n≥0}是暂留的。
关于变化环境中分枝树上的{λ_n, n≥1}-有偏随机游动，我们的主要结果如下：
定理1.1 ??设{Y_n, n≥0}是一个上临界的变化环境中的分枝过程，设{m_n, n≥1}如前所定义。给定一列实数λ_n>0(n≥1)及一棵由{Y_n, n≥0}决定的分枝树T，{X_n, n≥0}是取值于T的{λ_n, n≥1}-有偏随机游动，则有如下结论：
1)若{λ_n, n≥1}与{m_n, 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})$, P_T({X_n, n≥0}不返回根节点)>0;
2)若{λ_n, n≥1}与{m_n, 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，随机游动{X_n, n≥0}是正常返的(关于P_T);
3)若对VGW-a.s.T，随机游动{X_n, n≥0}关于P_T是常返的，而且

$\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，随机游动{X_n, n≥0}是零常返的(关于P_T)。
2 主要定理的证明命题2.1 ??VGW可唯一扩张为${\rm{\mathscr{B}(\mathscr{T})}}$上的一个概率测度。
证明 ??考虑乘积空间${\mathscr{T}^*}$=${\mathbb{N}^U}$，其中U如定义1.1设，现在任取u∈U, |u|=n, 记q^(u)={p⁽ⁿ⁺¹⁾(j):j=0, 1, …}, 对任意的u₁, u₂, …, u_n∈U, |u_i|=k_i, 1≤i≤n，存在唯一一个${\mathbb{N}^{*n}}$上的乘积测度×_i=1ⁿq^(u_i)，使得对${\mathbb{N}^{*n}}$中任意一个单点集{ < i₁, …, i_n > }有

$\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=1ⁿq^(u_i)的测度满足Kolmogrov相容性条件。
给定u∈U，设$v_u^*:{\mathscr{F}^*} \to \mathbb{N}$。定义ψ:${\mathscr{T}^*} \to \mathscr{T}$如下: ψ(ω^*)=T，其中树T上的每个节点u= < j₁, …, j_p>, p∈$\mathbb{N}$满足

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

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

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

则变化环境中的分枝树关于上述测度VGW几乎必然不是有限树。本文中将概率测度VGW决定的数学期望记为E_VGW。
受文献[9]中方法的启发，我们用变化环境中的分枝树的生殖规律与有偏随机游动的有偏参数的性质讨论状态分类。沿用文献[11]中使用的测度定义体系, 严格给出了状态分类定理的证明。
为证明定理1.1，首先需要下面一个引理。因为我们没有在文献中找到这一结果的证明，所以将详细的证明陈述如下。
引理2.1 ??设{S_t:t≥0}是取值于$\mathbb{N}$上的时齐马氏链, 给定0 < p_t < 1, t≥1, S_t转移概率如下:

$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, $

特别地, 当p_n=q_n=1/2(其中n≥1)时, p(τ₀>τ_n+1|S₀=1)=1/(n+1)，p_n≡p, q_n≡q=1-p, p≠q时，这就是一个经典的赌徒输光问题，$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⁽⁰⁾=τ_i。
记a_k=P(τ₀>τ_n+1|S₀=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 < k≤n，有

$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, {X_n(T), n≥0}是T上的{λ_n}-有偏随机游动(关于P_T)。定义

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

其中o是T的根，对于v≠o定义

${{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, {X_n, n≥0}是暂留的(关于P_T)，亦即，对VGW-a.s.T, {X_n, n≥0}在时间τ(T)之前以正概率访问了无穷多个T上的节点。
谬设P(τ < ∞)=1，此即对VGW-a.s.T, P_T(τ(T) < ∞)=1。
设n是满足(1)的正整数，n>1。给定树T，满足P_T(τ(T) < ∞)=1。对于树T上第n层的任一节点v，若过程{ X_n(T), n≥0}于时刻τ(T)之前访问它, 则将之涂成白色，以Γ₁记第n层全体白点的个数。对于k≥2，若T上(k-1)n层的白点依次标记为v₁, v₂, …, v_j，以V_{k, i}记v_i，位于第kn层的白色后代的个数(v_i位于第kn层的某后代被涂为白色当且仅当{ X_n(T), n≥0}于时刻H_vi之前访问它)。我们还假定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, } $

Γ₀=1, Γ₁是T上第n层的白点个数。
上式定义的{Γ_k, k≥0}是$\mathscr{T}$×Ω上一个依赖于代的分枝过程。现在考虑V_{k+1, j}的均值(关于P)。设v是T的根o的某一个孩子，即|v|=1，又设P_T(T_v(T) < ∞)>0。由于P_T(τ(T) < ∞)=1, 故

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

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

${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 }}$。
以u₀记根节点o, {X_n(T), n≥0}沿u₀u₁…u_n移动可以看成一个广义的赌徒输光问题, 此时引理2.1所定义的{S_n, n≥0}从i移至i+1可看成{X_n(T), n≥0}从u_i有效下行至u_i+1, {S_n, n≥0}从i移至i-1可看成{X_n(T), n≥0}从u_i有效上行至u_i-1，而输光概率P(τ₀>τ_n|S₀=1)即是{X_n(T), n≥0}于H_v之前击中u的概率, 故由引理2.1知
P_T[{X_n(T)}于H_v前击中u|T_v < ∞]=$\frac{1}{{1 + {\lambda _1} + {\lambda _1}{\lambda _2} + \cdots + {\lambda _1} \cdots {\lambda _{n-1}}}}:{\eta _n}$.
以|D_n(T, v)|记v的位于T上第n层的全体后代个数, 则
E_P(v在第n层的后代个数|T_v < ∞)=

$\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), 且于τ之前被{X_n(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(T_v < ∞)>0。又任取v在T上位于第kn层的一个后代u′。从v′到u′的最短路径为v₁v₂…v_n+1，其中v_i+1是v_i的孩子，v₁=v′, v_n+1=u′。类似于前面的讨论, 我们得到: { X_n, n≥0}在H_v′之前击中u′的概率即是输光概率P(τ₀ > τ_n+1|S₀=1), 亦即$\frac{1}{{1 + \sum\limits_{l=1}^n {\prod\limits_{j=1}^l {{\lambda _{(k-1) n + j-1}}} } }}$，故v′位于T的第kn层在H_v′之前被击中的后代的总个数之期望(关于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)

事实上, 这正是E_P(V_{k, j})。
现在根据1)可知，E_P(Γ₁)>1, E_P(V_{k, 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={{X_n(T), n≥0}在τ(T)之前访问了树T上的无穷多个节点}。根据式(6)，存在$\mathscr{T}$的可测子集${\mathscr{T}_0}$使得VGW(${\mathscr{T}_0}$)>0且对每个T∈T₀，总有

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

此即P(τ=∞)>0，矛盾，1)得证。
其次证明2)。给定k≥2，对于第k层的任一节点v，事件{T_v < τ}发生，必然使得X₁为v之祖先且{X_n(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={X_n, n≥0}在τ(T)之前所抵达的最大层数，注意

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

由于对VGW-a.s.T, |D_n(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)知E_P(τ) < ∞，因此对VGW-a.s.T, E_T(τ) < ∞，此即对VGW-a.s.T, {X_n, n≥0}在T上关于P_T是正常返的。
最后证明3)。事实上要证3), 只需要证明对VGW-a.s.T, E_T[τ(T)]=∞。根据第一部分的证明知:对于VGW-a.s.T，在τ之前第k层(k≥2)被{X_n, n≥0}击中的节点个数的期望(关于P_T)是

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

给定T，对每个ω，τ(T, ω)大于或等于{X_n, 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, E_T(τ(T))=∞。因此随机游动{X_n, n≥0}在T上关于P_T是零常返的。
注2.1 ??当${E_{VGW}}\left ({{{\left[{\frac{{{m_1} \cdots {m_n}}}{{\left| {{D_n}(T)} \right|}}} \right]}^2}} \right) \le C < \infty $, λ_n=m_n+1, n≥1，而且对VGW-a.s.T，随机游动{X_n, n≥0}在T上是常返的, 则对于VGW-a.s.T, {X_n, 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，当k≥k₀=k₀(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, 则m₁…m_n-1≈m^n-1logn，n→∞，因此

$\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)知此时随机游动{X_n, n≥0}在T上是零常返的(上述随机游动不满足1)、2), 构造是合理的)。
注2.2 ??考虑经典分枝树上的λ_n-有偏随机游动{X_n, 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-有偏随机游动{X_n, n≥0}，对于G-W-a.s.T, 随机游动在T上是常返的, 进一步经过类似于式(7)和式(8)的计算, 可知{X_n, n≥0}是零常返的。
注2.3 ??根据注2.1和注2.2, 当λ_n=m_n+1(n≥1)时或λ_n↓m时，可以考虑变化环境中分枝树上的中心极限定理。我们猜测有类似于文献[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.