# Random Walks on Random Networks @ BMC 2016

﻿

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