Universal cover-time distribution of heterogeneous random walks Jia-Qi Dong1 2Wen-Hui Han1Yisen Wang1Xiao-Song Chen3and Liang Huang1 1Lanzhou Center for Theoretical Physics and Key Laboratory of Theoretical Physics of Gansu Province

2025-05-06 0 0 1.34MB 12 页 10玖币

侵权投诉

Universal cover-time distribution of heterogeneous random walks

Jia-Qi Dong,1, 2 Wen-Hui Han,1Yisen Wang,1Xiao-Song Chen,3and Liang Huang1, ∗

1Lanzhou Center for Theoretical Physics and Key Laboratory of Theoretical Physics of Gansu Province,

Lanzhou University, Lanzhou, Gansu 730000, China

2CAS Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, CAS, Beijing 100190, China

3School of Systems Science, Beijing Normal University, Beijing 100875, China

(Dated: October 12, 2022)

The cover-time problem, i.e., time to visit every site in a system, is one of the key issues of

random walks with wide applications in natural, social, and engineered systems. Addressing the

full distribution of cover times for random walk on complex structures has been a long-standing

challenge and has attracted persistent eﬀorts. Yet, the known results are essentially limited to

homogeneous systems, where diﬀerent sites are on an equal footing and have identical or close

mean ﬁrst-passage times, such as random walks on a torus. In contrast, realistic random walks are

prevailingly heterogeneous with diversiﬁed mean ﬁrst-passage times. Does a universal distribution

still exist? Here, by considering the most general situations, we uncover a generalized rescaling

relation for the cover time, exploiting the diversiﬁed mean ﬁrst-passage times that have not been

accounted for before. This allows us to concretely establish a universal distribution of the rescaled

cover times for heterogeneous random walks, which turns out to be the Gumbel universality class

that is ubiquitous for a large family of extreme value statistics. Our analysis is based on the

transfer matrix framework, which is generic that besides heterogeneity, it is also robust against

biased protocols, directed links, and self-connecting loops. The ﬁnding is corroborated with extensive

numerical simulations of diverse heterogeneous non-compact random walks on both model and

realistic topological structures. Our new technical ingredient may be exploited for other extreme

value or ergodicity problems with nonidentical distributions.

I. INTRODUCTION

Random walk [1–6] has been one of the pillars of the

probability theory since the 17th century from the analy-

sis of games of chance [7], and lays the foundation of the

modern theory of stochastic processes and Brownian mo-

tions [8–10]. Cover time, the time for a random walker to

visit all the sites, is a key quantity that characterizes the

eﬃciency of exhaustive search [11–15]. The cover-time

problem, also known as the traverse process [11, 12], has

widespread natural [16–19], social [14, 15, 20, 21], and

engineering [22–24] applications. Examples include ro-

dent animals searching and storing as much food as pos-

sible in their conﬁned habitats [16–18], the dendritic cells

chasing all danger-associated antigens in a constantly

changing tissue environment [19], collecting all the items

in the classic coupon collector problem [14, 15, 20, 21],

the Wang-Landau Monte Carlo algorithm sampling ev-

ery energy state in calculating the density of states in

a rough energy landscape [22, 23, 25], robotic explo-

ration of a complex domain for cleaning or demining

and corresponding algorithm design [24], and informa-

tion spreading or collecting on large scale Internet, mo-

bile ad hoc network, peer-to-peer network, and other dis-

tributed systems where random walks are more feasible

versus topology-driven algorithms due to the dynamical

evolution, unknown global structure, limited memory, or

otherwise broadcast storm issues [26–30].

Since the proposal of the cover-time problem [11–15],

∗Corresponding author: huangl@lzu.edu.cn

a series of theoretical progresses has been made for stan-

dard random walks, where the walker moves to the neigh-

boring sites with equal probabilities. By bridging the

cover time with the longest ﬁrst-passage time (FPT, the

time required to reach a particular site), the cover time

can be estimated via the tail of the FPT distribution

[14]. The average cover time scales distinctively in diﬀer-

ent dimensions, i.e., N2for one-dimensional (1D) lattices

[13, 15, 31], N(ln N)2for two-dimensional (2D) lattices

with periodic boundary conditions, or 2-torus [18, 32],

and Nln Nfor 3- or 4-torus [13].

Despite these theoretical progresses, the full distribu-

tion of the cover time for complex topologies has been

a long-standing challenge and has attracted persistent

eﬀorts due to its ultimate importance in characterizing

all types of statistics including extreme events [33–38].

Erd˝os and R´enyi found in 1961 that the cover time for

fully connected graphs with self-connecting loops (the

coupon collection time) follows the Gumbel distribution

[33], one of the well-known extreme value distributions

[39]. Later in 1989 Aldous conjectured that for random

walks on d≥3 torus the distribution is also Gumbel

[34], which has been proved by Belius in 2013 [35]. Re-

cently, a substantial progress has been achieved for non-

compact homogeneous random walks, where the mean

ﬁrst-passage times (MFPT) hTki≡hTk←sisaveraging

over the starting sites are narrowly distributed and can

be approximated by a single value hTi≡hTkik, i.e., the

global mean ﬁrst-passage time (GMFPT). In particular,

by rescaling the cover time τas ˜χ=τ/hTi − ln Nand

employing the Laplace transform, the full distribution for

˜χwas shown to follow the Gumbel universality class [36].

arXiv:2210.05122v1 [cond-mat.stat-mech] 11 Oct 2022

FIG. 1. Schematics of heterogeneous random walks. (a) Het-

erogeneity due to the conﬁnement boundary and nonuniform

landscapes, which result in diversiﬁed location-dependent oc-

cupation ratios and mean ﬁrst-passage times. (b) Heterogene-

ity due to inherent heterogeneous connection structures, e.g.,

a small subset pruned from Wikipedia where nodes are pages

and edges are hyperlinks.

It should be noted that the theory in Ref. [36] only

depends on a single value, i.e., the GMFPT hTi, of dif-

ferent random walk models. This will be suﬃcient for

homogeneous systems. For example, for random walks

on a torus, hTkifor diﬀerent sites will be exactly the

same due to the translational symmetry. However, for

conﬁned or disordered systems, or those with complex

topological structures, as illustrated in Fig. 1, sites at

diﬀerent locations are obviously inequivalent [5, 40–47],

even in the thermodynamic limit. This invalids the basis

of the rescaling process and leads to an immediate ques-

tion that whether there still exists a universal cover-time

distribution for such systems, and more commonly, in

general heterogeneous systems where hTkican be diverse

[48]. This is of particular importance as most realistic

systems are in fact heterogeneous.

In this paper, based on the transfer matrix framework

and employing the longest FPT for the cover time, we de-

rive the Gumbel universality class for rescaled cover-time

distributions explicitly in heterogeneous systems under

reasonable approximations. The key is the generalized

rescaling relation exploiting the complete set of MFPTs

{hTki}, which can degenerate to Ref. [36] for homoge-

neous cases. Thus our results extend the universality of

the Gumbel class to realistic, heterogeneous non-compact

random walks. The ﬁnding is corroborated by extensive

numerical simulations of 12 diverse random walk models

with ideal or realistic heterogeneous structures, standard

or biased random walk protocols, and undirected or di-

rected connections.

The rest of the paper is organized as follows. In Sec. II,

the distribution function of the rescaled cover times in

heterogeneous systems is derived. Section III provides ev-

idence of the universal distribution with extensive simula-

tions. Conclusion and discussions are provided in Sec. IV.

Detailed derivations are provided in the Appendices.

II. THEORY OF UNIVERSAL COVER-TIME

DISTRIBUTIONS FOR HETEROGENEOUS

RANDOM WALKS

For random walks in homogeneous systems, diﬀerent

sites are on an equal footing where the MFPT to all the

sites are close to each other and can be approximated by

their mean value, i.e., the GMFPT hTi. In contrast, for

random walks in a conﬁned region, the existence of the

boundary breaks the symmetry of the sites. For example,

the boundary itself may have attracting eﬀects that the

walker crawls along the boundary and reaches sites closer

to the boundary with a higher probability. Therefore, the

FPT between a given pair of sites depends not only on

their distance, but also on their speciﬁc locations. This is

even critical for random walks on complex structures such

as heterogeneous graphs, where sites with more edges are

easier to be reached. As a natural consequence, the time

for the walker to visit all the sites, i.e., the cover time, will

need to consider the diversity of those FPTs, especially

the long FPTs.

Therefore, in the following we shall ﬁrst present the

FPT distribution function based on the transfer matrix

framework of Markovian process, which can take the het-

erogeneity into account through inhomogeneous transi-

tion probabilities. Then by counting the longest FPTs,

the distributions of the cover times are derived.

A. First-passage time

The transfer probability that a random walker moves

from site jto site iis denoted as ωi←j. The case i=jis

included to account for the case when the walker has a

nonzero probability to stay on the same site at the next

time step, which eﬀectively describes the eﬀect of self-

connecting loops. Collecting all the elements forms the

transfer matrix Ω= [ωi←j]. The occupation probability

gi(t) that a walker appears on site iat time tcan be

obtained recursively by

gi(t) = X

ωi←jgj(t−1).(1)

To obtain the FPT from starting site sto site k, a ma-

trix D(k) is constructed based on Eq. (1). The element

Dij (k) equals ωi←jexcept the k’th column Dik(k), which

equals 0. When ωi←jin Eq. (1) is replaced by Dij (k), if

the random walker arrives at site k, it will be removed

from the system in the next time step. Then, the FPT

probability Fk←s(t) from site sto site kat time tis equal

to the diﬀerence of the probability that the walker is still

in the system at time tand that at t+ 1, given that the

walker starts from site sin the beginning:

Fk←s(t) = kD(k)tG(s)k1− kD(k)t+1G(s)k1,(2)

where G(s) is the initial spatial distribution at t= 0,

Gi(s) = 1 if i=sand zero otherwise, kvk1=Piviis

the L1 norm of vector v.

In very short time scales, Fk←s(t) is caused by the

direct diﬀusion process according to the transfer matrix,

thus it depends on the speciﬁc starting site sand could

decrease rapidly versus time if sand kare not far from

each other.

For large t, the asymptotic behavior of Fk←s(t) in

Eq. (2) is determined by the largest eigenvalue λk(0 <

λk<1) of the matrix D(k), i.e., Fk←s(t)∼λt

k∼e−t/Tk,

where Tk=−1/ln(λk) is the characteristic FPT to site

kin the long time limit. Therefore, the asymptotic be-

havior of Eq. (2) can be written as

Fk(t)'1

exp −t

Tk.(3)

The FPT distribution Fk←s(t) in the long time limit

only depends on Tk, but is independent to the starting

site s. For random walk on homogeneous systems such

as lattices with periodic boundary conditions, all target

sites are identical and share the same characteristic FPT.

However, for heterogeneous systems such as conﬁned re-

gion with nontrivial boundary conditions or other com-

plex structures, the characteristic FPT Tkcan be scat-

tered in a broad span, thus the distribution function Fk(t)

will be nonidentical and site dependent. Therefore, the

complete set of the diverse characteristic FPTs will be

needed to determine the cover-time distribution in het-

erogeneous system.

In many cases it is impractical to calculate the charac-

teristic FPT Tkbased on matrix D(k), since the transfer

probability ωi←jcan not be completely obtained in gen-

eral. Alternatively, since Tk=RtFk(t)dtis also the mean

FPT to site k,Tkcan be approximated by the average

of the FPT Tk←sfrom all possible starting site sto site

k, i.e., Tk≈ hTki ≡ hTk←sis(see Appendix A for an

exemplary numerical veriﬁcation).

B. Full cover time

For a trajectory which fully covers the system, the ran-

dom walker will ﬁrst successively pass N−1 sites in a

speciﬁc order. Then the time arriving at the last un-

visited site is the full cover time. Meanwhile, this time

is also the FPT to this ending site. Therefore, the cover

time can be regarded as the longest FPT in a single cover

process [14]. To be speciﬁc, the probability that the cover

time equals τcan be estimated as

P(τ) = 1

k6=s

k,s

Fk(τ)



i /∈{k,s}

τ−1

Fi(t)

.(4)

The formula in the square brackets denotes the prob-

ability that all sites except the starting site sand the

ending site khave been visited during τ−1 steps, and

Fk(τ) is the probability that the last unvisited site kis

ﬁrstly visited at τ, which completes the covering pro-

cess. The factor 1/N is for the average over all the start-

ing sites. Equation (4) neglects any structural correla-

tion of the background system, which should be (at least

weakly) satisﬁed for non-compact random walks [49], i.e.,

the diﬀusion dimension dwof the random walk (deﬁned

by h|r|2i ∼ t2/dw) is smaller than the dimension of the

background space d. In this case, the number of sites

visited by the walker |r|dwwill be negligible compared

to all the sites within |r|, which is |r|d. Thus the walker

needs to traverse the region many times in order to cover

all the sites. This means that the eﬀective structural cor-

relation will be signiﬁcantly reduced as the information

of the initial position is completely lost when the walker

comes back again.

Replacing Tkby hTki, and considering τ−1∼

=τfor

τ1, the summation in the square bracket yields

t=1

Fk(t)∼

=1−exp −τ

hTki.(5)

For τbeing large, higher order terms in the production

in the square bracket can be neglected, leading to

Fi(t)∼

=exp −

i=1

exp −τ

hTii!,(6)

where the condition i /∈ {k, s}has also been relaxed.

Deﬁne a rescaled cover time χfrom the original cover

time τby

χ=−ln X

e−τ

hTii,(7)

where the summation can be replaced by the in-

tegration if the distribution of hTiiis known, i.e.,

Pie−τ

hTii=NRe−τ

hTiiP(hTii)dhTii. Together with

Eq. (3), it is straightforward to show that PkFk(τ) =

exp(−χ)dχ/dτ. Thus one has

P(τ)dτ∼

=exp[−exp(−χ)] exp(−χ)dχ, (8)

yielding a universal distribution function for the rescaled

cover time χthat is independent to any of the system

details:

P(χ) = exp(−χ−exp(−χ)).(9)

The detailed derivations are shown in Appendix B.

Equation (9) is the Gumbel distribution which is one

of the three well-known extreme value distributions [50],

and shares the same form as in the theory for homoge-

neous cases [36]. The main diﬀerence is the rescaling

functional relation between χand τ, e.g., ˜χ=τ/hTi −

ln Nfor homogeneous cases, and Eq. (7) for the heteroge-

neous cases, which now requires the complete set of MF-

PTs {hTki} or their distribution function. Equation (7)

ensures a monotonous relation between χand τ. For

homogeneous cases, all sites share a single identical char-

acteristic MFPT, which is then the GMFPT hTi, and

Eq. (7) degenerates to ˜χ=τ/hTi − ln N.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Universalcover-timedistributionofheterogeneousrandomwalksJia-QiDong,1,2Wen-HuiHan,1YisenWang,1Xiao-SongChen,3andLiangHuang1,1LanzhouCenterforTheoreticalPhysicsandKeyLaboratoryofTheoreticalPhysicsofGansuProvince,LanzhouUniversity,Lanzhou,Gansu730000,China2CASKeyLaboratoryofTheoreticalPhysics,Institu...

展开>> 收起<<

Universal cover-time distribution of heterogeneous random walks Jia-Qi Dong1 2Wen-Hui Han1Yisen Wang1Xiao-Song Chen3and Liang Huang1 1Lanzhou Center for Theoretical Physics and Key Laboratory of Theoretical Physics of Gansu Province.pdf

共12页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Universal cover-time distribution of heterogeneous random walks Jia-Qi Dong1 2Wen-Hui Han1Yisen Wang1Xiao-Song Chen3and Liang Huang1 1Lanzhou Center for Theoretical Physics and Key Laboratory of Theoretical Physics of Gansu Province

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: