JPhysA编辑优选：随机游走覆盖时间极限分布的数学基础

JPhysA编辑优选：随机游走覆盖时间极限分布的数学基础

随机搜索过程在物理学、化学和生物学，乃至机器学习和机器人等各个学科中都具有广泛的应用。随机游走是随机搜索过程的数学模型。覆盖时间，即一个随机游走首次访问所有节点所需的时间，是描述随机搜索过程的关键参数。2015年，有研究组在Nature Physics发文，通过数值模拟发现，在很多不同的随机游走模型中，覆盖时间，当进行适当的归一化后，其极限分布都是Gumbel分布，这就意味着研究首达时间的结果都可以被应用到研究覆盖时间上来。这项工作对于理论工作者也是一个很好的提示，也许这是一个研究覆盖时间理论性质的切入口。因此本研究希望通过严格的数学分析，深入探讨环面上有限范围对称随机游走的覆盖时间，试图证明其满足2015年这项数值模拟工作中发现的规律。

研究背景

随机搜索过程在物理学、化学和生物学，乃至机器学习和机器人等各个学科中都具有广泛的应用。随机游走是随机搜索过程的数学模型。覆盖时间，即一个随机游走首次访问所有节点所需的时间，是描述随机搜索过程的关键参数。2015年，有研究组在Nature Physics发文，通过数值模拟发现，在很多不同的随机游走模型中，覆盖时间，当进行适当的归一化后，其极限分布都是Gumbel分布，这就意味着研究首达时间的结果都可以被应用到研究覆盖时间上来。这项工作对于理论工作者也是一个很好的提示，也许这是一个研究覆盖时间理论性质的切入口。因此本研究希望通过严格的数学分析，深入探讨环面上有限范围对称随机游走的覆盖时间，试图证明其满足2015年这项数值模拟工作中发现的规律。

研究内容

本研究利用严格的数学分析方法，研究了环面上有限范围对称随机游走的覆盖时间特性。数学家Belius在2013年严格证明了简单随机游走覆盖时间的这一极限性质，其证明中采用了数学家Sznitman在2009年建立的随机交织模型。其证明比较艰深复杂，涉及很多的细致估计，整个证明长达五十多页。我们在仔细研究了Belius的工作之后发现，其证明中的构造方法是可以在进行一定的改造后，推广到环面上有限范围对称随机游走模型上的；其证明中最关键的有关随机游走和随机交织模型的耦合结果，也是可以直接推广过去的。

从数学角度来看，我们的证明并没有什么特别创新的地方，很多改造也是这方面的数学专家比较容易想象得到的。但是从解释数值模拟中发现的这一现象的角度，我们的工作有其独特的价值，因为我们把环面上运动的各方面细节都研究得更深入，给出了关于覆盖时间Gumbel分布极限的一般结果，同时基本囊括了2015年的那篇文献里几乎全部数值实验，给这一普适现象提供了严格的数学基础。

作者介绍

葛颢 教授

北京大学

• 葛颢，北京大学长聘教授、国家杰青获得者。长期从事随机过程和统计学在物理、化学以及生物上的应用，在Physical Review Letters、Cell、Journal of Chemical Physics、Journal of Statistical Physics等权威期刊发表论文60余篇。获2009年中国数学会钟家庆数学奖，入选2016年教育部青年长江学者名单。