Title: A dynamical system approach to compute the transient behavior of stochastic distributed system
Let us consider a random walker over a finite grid (or torus) in dimension d. A natural question is how long does it take for the walker to have a chance to visit any state in the grid, or, more or less equivalently, how long does it take for the walker’s initial position not to matter anymore?
These questions are all related to the {\it mixing time} of the random walk: the time it takes for the probability distribution at time t, to be close (for the total variation norm) to the stationary distribution. Computing the mixing time is an important challenge in modern Markov chain theory that has been approached in many ways (spectral decomposition of the transition matrix, coupling theory, perfect simulations).
In this internship, we propose to investigate a new approach based on asymptotic arguments (by letting the space dimension d, go to infinity). This approach transforms the stochastic random walk into a deterministic dynamical system whose long run behavior can be well understood (sometimes).
This new approach can allow one to compute the mixing time of random walks that cannot to tackled using the classical tools. It is also useful fo compute the complexity of distributed randomized algorithms such as cooperative protocols in games. Finally, it can help to assess the expected time to extension of population processes with intricate dynamics (such as populations of particules under general interaction processes).
Location and supervisor
The intern will be hosted at Inria Grenoble and supervised by Nicolas Gast and Bruno Gaujal (Inria).
References:
- Computing hitting times via fluid approximation: application to the coupon collector problem. Nicolas Gast
- Differential equation approximations for Markov chains, R.W.R. Darling, J.R. Norris,
- A class of mean field interaction models for computer and communication systems. M. Benaïm, J.-Y. Le Boudec.