Monotone interactions of random walks and graphs
Abstract/Contents
- Abstract
- This thesis deals with the behavior of random walks on monotonically time-varying graphs, where due to this monotonicity we can establish certain universality properties. In Chapter 1, we consider normally reflected Brownian motion (RBM) and simple random walk (SRW) on independently growing-in-time d-dimensional domains, d> =3. We establish a sharp criterion for recurrence versus transience in terms of the growth rate. For more general growing subgraphs of an infinite graph, we use evolving sets to establish heat kernel bounds that yield sufficient transience/recurrence criteria. In contrast, we demonstrate rich and non-universal behavior of certain non-Markovian models of random walks, in which monotone interaction enforces domain growth as a result of visits by the walk (or probes it sent), to the neighborhood of domain boundary. This is complemented by Chapter 2, where we address stability issues for random walks among time-dependent conductances. For both the discrete-time uniformly-lazy and continuous-time constant-speed random walks (DTRW/CSRW), we show that Gaussian heat kernel estimates are not stable under perturbations. As a by-product, we refute an open question about inhomogeneous merging of finite Markov chains. We establish matching Gaussian upper and lower transition density bounds for the CSRW among time-increasing conductances on any graph satisfying a uniform-in-time Poincare inequality and volume growth regularity. In contrast, stability is known for the variable-speed random walk (VSRW), for which the counting measure is the reversing measure.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Huang, Ruojun |
|---|---|
| Associated with | Stanford University, Department of Statistics. |
| Primary advisor | Dembo, Amir |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Chatterjee, Sourav |
| Thesis advisor | Diaconis, Persi |
| Advisor | Chatterjee, Sourav |
| Advisor | Diaconis, Persi |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Ruojun Huang. |
|---|---|
| Note | Submitted to the Department of Statistics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Ruojun Huang
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...