Invariant point processes, fair allocations, random-turn games and applications

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

This proposal describes problems in several areas of probability, involving stochastic geometry, Markov chains, and stochastic games. Determinantal point processes arise naturally in several settings, including eigenvalues of random matrices. One goal of the proposal is to develop robust methods to recognize determinantal processes that do not require calculating correlation functions of all orders. Two methods of allocating equal volumes to the points of a point process, one based on the Gale-Shapley stable matching algorithm, the other on gravitational potentials, will be compared. In the area of Markov chain mixing, the ``cutoff phenomenon'' where distance to stationarity decreases rapidly from near 1 to near zero is believed to hold in most natural chains but is established for very few. A robust and easily checkable possible criterion for cutoff will be investigated. Recently, the classical connection between random walks and harmonic functions has been extended to nonlinear potential theory using ideas from game theory and optimal control. A major aim of the proposal is to develop and study stochastic games whose value functions, in the scaling limit, solve other important PDE. Random scatters (Point processes) that exhibit clumping have effective models in statistics, but random scatters that exhibit repulsion are less well understood. The proposed project aims to develop a better understanding of such processes which should enable wider use for them in statistical modeling. Given a random scatter, different algorithms for allocating equal areas to the points of the scatter will be investigated. Markov chains are a widely used tool in simulation and randomized algorithms. Basic features of convergence to equilibrium in these chains will be studied. These should have an impact on the analysis of algorithms. The project has a substantial educational component, in mentoring of graduate students and preparation of educational materials at the undergraduate level on Markov chains and game theory.