圈上的多重懶惰隨機(jī)游走

王彬

(桂林理工大學(xué)理學(xué)院,廣西桂林541004)

圈上的多重懶惰隨機(jī)游走

王彬

(桂林理工大學(xué)理學(xué)院,廣西桂林541004)

本文考慮了n個(gè)定點(diǎn)的圈上的多重懶惰隨機(jī)游走.利用偶和方法證明了其最大相遇時(shí)的期望的階數(shù)為hmax×logn,其中hmax為圈上的一簡(jiǎn)單隨機(jī)游走的最大擊中時(shí).

多重懶惰隨機(jī)游走;相遇時(shí);擊中時(shí)

1 引言及主要結(jié)果

隨機(jī)游走是概率論中的一個(gè)熱點(diǎn),其在計(jì)算機(jī)等領(lǐng)域有著廣泛的應(yīng)用.簡(jiǎn)單隨機(jī)游走定義如下[1]：從一給定連通無(wú)向圖G=(V,E)中的某一頂點(diǎn)出發(fā)的一隨機(jī)過(guò)程,其每一步獨(dú)立等概率地選擇其相鄰的頂點(diǎn).給定G上的一簡(jiǎn)單隨機(jī)游走以及任意兩頂點(diǎn)u,v,擊中時(shí)h(u,v)表從u點(diǎn)出發(fā)第一次到達(dá)v點(diǎn)的平均時(shí)間.令hmax：=maxu,vh(u,v).文獻(xiàn)[2,3]等研究了擊中時(shí)、hmax的諸多性質(zhì).關(guān)于隨機(jī)游走的綜述,參見(jiàn)文獻(xiàn)[1,4].

近年來(lái),人們考慮了各種非簡(jiǎn)單隨機(jī)游走,比如貪婪隨機(jī)游走[5]、隨機(jī)環(huán)境中的隨機(jī)游走[6,7]等.本文考慮如下多重懶惰隨機(jī)游走：令G=(V,E)表示有n限連通o無(wú)向圖,其中V={1,2,···,n}.假設(shè)在0時(shí)刻每個(gè)頂點(diǎn)i∈V上有一懶惰隨機(jī)游走且所有從

每個(gè)頂點(diǎn)出發(fā)的隨機(jī)游走是相互獨(dú)立的.設(shè)在t時(shí)刻S(i)處于頂點(diǎn)v,即=v.則在t+1時(shí)刻此游走待在n的概率為跑向相鄰頂點(diǎn)的概率為.其中d(v)表示v的度數(shù).定義：=min一個(gè)自然且有意思的問(wèn)題如下.

問(wèn)題考慮有限連通無(wú)向圖上的多重懶惰隨機(jī)游走,經(jīng)過(guò)多長(zhǎng)時(shí)間每個(gè)隨機(jī)游走與其他所有的隨機(jī)游走相遇過(guò)?此時(shí)間與hmax有什么關(guān)系?

對(duì)于圈而言,本文證明了如下定理.

定理1.1令Zn=(V,E),其中V={1,···,n},E={jk|j≡k±1 mod n}.考慮Zn上的多重懶惰隨機(jī)游走,則

本文中記號(hào)說(shuō)明如下P(·)及E(·)表示一個(gè)隨機(jī)變量的概率、期望.設(shè)f(n)＞0,g(n)＞0,其中n屬于自然數(shù).記f(n)=O(g(n)),若存在一正常數(shù)C使得當(dāng)n足夠大時(shí),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 上界

為得到上界,只需注意到如下事實(shí)(見(jiàn)文獻(xiàn)[3,性質(zhì)1]).對(duì)所有可逆馬氏鏈存在一正常數(shù)K使得maxijE(τij)≤Khmax.現(xiàn)開(kāi)始給出其上界.事實(shí)上,對(duì)任意兩頂點(diǎn)i,j∈Zn,

注此上界對(duì)所有有限連通圖上的多重懶惰隨機(jī)游走的最大相遇時(shí)都成立.

2.2 下界

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

為得到下界首先證明存在一服從幾何分布的隨機(jī)變量η使得η?σ1(見(jiàn)引理2.1);然后由如下引理2.2可得

其中諸η(?)是η的獨(dú)立拷貝.因此只需要證明如下引理2.1-2.2.

為找到這樣的η,首先描述下直覺(jué).由文獻(xiàn)[8,p.254],可知當(dāng)i非常大時(shí),

此處Bt表一從原點(diǎn)出發(fā)的標(biāo)準(zhǔn)Brown運(yùn)動(dòng).

引理2.1存在一參數(shù)為11n-2的幾何分布η使得η?σ.

證令φ(λ)=log?μ(λ),其中?μ(λ)為μ的Laplace變換.設(shè)Mt：=exp(λXt-φ(λ)t).易知

由停時(shí)定理有E(exp(λXσ-φ(λ)σ))=1.注意到Xσ取值于且此隨機(jī)游走是對(duì)稱的.因此

也就是說(shuō)

1定義：令X,Y為R1上的兩隨機(jī)變量.記X?Y,若對(duì)任意x∈R1,有P(X≤x)≥P(Y≤x).眾知,若X?Y,則存在一耦合(X,Y)使得X≤Y a.s..

另一方面,設(shè)p=11n-2,η?為一參數(shù)為p的幾何分布.注意到φ(λ)=log

則

進(jìn)一步的,對(duì)任意x,y＞0,

有

因此對(duì)任意的λ＞0,E■e-φ(λ)σ■≤E■e-φ(λ)?η■.故由耦合方法可找到一個(gè)與?η具有相同分布的幾何隨機(jī)變量η使得η?σ.

設(shè)α=-log(1-p)=-log(1-11n-2)(≈11n-2),γ為一服從參數(shù)為α的指數(shù)分布的隨機(jī)變量.則易知■γ■與η具有相同的分布.此處對(duì)實(shí)數(shù)x,■x■表大于等于x的最小整數(shù).令γ1,γ2,···,γn為γ的n個(gè)獨(dú)立拷貝.至此只需如下引理.

引理2.2設(shè)γ,γ1,···,γn為一族獨(dú)立同分布服從參數(shù)為α的指數(shù)分布的隨機(jī)變量,則

證事實(shí)上,由指數(shù)分布的無(wú)記憶性可得

3 討論

3.1 一些圖上的多重懶惰隨機(jī)游走的刻畫(huà)

因此

3.2 問(wèn)題

易找出反例,當(dāng)圖G=(V,E)中頂點(diǎn)的度不是一致有界時(shí)(即度與頂點(diǎn)數(shù)n有關(guān)), E(maxi,jτij)6=Θ(hmaxlogn).例如n個(gè)頂點(diǎn)上的星圖.為此有如下猜想.

問(wèn)題考慮n個(gè)頂點(diǎn)上的有限連通無(wú)向圖上的多重懶惰隨機(jī)游走,當(dāng)其度一致有界時(shí), E(maxi,jτij)=Θ(hmaxlogn),其中hmax為此圖上的簡(jiǎn)單隨機(jī)游走的最大擊中時(shí).

致謝感謝審稿專家的寶貴意見(jiàn)及王龍敏博士的討論.

[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ī)環(huán)境中的隨機(jī)游動(dòng)的常返性[J].數(shù)學(xué)雜志.2003,23(1)：29-32.

[6]任敏,張光輝,費(fèi)時(shí)龍.半直線上的獨(dú)立隨機(jī)環(huán)境中的隨機(jī)游動(dòng)[J].數(shù)學(xué)雜志,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

國(guó)家自然科學(xué)基金NSFC(11401127);廣西自然科學(xué)基金GXNSF(2014GXNSFCA 118015; 2014GXNSFBA118006)及桂林理工大學(xué)啟動(dòng)金.

王彬(1980-),男,湖南邵陽(yáng),副教授,主要研究方向：隨機(jī)過(guò)程及其在隨機(jī)圖與復(fù)雜網(wǎng)絡(luò)中的應(yīng)用.

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