اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAsymptotic behavior of Aldous gossip process
314
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Aldous [(2007) Preprint] defined a gossip process in which space is a discrete $Ntimes N$ torus, and the state of the process at time $t$ is the set of individuals who know the information. Information spreads from a site to its nearest neighbors at rate 1/4 each and at rate $N^{-alpha}$ to a site chosen at random from the torus. We will be interested in the case in which $alpha<3$, where the long range transmission significantly accelerates the time at which everyone knows the information. We prove three results that precisely describe the spread of information in a slightly simplified model on the real torus. The time until everyone knows the information is asymptotically $T=(2-2alpha/3)N^{alpha/3}log N$. If $rho_s$ is the fraction of the population who know the information at time $s$ and $varepsilon$ is small then, for large $N$, the time until $rho_s$ reaches $varepsilon$ is $T(varepsilon)approx T+N^{alpha/3}log (3varepsilon /M)$, where $M$ is a random variable determined by the early spread of the information. The value of $rho_s$ at time $s=T(1/3)+tN^{alpha/3}$ is almost a deterministic function $h(t)$ which satisfies an odd looking integro-differential equation. The last result confirms a heuristic calculation of Aldous.
قيم البحث
اقرأ أيضاً
We introduce an extension of the frog model to Euclidean space and prove properties for the spread of active particles. Fix $r>0$ and place a particle at each point $x$ of a unit intensity Poisson point process $mathcal P subseteq mathbb R^d - mathbb
B(0,r)$. Around each point in $mathcal{P}$, put a ball of radius $r$. A particle at the origin performs Brownian motion. When it hits the ball around $x$ for some $x in mathcal P$, new particles begin independent Brownian motions from the centers of the balls in the cluster containing $x$. Subsequent visits to the cluster do nothing. This waking process continues indefinitely. For $r$ smaller than the critical threshold of continuum percolation, we show that the set of activated points in $mathcal P$ approximates a linearly expanding ball. Moreover, in any fixed ball the set of active particles converges to a unit intensity Poisson point process.
Aldous spectral gap conjecture asserts that on any graph the random walk process and the random transposition (or interchange) process have the same spectral gap. We prove the conjecture using a recursive strategy. The approach is a natural extension
of the method already used to prove the validity of the conjecture on trees. The novelty is an idea based on electric network reduction, which reduces the problem to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates. The proof of the latter inequality uses suitable coset decompositions of the associated matrices on permutations.
We introduce a class of stochastic processes with reinforcement consisting of a sequence of random partitions ${mathcal{P}_t}_{t ge 1}$, where $mathcal{P}_t$ is a partition of ${1,2,dots, Rt}$. At each time~$t$,~$R$ numbers are added to the set being
partitioned; of these, a random subset (chosen according to a time-dependent probability distribution) joins existing blocks, and the others each start new blocks on their own. Those joining existing blocks each choose a block with probability proportional to that blocks cardinality, independently. We prove results concerning the asymptotic cardinality of a given block and central limit theorems for associated fluctuations about this asymptotic cardinality: these are proved both for a fixed block and for the maximum among all blocks. We also prove that with probability one, a single block eventually takes and maintains the leadership in cardinality. Depending on the way one sees this partition process, one can translate our results to Balls and Bins processes, Generalized Chinese Restaurant Processes, Generalized Urn models and Preferential attachment random graphs.
We give an explicit construction of the weak local limit of a class of preferential attachment graphs. This limit contains all local information and allows several computations that are otherwise hard, for example, joint degree distributions and, mor
e generally, the limiting distribution of subgraphs in balls of any given radius $k$ around a random vertex in the preferential attachment graph. We also establish the finite-volume corrections which give the approach to the limit.
We explore an asymptotic behavior of Renyi entropy along convolutions in the central limit theorem with respect to the increasing number of i.i.d. summands. In particular, the problem of monotonicity is addressed under suitable moment hypotheses.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
