The problem of self-avoiding walks (SAWs) arose in statistical mechanics in the 1940s, and has connections to probability, combinatorics, and the geometry of groups. The basic question is to count SAWs. The so-called 'connective constant' is the exponential growth rate of the number of n-step SAWs. We summarise recent joint work with Zhongyang Li concerned with the question of how the connective constant depends on the choice of graph. This work includes equalities and inequalities for connective constants, and a partial answer to the so-called 'locality problem' for graphs and particularly Cayley graphs.
Self-avoiding walks on graphs and groups
Dec. 07, 2017 3pm (MATH 350)
Probability
Manuel Lladser (Applied Math, CU Boulder)
X
In this talk, I will present work in progress to approximate the distribution of so-called linear functionals of paths in Markov chains. Archetypical examples of these are sojourn-times, such as those encountered in genomic sequence analyses, telecommunication protocols, and inventory models. Approximating the distribution of linear functionals is a challenging problem in transient regimes because exact computations, as well as stationarity assumptions, are typically infeasible in such regimes. Instead, using low-rank operators and probabilistic arguments, we will see how to approximate the distribution of these functionals in total variation distance - provided the existence of a so-called “regeneration” set; in particular, this setting encompasses Harris-recurrent Markov chains. This work is in collaboration with Dr. Barrera from Universidad Adolfo Ibañez in Chile.
Non-asymptotic approximation of Markovian functionals in transient regimes