IS30: Mixing times for random walks

date: 7/17/2025, time: 14:00-15:30, room: IM EM

Organizer: Perla Sousi (University of Cambridge)

Chair: Dominik Schmid (University of Augsburg)

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

Zsuzsanna Baran (University of Cambridge)

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.

Mixing of a random walk on a randomly twisted hypercube

Andela Sarkovic (King’s College, Cambridge)

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

Mixing times for time-fractional processes

Nicos Georgiou (University of Sussex)

In this talk we will be discussing mixing times for time-changed Markov chains when the time change is a heavy-tailed, power law distribution. We show the usual logarithmic mixing is replaced by a power law whose exponent is the tail index. While some generic results and bounds hold for arbitrary time-change distributions, the strongest results with matching upper and lower bounds appear when the time-change is Mittag-Leffler with index less than 1. In this case the semi-Markov processes are driven by a single fractional Poisson process. One of the interesting applications (and some of the open questions) are the mixing times and relaxation times to equilibrium of fractional queueing systems.

This is joint work with Enrico Scalas and Jacob Butt (University of Rome -La Sapienza)