2022/08/29 by Christian Gorski, Gorski, Christian · 1 citation
Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2208.13922
openalex publication_date 2022/08/29 · openalex created_date 2022/09/01 · openalex updated_date 2026/07/28
In 1993 van den Berg and Kesten proved a strict monotonicity theorem for first passage percolation on ℤd, d ≥ 2: given two probability measures ν and ν with finite mean, if ν is strictly more variable than ν and ν is subcritical in an appropriate sense, the time constant associated to ν is strictly smaller than the time constant associated to ν. In this paper, an analogous result is proven for (not necessarily almost-transitive) graphs of strict polynomial growth and for bounded degree graphs quasi-isometric to trees which satisfy a certain geometric condition we call "admitting detours." It is also proven that if a bounded degree graph does not admit detours, then such a strict monotonicity theorem with respect to variability cannot hold. Large classes of graphs are shown to admit detours, and we conclude that for example any Cayley graph of a virtually nilpotent group which is not isomorphic to the standard Cayley graph of ℤ satisfies strict monotonicity with respect to variability, as does any Cayley graph of F \rtimes Fk, F a nontrivial finite group and Fk a free group. Moreover, it is proven that for graphs of strict polynomial growth and bounded degree graphs quasi-isometric to trees, if the weight measure is subcritical in an appropriate sense, then it is "absolutely continuous with respect to the expected empirical measure of the geodesic." This implies a strict monotonicity theorem with respect to stochastic domination of measures, whether or not the graph admits detours.