随机游走是概率论中的一个热点, 其在计算机等领域有着广泛的应用.简单随机游走定义如下^[1]:从一给定连通无向图$G=(V, E)$中的某一顶点出发的一随机过程, 其每一步独立等概率地选择其相邻的顶点.给定$G$上的一简单随机游走以及任意两顶点$u, v, $击中时$h(u, v)$表从$u$点出发第一次到达$v$点的平均时间.令$h_{\max}:=\max_{u, v}h(u, v)$.文献[2, 3]等研究了击中时、$h_{\max}$的诸多性质.关于随机游走的综述, 参见文献[1, 4].

近年来, 人们考虑了各种非简单随机游走, 比如贪婪随机游走^[5]、随机环境中的随机游走^{[6, 7]}等.本文考虑如下多重懒惰随机游走:令$G=(V, E)$表示有限连通无向图, 其中$ V =\{1, 2, \cdots, n\}$.假设在0时刻每个顶点$i\in V$上有一懒惰随机游走$\left\{S^{ (i)}_t\right\}_{t\geq0}$, 且所有从每个顶点出发的随机游走是相互独立的.设在$t$时刻$S^{ (i)}$处于顶点$v$, 即$S^{ (i)}_t=v$.则在$t+1$时刻此游走待在$v$的概率为$\frac{1}{d(v)+1}$, 跑向相邻顶点的概率为$\frac{1}{d (v)+1}$.其中$d(v)$表示$v$的度数.定义$\tau_{ij}:=\min\left\{t\geq 0: S^{(i)}_t=S^{(j)}_t\right\}.$一个自然且有意思的问题如下.

问题  考虑有限连通无向图上的多重懒惰随机游走, 经过多长时间每个随机游走与其他所有的随机游走相遇过?此时间与$h_{\max}$有什么关系?

对于圈而言, 本文证明了如下定理.

定理1.1  令$\mathbb{Z}_n=(V, E) $, 其中$V= \{1, \cdots, n \}$, $E=\{jk|j\equiv k\pm 1\ \mbox{mod}\ n\}$.考虑$\mathbb{Z}_n $上的多重懒惰随机游走, 则

$ \mathbb{E}(\max\limits_{i, j}\tau_{ij})=\Theta( h_{\max}\log n)=\Theta(n^2\log n). $

本文中记号说明如下$\mathbb{P}(\cdot)$及$\mathbb{E}(\cdot)$表示一个随机变量的概率、期望.设$f(n)>0, \ g(n)>0, $其中$n$属于自然数.记$f(n) = O(g(n)), $若存在一正常数$C$使得当$n$足够大时, $f(n)\leq Cg(n)$; $f(n) = o(g(n))$, 若$\lim\limits_{n\rightarrow \infty}f(n)/g(n)=0$; $f(n)=\Theta(g(n))$, 若$f(n) = O(g(n))$且$g(n) = O(f(n))$; $f(n)\sim g(n)$, 若$\lim\limits_{n\rightarrow \infty}f(n)/g(n)=1$.

为得到上界, 只需注意到如下事实(见文献[3, 性质1]).对所有可逆马氏链存在一正常数$K$使得$\label{maxmeetingtime} \max_{ij}\mathbb{E}(\tau_{ij})\leq K h_{\max}.$现开始给出其上界.事实上, 对任意两顶点$i, j\in \mathbb{Z}_n$,

$ \begin{eqnarray*} \mathbb{P}(\tau_{ij}>ms\vert \tau_{ij}>(m-1)s) \leq \max\limits_{ij} \mathbb{P}(\tau_{ij}>s) \leq \frac{\max\limits_{i, j}\mathbb{E}(\tau_{ij})}{s}\leq\frac{Kh_{\max}}{s}. \end{eqnarray*} $

于是$\mathbb{P}(\tau_{ij}>ms)\leq (\frac{Kh_{\max}}{s})^m$.因此对某一常数$C_1>\frac{K}{2}$,

$ \begin{eqnarray} \label{upperbound} \mathbb{P}(\tau_{ij}> 2C_1 \lfloor\log n\rfloor h_{\max}) \leq (\frac{Kh_{\max}}{ 2C_1 h_{\max} } )^{\lfloor \log n\rfloor }. \end{eqnarray} $

(2.1)

此处对实数$x, $ $\lfloor x\rfloor$表小于等于$x$的最大整数.故对任意常数$t>K$,

$ \begin{eqnarray*} \mathbb{P}(\max\limits_{i, j}\tau_{ij}>t\cdot h_{\max}\log n) &=&\mathbb{P}(\exists i, j\ \mbox{使得}\ \tau_{ij}>t\cdot h_{\max}\log n)\\ &\leq&n^2\mathbb{P}(\tau_{ij}>t\cdot h_{\max}\lfloor \log n\rfloor)\\ &\leq& n^2\mathbb{P}(\tau_{1\lfloor n/2\rfloor}>t\cdot h_{\max}\lfloor \log n \rfloor) \leq n^2(\frac{K}{t})^{\lfloor \log n\rfloor}. \end{eqnarray*} $

设$Y=\frac{\max_{i, j}\tau_{ij}}{ h_{\max}\log n}$.则

$ \begin{eqnarray*} \frac{\mathbb{E}(\max\limits_{i, j}\tau_{ij})}{ h_{\max}\log n}&=& \mathbb{E}(Y)=\int_{0}^\infty \mathbb{P}(Y>t)dt\leq \int_{0}^{9K}\mathbb{P}(Y>t)dt +\int_{9K}^\infty \mathbb{P}(Y>t)dt\\ &\leq& O(1)+\int_{9K}^\infty n^2(\frac{K}{t})^{\lfloor \log n\rfloor}dt= O(1). \end{eqnarray*} $

注  此上界对所有有限连通图上的多重懒惰随机游走的最大相遇时都成立.

设$\left\{X_t \right\}_{t\geq0}$表从0点出发分布为$\mu$的一随机游走, 其中$\mu(0)=3/9, \ \mu(1)=\mu(-1)=2/9, \ \mu(2)=\mu(-2)=1/9$以及$k\neq0, \pm1, \pm2$, $\mu(k)=0$.对于给定区间$(-\frac{n}{2}+1, \frac{n}{2}-1)$定义其逃离时间

$ \sigma:=\min\left\{t: X_t \not\in(-\frac{n}{2}+1, \frac{n}{2}-1)\right\}. $

为简单记, 称顺时针方向为正, 且将顶点从1开始按照递增顺序沿顺时针在圈上标记.对任意的$i < j, $令$H^{(ij)}_t=\widehat{S}^{(j)}_t-\widehat{S}^{(i)}_t, $其中$\widehat{S}^{(i)}_t$ (相应地$\widehat{S}^{(j)}_t$)表示从顶点$i$ (相应地$j$)出发的随机游走在$t$时刻所处的顶点之间的顺时针``图距离".注意此处所说的``图距离"可正可负, 其依赖$S^{(i)}_t$所处的位置.则当$ j-i \leq \frac{n}{2} $时$H^{(ij)}_0=j-i$; 当$ j-i > \frac{n}{2} $时$H^{(ij)}_0=-(n-(j-i))$.易知$ H^{(ij)}_{t+1}-H^{(ij)}_{t}$的分布为$\mu$.而$\mu$是对称的, 所以

$ \tau_{ij}=\min \left\{t>0: H_t^{ij}=0 \right\}=\min \left\{t>0:X_{t}=j-i\ \mbox{或}\ X_{t}=-(n-(j-i)) \right\}. $

显然, $\sigma$小于等于$\tau_{1 \lfloor n/2\rfloor}.$因此

$ \begin{eqnarray*} \mathbb{E}(\max\limits_{i, j}\tau_{ij})\geq\mathbb{E}(\max\limits_{1\leq\ell\leq \lfloor n/2\rfloor}\tau^{(\ell)}) \geq\mathbb{E}(\max\limits_{1\leq\ell\leq \lfloor n/2\rfloor}\sigma^{(\ell)}), \end{eqnarray*} $

此处诸$\tau^{(\ell)}$以及$\sigma^{(\ell)}$分别是$\tau_{1\lfloor n/2\rfloor}$和$\sigma$的独立拷贝; 第一个不等式是由于在圈上有$\lfloor n/2\rfloor$对顶点它们的距离为$\lfloor n/2\rfloor$.

为得到下界首先证明存在一服从几何分布的随机变量$\eta$使得$ \eta\preceq$ $\sigma$¹ (见引理2.1);然后由如下引理2.2可得

¹定义:令$X$, $Y$为$\mathbb{R}^1$上的两随机变量.记$X\preceq Y$, 若对任意$x\in \mathbb{R}^1$, 有$\mathbb{P}(X\leq x)\geq \mathbb{P}(Y\leq x)$.众知, 若$X\preceq Y$, 则存在一耦合$(X, Y)$使得$X\leq Y$ a.s..

$ \begin{eqnarray*} \mathbb{E}(\max\limits_{i, j}\tau_{ij}) &\geq&\mathbb{E}(\max\limits_{1\leq\ell\leq n/2}\sigma^{(\ell)}) \geq\mathbb{E}(\max\limits_{1\leq\ell\leq n/2}\eta^{(\ell)})\\ &\approx& \mathbb{E}(\eta) \log n= C_1n^2\log n=\Theta( h_{\max}\log n), \end{eqnarray*} $

其中诸$\eta^{(\ell)}$是$\eta$的独立拷贝.因此只需要证明如下引理2.1-2.2.

为找到这样的$\eta, $首先描述下直觉.由文献[8, p.254], 可知当$i$非常大时,

$ \begin{eqnarray*} \mathbb{P}(\frac{\tau_{1\lfloor \frac{n}{2}\rfloor}}{n^2}>i)\sim \mathbb{P}(\max\limits_{0 < t\leq i n^2}\vert B_t\vert < \frac{n}{2})\sim \mathbb{P}(\max\limits_{0 < t\leq 1}\vert B_t\vert < \frac{1}{2\sqrt{i}})\sim e^{-Ci}, \end{eqnarray*} $

此处$B_t$表一从原点出发的标准Brown运动.

引理2.1  存在一参数为$11n^{-2}$的几何分布$\eta$使得$\eta\preceq\sigma.$

证  令$\phi(\lambda)=\log \hat{\mu}(\lambda), $其中$\hat{\mu}(\lambda)$为$\mu$的Laplace变换.设$M_t:=\exp(\lambda X_t-\phi(\lambda)t).$易知

$ \begin{eqnarray*} \mathbb{E}\left[M_{t+1}\vert {\cal F}_t\right] &=&\mathbb{E}\left[\exp(\lambda X_{t+1}-\lambda X_t+(\lambda X_t-\phi(\lambda)t)-\phi(\lambda))\vert M_t\right]\\ &=& \exp(\lambda X_t-\phi(\lambda)t))\times e^{-\phi(\lambda)}\times \mathbb{E}(\exp(\lambda(X_{t+1}-X_t)\vert M_t)\\ &=&M_t \frac{\mathbb{E}(\exp(\lambda(X_{t+1}-X_t)\vert M_t)}{\hat{\mu}(\lambda)}=M_t. \end{eqnarray*} $

由停时定理有$\mathbb{E}(\exp(\lambda X_\sigma-\phi(\lambda)\sigma))=1.$注意到$X_\sigma$取值于$\left\{\pm\frac{n}{2}, \pm(\frac{n}{2}-1)\right\}$且此随机游走是对称的.因此

$ \begin{eqnarray*} 1&=&\mathbb{E}[\exp(\lambda X_\sigma-\phi(\lambda)\sigma)\vert X_t\ \mbox{左边逃离}]\times \mathbb{P}~(X_t \ \mbox{左边逃离})\\ &&+\mathbb{E}[\exp(\lambda X_\sigma-\phi(\lambda)\sigma)\vert X_t\ \mbox{右边逃离}]\times \mathbb{P}~(X_t \ \mbox{右边逃离})\\ &\geq& e^{\lambda (n-1)/2}\mathbb{E}[\exp(-\phi(\lambda)\sigma)\vert X_t\ \mbox{左边逃离}]\times \mathbb{P}~(X_t \ \mbox{左边逃离})\\ &&+e^{-\lambda n/2}\mathbb{E}[\exp(-\phi(\lambda)\sigma)\vert X_t\ \mbox{右边逃离}]\times \mathbb{P}~(X_t \ \mbox{右边逃离})\\ &\geq&\frac{1}{2}(e^{\lambda (n-1)/2}+e^{-\lambda (n-1)/2})\mathbb{E}(e^{-\phi(\lambda)\sigma)}). \end{eqnarray*} $

也就是说

$ \begin{eqnarray*} \mathbb{E}(e^{-\phi(\lambda)\sigma})\leq \frac{2}{e^{\lambda (n-1)/2}+e^{-\lambda (n-1)/2}}= \frac{1}{\cosh (\lambda (n-1)/2)}. \end{eqnarray*} $

另一方面, 设$p=11n^{-2}$, $\hat{\eta}$为一参数为$p$的几何分布.注意到$\phi(\lambda)=\log (\frac{3+4\cosh(\lambda)+2\cosh(2\lambda)}{9})$.则

$ \begin{eqnarray*} \mathbb{E}(e^{-\phi(\lambda)\hat{\eta}}) &=&\sum\limits_{k=1}^\infty e^{-\phi(\lambda)k}{(1-p)^{k-1}p} =\frac{pe^{-\phi(\lambda)}}{1-(1-p)e^{-\phi(\lambda)}}\\ &=&\frac{9p}{3+4\cosh(\lambda)+2\cosh(2\lambda)-9(1-p)}\\ &\geq&\frac{9p}{3+6\cosh(2\lambda)-9(1-p)}\\ &=&\frac{1}{1+\frac{2n^2}{33}(\cosh (2\lambda)-1)}. \end{eqnarray*} $

进一步的, 对任意$x, y>0$,

$ \sinh(x+y)=\sinh(x)\cosh(y)+\cosh(x)\sinh(y)\geq \sinh(x)+\sinh(y), $

有

$ \begin{eqnarray*} \cosh(\lambda(\frac{n-1}{2}))-1= \sinh^2(\lambda(\frac{n-1}{4})) \geq(\frac{n-1}{4})^2\sinh^2(\lambda)\geq \frac{2n^2}{33}\sinh^2(\lambda). \end{eqnarray*} $

因此对任意的$\lambda>0$, $\mathbb{E}\left[e^{-\phi(\lambda)\sigma}\right]\leq \mathbb{E}\left[e^{-\phi(\lambda)\hat{\eta}}\right].$故由耦合方法可找到一个与$\hat{\eta}$具有相同分布的几何随机变量$\eta$使得$\eta\preceq\sigma.$

设$\alpha=-\log (1-p)=-\log (1-11n^{-2})(\thickapprox 11n^{-2}), $ $\gamma$为一服从参数为$\alpha$的指数分布的随机变量.则易知$\lceil \gamma\rceil$与$\eta$具有相同的分布.此处对实数$x, $ $\lceil x\rceil$表大于等于$x$的最小整数.令$\gamma_1, \gamma_2, \cdots, \gamma_n$为$\gamma$的$n$个独立拷贝.至此只需如下引理.

引理2.2  设$\gamma, \gamma_1, \cdots, \gamma_n$为一族独立同分布服从参数为$\alpha$的指数分布的随机变量, 则

$ \mathbb{E}(\max\limits_{1\leq i\leq n}\gamma_i)=\mathbb{E}(\gamma)(1+\frac{1}{2}+\cdots+\frac{1}{n}). $

证  事实上, 由指数分布的无记忆性可得

$ \begin{eqnarray*} &&\mathbb{P}(\left.\max\limits_{1\leq i\leq n}\gamma_i-\max\limits_{1\leq i\leq n-1}\gamma_i>x \right\vert\max\limits_{1\leq i\leq n}\gamma_i=\gamma_n)\\ &=&\mathbb{P}(\left.\gamma_n>x+\max\limits_{1\leq i\leq n-1}\gamma_i\right\vert \gamma_n>\max\limits_{1\leq i\leq n-1}\gamma_i)=\mathbb{P}(\gamma_n>x). \end{eqnarray*} $

因此

$ \begin{eqnarray*} \mathbb{E}\left[\left.\max\limits_{1\leq i\leq n}\gamma_i-\max\limits_{1\leq i\leq n-1}\gamma_i\right\vert\max\limits_{1\leq i\leq n}\gamma_i=\gamma_n\right]=\mathbb{E}(\gamma). \end{eqnarray*} $

注意到

$ \begin{eqnarray*} \mathbb{E}\left[\left.\max\limits_{1\leq i\leq n}\gamma_i-\max\limits_{1\leq i\leq n-1}\gamma_i\right\vert\max\limits_{1\leq i\leq n}\gamma_i\neq\gamma_n\right]=0, \end{eqnarray*} $

有

$ \begin{eqnarray*} \mathbb{E}\left[\max\limits_{1\leq i\leq n}\gamma_i-\max\limits_{1\leq i\leq n-1}\gamma_i \right] &=&\mathbb{E}\left[\left.\max\limits_{1\leq i\leq n}\gamma_i -\max\limits_{1\leq i\leq n-1}\gamma_i\right\vert\max\limits_{1\leq i\leq n}\gamma_i =\gamma_n\right]\mathbb{P}(\max\limits_{1\leq i\leq n}\gamma_i=\gamma_n)\\ &=&\mathbb{E}(\gamma)\frac{(n-1)!}{n!}=\frac{\mathbb{E}(\gamma)}{n}. \end{eqnarray*} $

故

$ \begin{eqnarray*} \mathbb{E}\left[\max\limits_{1\leq i\leq n}\gamma_i\right] =\mathbb{E}\left[\max\limits_{1\leq i\leq n-1}\gamma_i \right]+\frac{\mathbb{E}(\gamma)}{n}= \cdots=\mathbb{E}(\gamma)(1+\frac{1}{2}+\cdots+\frac{1}{n}). \end{eqnarray*} $

在此章节中, 将证明若$ n$个顶点上的有限连通无向图$G$中存在$n^a$对$u_iv_j$ ($0 < a < 1$)使得$H(u_iv_j)=\Omega(h_{\max}), $则$\mathbb{E}(\max_{ij} \tau_{ij})=\Omega(h_{\max}\log n)$, 其中$ h_{\max}$为此图上的一简单随机游走的最大击中时.

引理3.1   (见文献[9, 引理2.9])设$X$为取值于自然数$\mathbb{N}$的一随机变量使得对任意的$\lambda, t\in \mathbb{N}, $ $\mathbb{P}(X\geq\lambda t)\leq [\mathbb{P}(X\geq t)]^{\lambda}, $则

(1) 对任意满足$\mathbb{P}(X\geq t) < 1$的$t\in \mathbb{N}, $ $\mathbb{E}(X)\leq \frac{t}{1-\mathbb{P}(X\geq t)}, $

(2) 对任意使得$\epsilon \mathbb{E}(X)$为一整数的$0 < \epsilon\leq 1, $ $\mathbb{P}(X\geq \epsilon \mathbb{E}(X))\geq 1-\epsilon.$

引理3.2  给定任意连通图$G, $若存在$n^a\ (0 < a < 1)$个顶点对$u_iv_i$使得击中时$H(u_iv_i)=\Omega(h_{\max}), $则$\mathbb{E}(\max_{ij} \tau_{ij})=\Omega(h_{\max}\log n).$

证  设$u$, $v$是满足$H(u, v)=\Theta(h_{\max})$的一对顶点.对$\epsilon^\prime < 2a$, 令$A_{uv}$表在$(1-e^{-1/2})h_{\max}(\epsilon^\prime \log n)$时刻之前随机游走$S^{ {(u)}}_t$和$S^{{(v)}}_t$没有相遇.注意到式(2.1)以及存在某常数$K>1$, $\max_{ij}\mathbb{E}(\tau_{ij})\leq K h_{\max}$.因此由引理3.1, 知

$ \mathbb{P}(\tau_{uv}>(1-e^{-1/2}) \mathbb{E}(\tau_{uv}))>e^{-1/2}. $

这意味着

$ \mathbb{P}(A_{uv})=\mathbb{P}(\tau_{uv}>(1-e^{-1/2}) \mathbb{E}(\tau_{uv})(\epsilon^\prime\log n)) >(e^{-1/2})^{\epsilon^\prime\log n}=n^{-\frac{\epsilon^\prime}{2}}. $

选择$n^a$对这样的顶点, 记为$(i_1, j_1), \cdots, $ $(i_{n^a}, j_{n^a}), $则对任意$0 < \epsilon^\prime < 2a, $

$ \begin{eqnarray*} &&\mathbb{P}(\max\limits_{ij} \tau_{ij}\geq (1-e^{-1/2})h_{\max}(\epsilon^\prime\log n))\\ &\geq&\mathbb{P}(\max\limits_{ij} \tau_{ij}\geq (1-e^{-1/2}) \frac{\mathbb{E}(\tau_{uv})}{K}(\epsilon^\prime\log n))\\ &=&1-\mathbb{P}(\forall {i, j}, \tau_{ ij}\leq(1-e^{-1/2}) \frac{\mathbb{E}(\tau_{uv})}{K}(\epsilon^\prime\log n))\\ &\geq& 1-\mathbb{P}(\ \mbox{对所有的顶点对}\ ({i_k, j_k}, \tau_{i_kj_k}\leq (1-e^{-1/2}) \frac{\mathbb{E}(\tau_{uv})}{K}(\epsilon^\prime\log n))\\ &\geq& 1- \mathbb{P}(\cap A_{ i_kj_k}^c) \geq 1-(1-n^{-\epsilon^\prime/2})^{n^a}\\ &\geq& 1-\exp\left\{-n^{a-\epsilon^\prime/2}\right\}>\frac{1}{2}. \end{eqnarray*} $

因此

$ \begin{eqnarray*} \mathbb{E}(\max\limits_{ij} \tau_{ij}) >\frac{1}{2}(1-e^{-1/2})h_{\max}(\epsilon^\prime\log n)=\Omega(h_{\max}\log n). \end{eqnarray*} $

易找出反例, 当图$G=(V, E)$中顶点的度不是一致有界时(即度与顶点数$n$有关), $\mathbb{E}(\max_{i, j}\tau_{ij})\neq\Theta( h_{\max}\log n)$.例如$n$个顶点上的星图.为此有如下猜想.

问题  考虑$n$个顶点上的有限连通无向图上的多重懒惰随机游走, 当其度一致有界时, $\mathbb{E}(\max_{i, j}\tau_{ij})=\Theta( h_{\max}\log n), $其中$h_{\max}$为此图上的简单随机游走的最大击中时.