Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks
198
0
0.0
(
0
)
Added by
Asaf Cassel
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 uniformly} 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 environments, 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 coalesced 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 for 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
