In this paper, which is a culmination of our previous research efforts, we provide a general framework for studying mixing profiles of non-backtracking random walks on dynamic random graphs... Show moreIn this paper, which is a culmination of our previous research efforts, we provide a general framework for studying mixing profiles of non-backtracking random walks on dynamic random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. With the help of coupling arguments we show that the link is provided by the probability that the random walk has not yet stepped along a previously rewired edge.To demonstrate the utility of our framework, we rederive our earlier results on mixing profiles for global edge rewiring under weaker assumptions, and extend these results to an entire class of rewiring dynamics parametrised by the range of the rewiring relative to the position of the random walk. Along the way we establish that all the graph dynamics in this class exhibit the trichotomy we found earlier, namely, no cut-off, one-sided cut-off or two-sided cut-off.For interpolations between global edge rewiring, the only Markovian graph dynamics considered here, and local edge rewiring (i.e., only those edges that are incident to the random walk can be rewired), we show that the trichotomy splits further into a hexachotomy, namely, three different mixing profiles with no cut-off, two with one-sided cutoff, and one with two-sided cut-off. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk. Show less
This thesis concerns the mathematical analysis of certain random walks in a dynamic random environment. Such models are important in the understanding of various models in physics, chemistry and... Show moreThis thesis concerns the mathematical analysis of certain random walks in a dynamic random environment. Such models are important in the understanding of various models in physics, chemistry and biology. The interest is in questions such as how to determine the average velocity of the random walker and how to control fluctuations and deviations thereof. This is in general a very challenging problem due to the possibility of strong dependence both in space and time, and many problems are still wide open. After a general introduction in Chapter 1, we present several approaches for determining the asymptotic behaviour for random walks in a dynamic random environment in Chapter 2-5 of this thesis. Our work improves on the existing literature for general models with strongly mixing dynamics and provides new insight for certain models with poorly mixing dynamics. One particular model is analysed in more detailed, namely the so-called contact process. This model is a prototype of a dynamic random environment with poor mixing properties. In addition to results for certain random walks with the contact process as dynamic random environment, we also provide new insight for the contact process itself, given in Chapter 5. Show less
This thesis is dedicated to the study of random walks in dynamic random environments. These are models for the motion of a tracer particle in a disordered medium, which is called a static random... Show moreThis thesis is dedicated to the study of random walks in dynamic random environments. These are models for the motion of a tracer particle in a disordered medium, which is called a static random environment if it stays constant in time, or dynamic otherwise. The evolution of the random walk is defined by assigning to it random jump rates which depend locally on the random environment. Such models belong to the greater area of \emph{disordered systems}, and have been studied extensively since the early seventies in the physics and mathematics literature. The goal is to understand the scaling properties, as time goes to infinity, of the path of the random walk. Several results are available in the literature for dynamic random environments which are uniformly elliptic and have uniform and fast enough mixing in space-time. However, very little is known when either of these conditions fail. In this thesis, we study examples of such situations, namely, non-elliptic cases in Chapter 2, a dynamic random environment with fast but non-uniform mixing in Chapter 4, and a dynamic random environment with both slow and non-uniform mixing in Chapters 3 and 5. Show less