اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRandom walks on graphs: new bounds on hitting, meeting, coalescing and returning
99
0
0.0
(
0
)
نشر من قبل
Roberto Imbuzeiro Oliveira
تاريخ النشر
2018
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove new results on lazy random walks on finite graphs. To start, we obtain new estimates on return probabilities $P^t(x,x)$ and the maximum expected hitting time $t_{rm hit}$, both in terms of the relaxation time. We also prove a discrete-time version of the first-named authors ``Meeting time lemma~ that bounds the probability of random walk hitting a deterministic trajectory in terms of hitting times of static vertices. The meeting time result is then used to bound the expected full coalescence time of multiple random walks over a graph. This last theorem is a discrete-time version of a result by the first-named author, which had been previously conjectured by Aldous and Fill. Our bounds improve on recent results by Lyons and Oveis-Gharan; Kanade et al; and (in certain regimes) Cooper et al.
قيم البحث
اقرأ أيضاً
Coalescing random walk on a unimodular random rooted graph for which the root has finite expected degree visits each site infinitely often almost surely. A corollary is that an opinion in the voter model on such graphs has infinite expected lifetime.
Additionally, we deduce an adaptation of our main theorem that holds uniformly for coalescing random walk on finite random unimodular graphs with degree distribution stochastically dominated by a probability measure with finite mean.
In recent years, protocols that are based on the properties of random walks on graphs have found many applications in communication and information networks, such as wireless networks, peer-to-peer networks and the Web. For wireless networks (and oth
er networks), graphs are actually not the correct model of the communication; instead hyper-graphs better capture the communication over a wireless shared channel. Motivated by this example, we study in this paper random walks on hyper-graphs. First, we formalize the random walk process on hyper-graphs and generalize key notions from random walks on graphs. We then give the novel definition of radio cover time, namely, the expected time of a random walk to be heard (as opposed to visit) by all nodes. We then provide some basic bounds on the radio cover, in particular, we show that while on graphs the radio cover time is O(mn), in hyper-graphs it is O(mnr) where n, m and r are the number of nodes, the number of edges and the rank of the hyper-graph, respectively. In addition, we define radio hitting times and give a polynomial algorithm to compute them. We conclude the paper with results on specific hyper-graphs that model wireless networks in one and two dimensions.
Let $mathbb{T}^d_N$, $dge 2$, be the discrete $d$-dimensional torus with $N^d$ points. Place a particle at each site of $mathbb{T}^d_N$ and let them evolve as independent, nearest-neighbor, symmetric, continuous-time random walks. Each time two parti
cles meet, they coalesce into one. Denote by $C_N$ the first time the set of particles is reduced to a singleton. Cox [6] proved the existence of a time-scale $theta_N$ for which $C_N/theta_N$ converges to the sum of independent exponential random variables. Denote by $Z^N_t$ the total number of particles at time $t$. We prove that the sequence of Markov chains $(Z^N_{ttheta_N})_{tge 0}$ converges to the total number of partitions in Kingmans coalescent.
The main results in this paper are about the full coalescence time $mathsf{C}$ of a system of coalescing random walks over a finite graph $G$. Letting $mathsf{m}(G)$ denote the mean meeting time of two such walkers, we give sufficient conditions unde
r which $mathbf{E}[mathsf{C}]approx 2mathsf{m}(G)$ and $mathsf{C}/mathsf{m}(G)$ has approximately the same law as in the mean field setting of a large complete graph. One of our theorems is that mean field behavior occurs over all vertex-transitive graphs whose mixing times are much smaller than $mathsf{m}(G)$; this nearly solves an open problem of Aldous and Fill and also generalizes results of Cox for discrete tori in $dgeq2$ dimensions. Other results apply to nonreversible walks and also generalize previous theorems of Durrett and Cooper et al. Slight extensions of these results apply to voter model consensus times, which are related to coalescing random walks via duality. Our main proof ideas are a strengthening of the usual approximation of hitting times by exponential random variables, which give results for nonstationary initial states; and a new general set of conditions under which we can prove that the hitting time of a union of sets behaves like a minimum of independent exponentials. In particular, this will show that the first meeting time among $k$ random walkers has mean $approxmathsf{m}(G)/bigl({matrix{k 2}}bigr)$.
Let $X$ be the constrained random walk on $mathbb{Z}_+^d$ $d >2$, having increments $e_1$, $-e_i+e_{i+1}$ $i=1,2,3,...,d-1$ and $-e_d$ with probabilities $lambda$, $mu_1$, $mu_2$,...,$mu_d$, where ${e_1,e_2,..,e_d}$ are the standard basis vectors. Th
e process $X$ is assumed stable, i.e., $lambda < mu_i$ for all $i=1,2,3,...,d.$ Let $tau_n$ be the first time the sum of the components of $X$ equals $n$. We derive approximation formulas for the probability ${mathbb P}_x(tau_n < tau_0)$. For $x in bigcup_{i=1}^d Big{x in {mathbb R}^d_+: sum_{j=1}^{i} x(j)$ $> left(1 - frac{log lambda/min mu_i}{log lambda/mu_i}right) Big}$ and a sequence of initial points $x_n/n rightarrow x$ we show that the relative error of the approximation decays exponentially in $n$. The approximation formula is of the form ${mathbb P}_y(tau < infty)$ where $tau$ is the first time the sum of the components of a limit process $Y$ is $0$; $Y$ is the process $X$ as observed from a point on the exit boundary except that it is unconstrained in its first component (in particular $Y$ is an unstable process); $Y$ and ${mathbb P}_y(tau< infty)$ arise naturally as the limit of an affine transformation of $X$ and the probability ${mathbb P}_x(tau_n < tau_0).$ The analysis of the relative error is based on a new construction of supermartingales. We derive an explicit formula for ${mathbb P}_y(tau < infty)$ in terms of the ratios $lambda/mu_i$ which is based on the concepts of harmonic systems and their solutions and conjugate points on a characteristic surface associated with the process $Y$; the derivation of the formula assumes $mu_i eq mu_j$ for $i eq j.$
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
