# 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.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**.