New Directions in Random Walk

随机游走的新方向

• 批准号: 1162172
• 负责人: Peter Winkler
• 金额: $ 33.93万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-06-01 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1162172&HistoricalAwards=false
• 关键词: New; Directions; Random; Walk

The PI will open and pursue several new areas of research in random walks on graphs. Among them are expected time for a random walk or Brownian particle to cover all the edges of a network; coupling of random walks in order to avoid collisions; strategies for searching and patrolling graphs; and some new ideas on "mixing time," that is, the time required for a random walk to reach a random state. The random walk on a graph has been a fundamental construction in discrete probability. The concept has numerous applications in computer science and statistical physics, and a strong connection to the theory of electrical networks. The proposed work has additional possible applications to disparate fields such as software design and policing; it brings game theory, as well as combinatorics and probability, into the random walk picture.

PI将在图上的随机游动中开辟和追求几个新的研究领域。其中包括随机游动或布朗粒子覆盖网络所有边的预期时间；为避免碰撞而耦合的随机游动；搜索和巡视图的策略；以及关于“混合时间”的一些新想法，即随机游动达到随机状态所需的时间。图上的随机游动一直是离散概率的一个基本结构。这一概念在计算机科学和统计物理中有许多应用，并与电子网络理论有很强的联系。拟议中的工作还可能应用于不同的领域，如软件设计和警务；它将博弈论以及组合学和概率论引入随机游走的图景。