Stationary Probability and First-Passage Time of Biased Random Walk?

Jing-Wen Li(李井文),Shen-Li Tang(唐沈立),and Xin-Ping Xu(徐新平)

School of Physical Science and Technology,Soochow University,Suzhou 215006,China

1 Introduction

Random walk(RW)is a powerful tool in studying stochastic processes.As a fundamental model in many miscellaneous areas,the theory of random walk has been successfully applied in computer science,physics,ecology,economics,and a number of other fields.[1?4]Many physical characteristics of RW,such as the dispersal distributions, first-passage times(FPT),encounter rates,etc.,have been extensively investigated in Refs.[5–7].

Here,we focus on the stationary probability(SP)and first-passage time(FPT)of biased random walk(BRW)on 1D chain.The stationary probability(SP)is the longtime limiting probability and plays an important role in Markov processes.The first-passage time(FPT)indicates the expected time to hit a target node for the first time for a walker staring from a source node.[6,8]It is a quantitative indicator to characterize the transport efficiency,and carries much information of random walks and many other quantities are related to FPT.[8?10]

In this paper,we will study the BRW on the onedimensional(1D)chain,which lacks one connection compared to the regular cycle.The left-most and right-most points are topological boundaries of the 1D chain and re fl ect the walker to their neighbors. Although there are numerous studies of FPT of RWs in Refs.[11–14],BRWs has received little attention due to the difficult analytical calculation.Previous work study FPT of homogeneous/unbiased RWs using the effective resistance method.[15?17]However,the method of effective resistance is only valid for the homogeneous/unbiased RWs,where the probability to each direction at a given vertex is equal.For the homogeneous/unbiased RWs on the 1D chain,the SP is proportional to the degree of the vertexand FPT from the left-most vertex 1 to the right-most vertexNequals to(N?1)2(easily obtained by the method of effective resistance).Here,we consider BRW on the 1D chain,where at each step the walker moves to the left and right with probabilitiespandqrespectively(0 6p,q6 1,p+q=1).Whenp=q=1/2,the BRW becomes homogeneous/unbiased RWs,so the BRW defined by parametersp,qis a more general model and its SP and FPT have not been investigated yet.

To study BRW parameterized byp,q(0 6p,q6 1,p+q=1),we consider the SPand FPT from the left-most vertex 1 to the right-most ver-using the spectrum method.The SP and FPT of RWs are related to the spectrum of the normalized adjacency matrixA=D?1/2AD?1/2.[18?19]whereAis the adjacency matrix(Aijequals to 1 ifiandjare connected,and 0 otherwise)andDis the degree diagonal matrix(diagonal elementDii=di,diis the degree of vertexi).For the homogeneous/unbiased RWs,the nonzero elements between two connected verticesiandjof the normalized adjacency matrix arewhere 1/diis the probability fromitojand 1/djis the probability fromjtoi.In view of this fact,the nonzero elements between two connected verticesiandjof the normalized adjacency matrix are given by

wherepi→jis the probability fromitojandpj→iis the probability fromjtoi.For the BRW on 1D chain,p1→2=pN→N?1=1,pi→i?1=pandpi→i+1=q(i=2,3,...,N?1).Thus,the elements ofAijare sum-marized as,

The SP and FPT are closely related to the spectrum ofA.[1?4]Suppose the eigenvalues and orthonormalized eigenvectors ofAare{λi,vi}(i=1,2,...,N). The maximal eigenvalue is 1 and its corresponding eigenvector(vλ=1)determines the SP distribution.The SP at vertexk(,k=1,2,...,N)equals to the square of thekth component ofvλ=1,i.e.,[20]

The FPT starting from vertexitojis related to the other(exceptλ=1)eigenvalues and eigenvectors by the following equation,[19?20]

In this paper,we focus on the FPT from the left-most vertex 1 to the right-most vertexN,which can be recasted as,

In order to calculate SP and FPT in Eqs.(3)and(5),all the eigenvalues and eigenvectors{λi,vi}are required.In the following,we will put emphasis on the calculation of the eigenvalues and orthonormalized eigenvectors ofA.

We use the Chebyshev polynomial method[21?22]to calculate the eigenvalues and orthonormalized eigenvectors ofA.The eigenequation isAv=λv,λis the eigenvalues andvis its corresponding eigenvector.Suppose eigenvectorvhasNcomponentsvT={v(1),v(2),...,v(N)},the eigenequation can be decomposed into the followingNlinear equations,

Equation(8)can be simplified asv(i?1)+v(i+1)=which is similar to the recursive relation of the Chebyshev polynomials of the second kind.Using the recursive definition of Chebyshev polynomials and the mapping relatio nthe arbitrary componentv(j)can be written as a function ofv(3)andv(2),Combining Eqs.(9)and(10)to eliminatev(N),we getwhich is further simplified as a function ofv(3)andv(2)by settingj=N?1 andj=N?2 in Eq.(11),

Utilizing Eqs.(6)and(7),we obtain an equation forv(3)andv(2),

We have obtained two independent Eqs.(12)and(13)forv(3)andv(2).The two equations should have nonzero solutions,the determinant of the coefficients equals to zero,which leads to,

where the first term equals to(λ2?1+pq/λ2)UN?4(x).After a simple recombination of Eq.(14),we arrive at

Noting that(mapping relation)and the Chebyshev polynomial recursive relation 2xUi(x) =Ui?1(x)+Ui+1(x),the first term in the square brackets of the above equation equals toand the third term in the square brackets equals to?pqUN?4(x).Thus Eq.(15)becomes as

which can be written as a simple form,

Solving Eq.(16),we obtain two special solutionsλ=±1.The remainingN?2 solutions are determined byUN?2(x)≡sin(N?1)θ/sinθ=0(x=cosθ),which leads to

Thus we get theNeigenvalues forλ:

Next,we analyze the eigenvectors.First,we consider the eigenvectors ofλ=±1.Whenλ=±1,Eq.(13)becomes as

thus Eq.(11)is simplified as

Combining Eqs.(6)and(10),we express the arbitrary componentv(j)as a function ofv(1),

Noting that(normalization condition),we obtain

Thus we have successfully determined eigenvectors of the eigenvaluesλ=±1.For the other eigenvectors ofλ=±1,we apply the same technique,where the normalization factor depends on the eigenvalues.

To obtain the eigenvectors ofλV=±1,we write Eqs.(6)and(7)asv(2)Thus Eqs.(10)and(11)can be rewritten as a function ofv(1),Similarly,according to the normalization conditionand after some algebraic calculations,we obtain

Thus we have obtained the remaining(N?2)eigenvectors when the variablexin Eq.(20)is replaced toxkin Eq.(17).

In the rest of this paper,we will use the exact solutions of eigenvalues and eigenvectors to calculate the SP and FPT.In accordance to Eq.(3),the SP is equal to the square of the eigenvector ofλ=1,which is calculated using the expressionv(j)|λ=1in Eq.(19)as follows,

Whenp=q=1/2 and taking the limit ofq/p→1,the above equation is simplified as

which is consistent from the calculationfor the homogeneous/unbiased RWs.

We now proceed to calculate the FPT in Eq.(5).The summation of contribution in Eq.(5)is composed by two parts:one is the contribution fromλ=?1 and the others from

where the contribution ofλ=?1 can be calculated usingv(j)|λ=?1in Eq.(19)

Noting that

Eq.(25)can be simplified as

Thus,the FPT in Eq.(23)can be written as the following explicit form:

Particularly,whenp=q=1/2,the first term of Eq.(27)is simplified asF1→N|λ=?1=(1/2)[1+(?1)N]by taking the limit ofq/p→1.In this case,the second term of Eq.(27)is calculated to be

where the series summation formula

are applied in the above calculations.Hence,the FPT for the homogeneous/unbiased RWs is

which is consistent with the expectation using the method of effective resistance.

Now we analyze the two extreme cases:p=0,q=1 andp=1,q=0.For these two extreme cases,the second summation in Eq.(27)is simplified as

while the first term(See Eq.(24))approaches to 0 forp=0,q=1 and∞forp=1,q=0.This result is consistent with our intuition.Whenp=0,q=1,the walker moves to the right at each step,the FPT is identical to the length of the 1D chainN?1;Whenp=1,q=0,the walker moves to the left at each step and the walker can never reach the right-most vertex,thus the FPT is in finite.

Fig.1 (Color online)F1→N|λ=?1vs.N for q/p>1(a)and q/p<1(b).F1→N|λ=?1shows an exponential decay for q/p>1(see(a)p=0.45,p=0.4,p=0.3 and p=0.2).In contrast,F1→N|λ=?1increases linearly for q/p<1(see(b)q=0.45,q=0.4,q=0.3,and q=0.2).

Fig.2 (Color online)as a function of N for different values of p,q.When q/p→1(pq=1/4),is close to the upper bound(N ? 1)2for p=q=1/2.shows a double power-law behavior.For NNc≡ |p? q|?1.The black solid line indicates the scaling N2and the dashed line implies linear behavior of N.

Finally,we investigate the dependence of FPT on the system sizeN.In Eq.(27),the first termF1→N|λ=?1(see Eq.(24))shows different behavior forq/p>1 andq/p<1.Figure 1(a)showsF1→N|λ=?1vs.Nforp=0.45,p=0.4,p=0.3,andp=0.2(q/p>1),which shows an exponential decay and approaches to 0 for largeN.On the contrary,F1→N|λ=?1increases linearly forq/p<1,as shown in Fig.1(b).Particularly,whenq→0,F1→N|λ=?1is close to the analytical expression(N?1)p/4q.The main contribution of FPT is determined by the second term of Eq.(27)(see Eq.(28)).Figure 2 showsas a function ofNfor different values ofp,q.As we can see,only depends on the product ofpandq;whenpq=0,1 is a complete linear function ofN.However,whenis close to the upper bound(N?1)2forp=q=1/2.Nevertheless,displays two kinds of behaviour forq/p=1.For small system(N

Fig.3 (Color online)FPTas a function of q for a 1D-Chain of N=10.FPT has a minimal value at qc≈0.2 in the region q∈(0,0.5).The peak around q0=0.5 corresponds to the FPT of homogeneous/unbiased RWs.We find that,the FPT of q=q′0≈0.03 is the same as that of the homogeneous/unbiased RWs((N?1)2)(see the vertical red lines in the figure).The critical value having the same FPT depends on the chain size N.In the inserted plot,we numerically investigate the dependence of the critical valueon the system size N,which shows a power-law decay～N?1.

Figure 3 shows the FPT as a function ofqfor a 1DChain ofN=10.Interestingly,FPT has a minimal value atqc≈0.2 betweenq∈(0,0.5).Forq

In summary,we obtain exact analytical results for the stationary probability and first-passage time of biased random walk as a function ofpandqfor the first time.Our results indicate that the first-passage time shows a double power-law behaviorF～(N?1)γ,where the exponentγ=2 forN<|p?q|?1andγ=1 forN>|p?q|?1.Furthermore,we find that there is a critical valueq=whose FPT is the same as the homogeneous/unbiased RWs ofq=q0=0.5.We investigate the dependence of such critical valueon the system sizeNand find a power law relationship～N?1.

[1]N.Guillotin-Plantard and R.Schott,Dynamic Random Walks:Theory and Application,Elsevier,Amsterdam(2006).

[2]W.Woess,Random Walks on In finite Graphs and Groups,Cambridge University Press,Cambridge(2000).

[3]F Spitzer,Principles of Random Walk,Springer,Berlin(2000).

[4]G.H.Weiss,Aspects and Applications of the Random Walk,North-Holland,New York(1994).

[5]Brian H.Kaye,A Random Walk Through Fractal Dimensions,VCH Publishers,New York(1989).

[6]S.Redner,A Guide to First-Passage Processes,Cambridge University Press,Cambridge(2001).

[7]X.K.Zhang,J.Wan,J.J.Lu,and X.P.Xu,Commun.Theor.Phys.56(2011)293.

[8]Z.Z.Zhang,et al.,Phys.Rev.E 81(2010)031118.

[9]R.Metzler and J.Klafter,Phys.Rep.339(2000)1.

[10]S.Havlin and D.ben-Avraham,Adv.Phys.36(1987)695.

[11]J.J.Kozak and V.Balakrishnan,Phys.Rev.E 65(2002)021105.

[12]J.J.Kozak and V.Balakrishnan,Int.J.Bifurcation Chaos Appl.Sci.Eng.12(2002)2379.

[13]E.Agliari,Phys.Rev.E 77(2008)011128.

[14]Z.Z.Zhang,W.L.Xie,S.G.Zhou,M.Li,and J.H.Guan,Phys.Rev.E 80(2009)061111;Phys.Rev.E 81(2010)016114.

[15]A.K.Chandra,P.Raghavan,W.L.Ruzzo,and R.Smolensky,inProceedings of the 21st Annnual ACM Symposium on the Theory of Computing,ACM Press,New York(1989)pp.574-586.

[16]P.Tetali,J.Theor.Probab.4(1991)101.

[17]P.G.Doyle and J.L.Snell,Random Walks and Electric Networks,The Mathematical Association of America,Oberlin,OH(1984).

[18]A.Garcia Cantu and E.Abad,Phys.Rev.E 77(2008)031121.

[19]H.Y.Chen and F.J.Zhang,Discrete.Appl.Math.155(2007)654.

[20]M.A.Pinsky and S.Karlin,An Introduction to Stochastic Modeling,Fourth Edition,Academic Press,New York(2011).

[21]X.P.Xu,Y.Ide,and N.Konno,Phys.Rev.A 85(2012)042327.

[22]T.J.Rivlin,Chebyshev Polynomials:From Approximation Theory to Algebra and Number Theory,Wiley-Interscience,2 ed.June,New York(1990).