Para receber por e-mail novas publicações de Seminário de Palestra Especial, Clique Aqui!

Seminários do IMPA

Palestra Especial

Random walks on graphs: mixing times and statistical inference
Anna Ben-Hamou

Sorbonne Université
Quarta-feira, 18 de abril de 2018, 13:30
Auditorio 1

Quantifying the speed of convergence of random walks (RW) on graphs is a question of both theoretical and practical interest: fast-mixing RWs allow to sample quickly from potentially huge networks. In some situations, convergence occurs at a very precise time: the distance to equilibrium remains close to 1 for a long time and then abruptly drops to 0. This is the cutoff phenomenon. Clearly, if there is cutoff, a person interested in sampling with RWs would want to know it. Unfortunately, proving its occurrence on a given graph is often a challenging task. But one might ask: what is the mixing behavior of a RW on a “typical” graph? The first part of this talk will be devoted to this question. On sparse random graphs with given degrees, cutoff occurs with high probability, both for simple and non-backtracking RWs. In a second part, we will adopt a more statistical point of view, and ask how well and how fast RWs can help estimating parameters of a given graph, such as its size. If the mixing time t_mix is known, then a simple scheme consists in using the endpoints of K independent RWs of length t_mix and resorting to classical methods for IID samples, such as collision counting. We will show that using the whole trajectories of RWs and not just their endpoint may significantly improve the performances of estimation, by designing estimators (based on intersections between RWs’ paths), which are shown to achieve optimal time complexity. The results which will be presented come from joint works with several authors: Eyal Lubetzky, Roberto Oliveira, Yuval Peres, Justin Salez.