اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks
198
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We identify a fundamental phenomenon of heterogeneous one dimensional random walks: the escape (traversal) time is maximized when the heterogeneity in transition probabilities forms a pyramid-like potential barrier. This barrier corresponds to a distinct arrangement of transition probabilities, sometimes referred to as the pendulum arrangement. We reduce this problem to a sum over products, combinatorial optimization problem, proving that this unique structure always maximizes the escape time. This general property may influence studies in epidemiology, biology, and computer science to better understand escape time behavior and construct intruder-resilient networks.
قيم البحث
اقرأ أيضاً
We prove that in any finite set of $mathbb Z^d$ with $dge 3$, there is a subset whose capacity and volume are both of the same order as the capacity of the initial set. As an application we obtain estimates on the probability of {it covering uniforml
y} a finite set, and characterize some {it folding} events, under optimal hypotheses. For instance, knowing that a region of space has an {it atypically high occupation density} by some random walk, we show that this random region is most likely ball-like
We introduce a heterogeneous continuous time random walk (HCTRW) model as a versatile analytical formalism for studying and modeling diffusion processes in heterogeneous structures, such as porous or disordered media, multiscale or crowded environmen
ts, weighted graphs or networks. We derive the exact form of the propagator and investigate the effects of spatio-temporal heterogeneities onto the diffusive dynamics via the spectral properties of the generalized transition matrix. In particular, we show how the distribution of first passage times changes due to local and global heterogeneities of the medium. The HCTRW formalism offers a unified mathematical language to address various diffusion-reaction problems, with numerous applications in material sciences, physics, chemistry, biology, and social sciences.
We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random $2$-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing
that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to `true under a uniformly random satisfying assignment.
Consider a system of coalescing random walks where each individual performs random walk over a finite graph G, or (more generally) evolves according to some reversible Markov chain generator Q. Let C be the first time at which all walkers have coales
ced into a single cluster. C is closely related to the consensus time of the voter model for this G or Q. We prove that the expected value of C is at most a constant multiple of the largest hitting time of an element in the state space. This solves a problem posed by Aldous and Fill and gives sharp bounds in many examples, including all vertex-transitive graphs. We also obtain results on the expected time until only k>1 clusters remain. Our proof tools include a new exponential inequality for the meeting time of a reversible Markov chain and a deterministic trajectory, which we believe to be of independent interest.
Corroborating a prediction from statistical physics, we prove that the Belief Propagation message passing algorithm approximates the partition function of the random $k$-SAT model well for all clause/variable densities and all inverse temperatures fo
r which a modest absence of long-range correlations condition is satisfied. This condition is known as replica symmetry in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random $k$-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
