Algorithmic Aspects of Markov Processes and Their Applications.

par Nhat-Thang Le

jeudi 30 oct. 2025, 15:00 → 18:00 Europe/Paris

Amphithéâtre 4 (TSE)

This thesis presents two applications of Markov processes.

The first part focuses on finite optimization, where we propose a new swarm dynamic formulated in the framework of nonlinear Markov chains. This dynamic serves as the foundation for a particle approximation algorithm designed to approximate the nonlinear Markov evolution. The underlying idea is that the interacting particles progressively concentrate on the set of optimizers of the target function. A key result we establish is that, by choosing a temperature schedule of the form βt ≈ t^α with α∈(0,1/2), the measure of the set of global optimizers converges to 1. This contrasts with the classical ln(t) temperature schedule used in simulated annealing algorithms.

The second part introduces a novel and efficient algorithm for computing both the value function and the Nash equilibrium in a class of zero-sum optimal stopping games involving two players, commonly known as Dynkin games. In such games, the players observe the evolution of a Markov process on a finite state space and may choose to stop the game at any time. When the game stops, a payoff is made from one player to the other. The proposed algorithm demonstrates strong practical efficiency and opens a promising direction for future applied research, complementing the already well-established theoretical literature on this topic. In particular, the algorithm terminates in strictly fewer than N^2 steps, where N denotes the size of the underlying state space. Moreover, each step requires only the computation of a matrix inverse, making the overall computational complexity entirely dependent on that of matrix inversion algorithms.

The thesis can be found in this link: Thesis-NhatThangLE.pdf