اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMany Random Walks Are Faster Than One
55
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.
قيم البحث
اقرأ أيضاً
Given a branching random walk on a set $X$, we study its extinction probability vectors $mathbf q(cdot,A)$. Their components are the probability that the process goes extinct in a fixed $Asubseteq X$, when starting from a vertex $xin X$. The set of e
xtinction probability vectors (obtained letting $A$ vary among all subsets of $X$) is a subset of the set of the fixed points of the generating function of the branching random walk. In particular here we are interested in the cardinality of the set of extinction probability vectors. We prove results which allow to understand whether the probability of extinction in a set $A$ is different from the one of extinction in another set $B$. In many cases there are only two possible extinction probability vectors and so far, in more complicated examples, only a finite number of distinct extinction probability vectors had been explicitly found. Whether a branching random walk could have an infinite number of distinct extinction probability vectors was not known. We apply our results to construct examples of branching random walks with uncountably many distinct extinction probability vectors.
We consider random walks in random Dirichlet environment (RWDE) which is a special type of random walks in random environment where the exit probabilities at each site are i.i.d. Dirichlet random variables. On $Z^d$, RWDE are parameterized by a $2d$-
uplet of positive reals. We prove that for all values of the parameters, RWDE are transient in dimension $dge 3$. We also prove that the Green function has some finite moments and we characterize the finite moments. Our result is more general and applies for example to finitely generated symmetric transient Cayley graphs. In terms of reinforced random walks it implies that directed edge reinforced random walks are transient for $dge 3$.
We study variable-speed random walks on $mathbb Z$ driven by a family of nearest-neighbor time-dependent random conductances ${a_t(x,x+1)colon xinmathbb Z, tge0}$ whose law is assumed invariant and ergodic under space-time shifts. We prove a quenched
invariance principle for the random walk under the minimal moment conditions on the environment; namely, assuming only that the conductances possess the first positive and negative moments. A novel ingredient is the representation of the parabolic coordinates and the corrector via a dual random walk which is considerably easier to analyze.
We consider a one dimensional random walk in random environment that is uniformly biased to one direction. In addition to the transition probability, the jump rate of the random walk is assumed to be spatially inhomogeneous and random. We study the p
robability that the random walk travels slower than its typical speed and determine its decay rate asymptotic.
Lecture Notes. Minicourse given at the workshop Activated Random Walks, DLA, and related topics at IMeRA-Marseille, March 2015.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
