IS30: Mixing Times for Random Walks

Organizer: Perla Sousi (University of Cambridge)

Mixing of a random walk on a randomly twisted hypercube

Andela Sarkovic

Inspired by the work of Benjamini et al \([1]\) we study, the mixing properties of a simple or lazy random walk on a twisted hypercube. In both cases, we establish the order of the mixing time and prove that the model does not exhibit cutoff.

Bibliography

\([1]\) Itai Benjamini, Yotam Dikstein, Renan Gross, and Maksim Zhukovskii Randomly twisted hypercubes – between structure and randomness Random Structures & Algorithms

Random walk on the small-world network model in 3 or more dimensions

Zsuzsanna Baran

Recently there has been an increasing interest in studying mixing properties of random graphs that have an underlying structure and some smaller random perturbation.

In this paper we consider a ‘small-world network model’ introduced by Dyer et al \([1]\), which is meant to resemble real-world networks with an underlying spatial structure and random connections whose probability decays with distance. We start with a torus \(\mathbb{Z}_n^d\), and for each pair \((x,y)\) of different vertices, we add an edge between them with probability \(p_{x,y}=\frac{Z}{|x-y|^d}\) independently, where \(Z\) is chosen such that the expected number of added edges is 1 for each vertex.

We study a lazy or non-lazy simple random walk on this random graph in the \(d\ge3\) case and we show that with high probability its \(\varepsilon\)-mixing time is of order \(\log n\) for any \(\varepsilon\in(0,1)\), and there is no cutoff.

Joint work with Andjela Šarković, Jonathan Hermon, Allan Sly and Perla Sousi.

Bibliography

\([1]\) Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda. Random walks on small world networks. ACM Transactions on Algorithms, 2020.