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

不变点过程、公平分配、随机回合博弈及应用

• 批准号: 0605166
• 负责人: Yuval Peres
• 金额: $ 33万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-01 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0605166&HistoricalAwards=false
• 关键词: Invariant; point; processes; fair; allocations

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.

这个提议描述了几个概率领域的问题，包括随机几何、马尔可夫链和随机对策。行列式点过程自然地出现在一些设置中，包括随机矩阵的特征值。该建议的一个目标是开发健壮的方法来识别不需要计算所有阶的相关函数的确定性过程。将比较两种为点过程的点分配等体积的方法，一种是基于Gale-Shapley稳定匹配算法，另一种是基于重力势。在马尔可夫链混合的领域，“截断现象”，即到平稳的距离从接近1迅速减少到接近0，被认为在大多数自然链中成立，但在极少数情况下成立。本文将研究一种鲁棒且易于检查的可能的截止准则。近年来，利用博弈论和最优控制的思想，将随机漫步和调和函数之间的经典联系扩展到非线性势理论。本文的主要目的是开发和研究随机对策，其值函数在缩放极限下求解其他重要的偏微分方程。随机散射（点过程）表现出团块在统计学中有有效的模型，但表现出排斥的随机散射却没有得到很好的理解。拟议的项目旨在更好地了解这些过程，以便在统计建模中更广泛地使用这些过程。给定一个随机的散点，不同的算法分配相等的面积到散点的点将被研究。马尔可夫链是仿真和随机化算法中广泛使用的工具。本文将研究这些链收敛到平衡点的基本特征。这些应该会对算法的分析产生影响。该项目有一个实质性的教育组成部分，在指导研究生和准备教育材料在本科水平的马尔可夫链和博弈论。