Random Walks on Random Networks @ BMC 2016



We gratefully acknowledge funding from the EPSRC and the University of Bristol. Whether you are attending the BMC or not, there is no need to register, but send us an email if possible.

This satellite meeting well be held on March 24th 2016 (afternoon session, starting 1:30pm) in the Verdon-Smith room, Royal Fort House.

13:30: tba
Mathew Penrose (Bath)

14:00: Random walks on random graphs
Nathanaël Berestycki (Cambridge)

We study random walks on the giant component of the Erdos-Renyi random graph G(n, p) where p = c/n for c > 1 fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order log^2 n. We prove that by contrast, when started from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant component) mixing occurs both quicker and in a more concentrated fashion: in particular we show that the cutoff phenomenon occurs. The mixing time is (1/vd) log n ± (log n)^{1/2+o(1)}, where v and d are the speed of random walk and dimension of harmonic measure on a Poisson(c)-Galton-Watson tree.

14:40: Electric network for non-reversible Markov chains
Márton Balázs (Bristol) - Joint work with Áron Folly

There is a well-known analogy between reversible Markov chains and electric networks: the probability of reaching one state before another agrees with voltages in a corresponding network of resistances, and the electric current also has a probabilistic interpretation. Such analogies can be used to prove a variety of theorems regarding transience-recurrence, commute times, cover times. The electric counterpart is very simple, consists of resistors only. These simple components behave in a symmetric fashion, that's why the analogy only works for reversible chains.

We found the electric component that allows to extend the above analogy from reversible Markov chains to irreversible ones. I will describe this new component, show how the analogy works, demonstrate some arguments that can be saved from the reversible case. I will also show how Rayleigh's monotonicity principle fails in our case, and interpret a recent non-reversible result of Gaudillière and Landim on the Dirichlet and Thomson variational principles in the electrical language.

15:10: tba
Ernesto Estrada (Strathclyde)

16:00: The half plane UIPT is recurrent
Gourab Ray (Cambridge)

We prove that a uniform infinite planar triangulation with a boundary (half plane UIPT) is recurrent. This extends the result of Nachmias and Gurel Gurevich that the full plane UIPT is recurrent. The proof introduces a layer decomposition of the half plane UIPT and circle packing theory. Joint work with Omer Angel.

16:30: Geodesic paths in random wireless networks
Alexander Kartun-Giles (Bristol)

17:00 tba
Georgie Knight (Bristol)




To contact the organisers, please send us an email.

Mountain View