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

点击翻译按钮获取中文摘要

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 isto develop robust methods to recognize determinantal processes that donot require calculating correlation functions of all orders. Twomethods of allocating equal volumes to the points of a point process,one based on the Gale-Shapley stable matching algorithm, the other ongravitational potentials, will be compared. In the area of Markovchain mixing, the ``cutoff phenomenon'' where distance to stationaritydecreases rapidly from near 1 to near zero is believed to hold in mostnatural chains but is established for very few. A robust and easilycheckable possible criterion for cutoff will be investigated.Recently, the classical connection between random walks and harmonicfunctions has been extended to nonlinear potential theory using ideasfrom game theory and optimal control. A major aim of the proposal is todevelop and study stochastic games whose value functions, in thescaling limit, solve other important PDE.Random scatters (Point processes) that exhibit clumping have effectivemodels in statistics, but random scatters that exhibit repulsion areless well understood. The proposed project aims to develop a betterunderstanding of such processes which should enable wider use for themin statistical modeling. Given a random scatter, different algorithmsfor allocating equal areas to the points of the scatter will beinvestigated. Markov chains are a widely used tool in simulation andrandomized algorithms. Basic features of convergence to equilibriumin these chains will be studied. These should have an impact on theanalysis of algorithms. The project has a substantial educationalcomponent, in mentoring of graduate students and preparation ofeducational materials at the undergraduate level on Markov chains andgame theory.