圈上的多重懒惰随机游走

王彬

(桂林理工大学理学院,广西桂林541004)

圈上的多重懒惰随机游走

王彬

(桂林理工大学理学院,广西桂林541004)

本文考虑了n个定点的圈上的多重懒惰随机游走.利用偶和方法证明了其最大相遇时的期望的阶数为hmax×logn,其中hmax为圈上的一简单随机游走的最大击中时.

多重懒惰随机游走;相遇时;击中时

1 引言及主要结果

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

近年来,人们考虑了各种非简单随机游走,比如贪婪随机游走[5]、随机环境中的随机游走[6,7]等.本文考虑如下多重懒惰随机游走：令G=(V,E)表示有n限连通o无向图,其中V={1,2,···,n}.假设在0时刻每个顶点i∈V上有一懒惰随机游走且所有从

每个顶点出发的随机游走是相互独立的.设在t时刻S(i)处于顶点v,即=v.则在t+1时刻此游走待在n的概率为跑向相邻顶点的概率为.其中d(v)表示v的度数.定义：=min一个自然且有意思的问题如下.

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

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

定理1.1令Zn=(V,E),其中V={1,···,n},E={jk|j≡k±1 mod n}.考虑Zn上的多重懒惰随机游走,则

本文中记号说明如下P(·)及E(·)表示一个随机变量的概率、期望.设f(n)＞0,g(n)＞0,其中n属于自然数.记f(n)=O(g(n)),若存在一正常数C使得当n足够大时,f(n)≤Cg(n);f(n)=o(g(n)),若f(n)/g(n)=0;f(n)=Θ(g(n)),若f(n)=O(g(n))且g(n)=O(f(n));f(n)～g(n),若f(n)/g(n)=1.

2 证明

2.1 上界

为得到上界,只需注意到如下事实(见文献[3,性质1]).对所有可逆马氏链存在一正常数K使得maxijE(τij)≤Khmax.现开始给出其上界.事实上,对任意两顶点i,j∈Zn,

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

2.2 下界

显然,σ小于等于τ1[n/2].因此

为得到下界首先证明存在一服从几何分布的随机变量η使得η≾σ1(见引理2.1);然后由如下引理2.2可得

其中诸η(ℓ)是η的独立拷贝.因此只需要证明如下引理2.1-2.2.

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

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

引理2.1存在一参数为11n-2的几何分布η使得η≾σ.

证令φ(λ)=logˆµ(λ),其中ˆµ(λ)为µ的Laplace变换.设Mt：=exp(λXt-φ(λ)t).易知

由停时定理有E(exp(λXσ-φ(λ)σ))=1.注意到Xσ取值于且此随机游走是对称的.因此

也就是说

1定义：令X,Y为R1上的两随机变量.记X≾Y,若对任意x∈R1,有P(X≤x)≥P(Y≤x).众知,若X≾Y,则存在一耦合(X,Y)使得X≤Y a.s..

另一方面,设p=11n-2,ηˆ为一参数为p的几何分布.注意到φ(λ)=log

则

进一步的,对任意x,y＞0,

有

因此对任意的λ＞0,E■e-φ(λ)σ■≤E■e-φ(λ)ˆη■.故由耦合方法可找到一个与ˆη具有相同分布的几何随机变量η使得η≾σ.

设α=-log(1-p)=-log(1-11n-2)(≈11n-2),γ为一服从参数为α的指数分布的随机变量.则易知■γ■与η具有相同的分布.此处对实数x,■x■表大于等于x的最小整数.令γ1,γ2,···,γn为γ的n个独立拷贝.至此只需如下引理.

引理2.2设γ,γ1,···,γn为一族独立同分布服从参数为α的指数分布的随机变量,则

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

3 讨论

3.1 一些图上的多重懒惰随机游走的刻画

因此

3.2 问题

易找出反例,当图G=(V,E)中顶点的度不是一致有界时(即度与顶点数n有关), E(maxi,jτij)6=Θ(hmaxlogn).例如n个顶点上的星图.为此有如下猜想.

问题考虑n个顶点上的有限连通无向图上的多重懒惰随机游走,当其度一致有界时, E(maxi,jτij)=Θ(hmaxlogn),其中hmax为此图上的简单随机游走的最大击中时.

致谢感谢审稿专家的宝贵意见及王龙敏博士的讨论.

[1]Aldous D,Fill J.Reversible Markov chains and random walks on graphs[M].Available：http：//statwww.berkeley.edu/users/aldous/RWG/book.html.

[2]Aldous D.Markov chain with almost exponential hitting time[J].Stoch.Proc.Appl.,1982,13：305-310.

[3]Aldous D.Meeting time for indepedent Markov chains[J].Stoch.Proc.Appl.,1991,38：185-193.

[4]Levin D A,Peres Y,Wilmer E L.Markov chains and mixing times[M].Washington：Amer.Math. Soc.,2009.

[5]陆中胜.半直线上随机环境中的随机游动的常返性[J].数学杂志.2003,23(1)：29-32.

[6]任敏,张光辉,费时龙.半直线上的独立随机环境中的随机游动[J].数学杂志,2015,32(5)：930-934.

[7]Orenshtein T,Shinkar I.Greedy random walk[J].Combin.Prob.Comput.,2014,23：269-289.

[8]Li W B,Shao Q M.Gaussian processes：inequalities,small ball probabilities and applications[M]. Stoch.Proc.：The.Meth.,Handbook of Statistics,New York：Elsevier,2001：533-598.

[9]Elsasser R,Sauerwald T.Tight bounds for the cover time of multiple random walks[J].Theor.Comp. Sci.,2011,412：2623-2641.

MULTIPLE LAZY RANDOM WALKS ON CYCLES

WANG Bin

(School of Science,Guilin University of Technology,Guilin 541004,China)

In this note,for the multiple lazy random walks on cycle with n vertices.By coupling method,we prove that the expectation of the maximum of meeting times is of order hmax×logn,where hmaxis the maximum of hitting time for a simple random walk on cycles with n vertices.

multiple random walks;hitting time;meeting time

O211.62

A

0255-7797(2017)05-1081-06

2015-09-22接收日期：2016-02-25

国家自然科学基金NSFC(11401127);广西自然科学基金GXNSF(2014GXNSFCA 118015; 2014GXNSFBA118006)及桂林理工大学启动金.

王彬(1980-),男,湖南邵阳,副教授,主要研究方向：随机过程及其在随机图与复杂网络中的应用.

2010 MR Subject Classif i cation：60G50;60J10