Mark Kempton (Harvard University)

Event Details

Title: Variations on Random Walk on Graphs

Abstract: Random walks on graphs are the basis of many algorithms involved in communication and computing theory, and have become a central area of research in graph theory.  Many variants of random walks have been studied on graphs.  I will give an overview of the theory of random walks on graphs, and describe some of these variants.  In particular, there is a growing literature studying non-backtracking random walks on graphs.  These are random walks that do not return to the immediately previous vertex in a graph.  I will discuss some of my results on non-backtracking random walks on graphs, and give a variant on a classical result from probability.