New Directions in Random Walk

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

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.