随机采样:台球漫步算法
提出了一种新的随机行走方法,用于均匀采样高维凸体;它在输出方面具有比之前已知的方法更强的保证,特别是在 Rényi 散度方面。证明与现有的问题的多项式时间算法方法不同,我们利用了随机扩散的视角,通过收敛性的速率与平稳密度的功能等周常数来显示到目标分布的收缩。
May, 2024
本文研究高维分布的取样方法,提出了基于 Gibbs Sampler 方法的 Coordinate Hit-and-Run 算法,在凸边界的范围内取样效率高且保证收敛。
Sep, 2020
研究了 $n$ 维凸体上的随机游走的混合时间,得到了一个多项式上界,并得出该问题一直存在的疑问,即坐标 Hit-and-Run 是否具有多项式混合时间。
Sep, 2020
本文探讨了非后退随机游走在正则扩张图上的混合速率问题,证明了其速率可能是简单随机游走速率的两倍,并给出了其应用,并提出了一种类似于投掷球到篮子中的方法来描述所访问的点的多集。
Oct, 2006
该研究提出并分析了两种新的 MCMC 抽样算法,即 Vaidya walk 和 John walk,用于从多面体上生成样本。其中提出的 Vaidya walk 算法的混合时间比过去的 Dikin walk 的混合时间少得多,混合时间上界为 O (n^0.5*d^1.5)。在数值例子中,Vaidya 步行的加速超过了 Dikin 步行。
Oct, 2017
我们提出了一种新的准蒙特卡洛机制,用于改进基于图的采样,称为斥力随机游走。通过在相互作用的集合中引入轨迹之间的相关性,使其边际转移概率不变,我们能够更高效地探索图,并提高统计估计量的集中度,同时保持其无偏性。该机制具有简单易用的实现方法。我们展示了斥力随机游走在估计图核、PageRank 向量和图图案集中度等各种环境中的有效性,并提供了详细的实验评估和稳健的理论保证。据我们所知,斥力随机游走是第一个对图上行走者的方向进行严格研究的准蒙特卡洛方案,在这个令人兴奋的初创领域中引发了新的研究。
Oct, 2023
对有限图上的懒惰随机游走进行了新的研究,得到了有关回归概率、最大期望击中时间、会面时间引理和多个随机游走的期望完全合并时间的新结果。
Jul, 2018
我们提出了一种新的 Monte Carlo 算法,可以通过独立的随机步骤在不同的能量范围内获得高精度的结果,并可直接计算自由能和熵,适用于一级和二级相变的研究,也可用于具有粗糙能量景观的复杂系统的研究。
Nov, 2000
本文提出了一种量子算法,在估算所有具有有界方差的任意随机或量子子程序的期望输出值方面实现了接近二次的加速,并且通过结合量子步行的使用,为计算分区函数的最快已知经典算法提供了量子加速,同时也能有效地估计概率分布之间的总变差距离。所提出的量子算法具有严格的性能边界。
Apr, 2015
本文提出了一种新的算法 Waddling Random Walk(WRW),用于估计任意大小的图相对浓度,并通过在可访问的节点路径上进行随机游走来采样子图以提高计算效率、精度与准确性。通过使用广泛使用的图形数据集,该算法在速度、精度和准确性方面都优于当前最先进的挖掘子图统计算法。
May, 2016