Random Walks On Metric Measure Spaces
In this thesis, we study transition probability estimates for Markov chains and their relationship to the geometry of the underlying state space. The thesis is divided into two parts. In the first part (Chapter 1) we consider Markov chains with bounded range, that is there exists R > 0 such that the Markov chain (Xn )n∈N satisfies d(Xn , Xn+1 ) < R for all n ∈ N). In the second part (Chapter 2 and 3) we consider Markov chains with heavy-tailed jumps. In Chapter 1, we characterize Gaussian estimates for transition probability of a discrete time Markov chain in terms of geometric properties of the underlying state space. In particular, we show that the following are equivalent: 1. Two sided Gaussian bounds on heat kernel 2. A scale invariant Parabolic Harnack inequality 3. Volume doubling property and a scale invariant Poincar´ inequality. e The underlying state space is metric measure space that includes both manifolds and graphs as special cases. Various applications and examples are provided. An important feature of our work is that our techniques are robust to small perturbations of the underlying space. In Chapter 2, we study the long-term behaviour of random walks with heavy tailed jumps. We focus on the case where the 'index of tail heaviness' (or jump index) [beta] ∈ (0, 2). Extending several existing work by other authors, we prove global upper and lower bounds for n-step transition probability density that is sharp up to constants. In Chapter 3, we study random walks with heavy tailed jumps where the index of tail heaviness [beta] is allowed to take any positive value. We assume that the state space in this case is a graph satisfying a sub-Gaussian estimate, which is typical of many fractal-like graphs. On such graphs, we establish a threshold behavior of heavy-tailed Markov chains when the index governing the tail heaviness equals the escape time exponent of the simple random walk. In a certain sense, this generalizes the classical threshold corresponding to the second moment condition. This thesis is based on joint work with Laurent Saloff-Coste.
Markov chains; transition probability estimates; anomalous diffusion
Ph.D. of Applied Mathematics
Doctor of Philosophy
dissertation or thesis