Sep, 2010

可逆随机游走的凝聚时间

PDF
TL;DR研究了一种随机漫步的聚合系统，其中每个个体都在有限图 G 上进行随机漫步，或者（更一般地）按照某个可逆马尔可夫链生成器 Q 进行演变，证明了所有漫步者聚合成单个群集的时间 C 的期望值最多仅为状态空间中某个元素的最大碰撞时间的常数倍，并且提出了关于仅剩下 k>1 个群集的预期时间的结果。
coalescing random walksreversible markov chainconsensus timehitting timemeeting time
发现论文，激发创造
  • 关于图中的合并时间 —— 何时合并速度与相遇速度一样快？

    该研究提出了一种强大的工具包，用于估计具有共同随机行走和混淆时间的随机游走在无向图上的汇聚时间和会合时间，并对相似类别的图形的汇聚时间和会合时间进行了完整的探索。

    Nov, 2016

  • 随机漫步汇聚的平均场条件

    本文研究了有限图上合并随机行走的完全合并时间 C，提出了 mean meeting time 和 mixing times 的充分条件，得出了类似于大型完整图的定律。证实均场行为可在混合时间远小于 mean meeting time 的所有顶点可转移图中出现，并且扩展到非翻转游走和选民模型共识时间。

    Sep, 2011

  • 图上的随机游走：关于撞击、会合、汇合和返回的新界限

    对有限图上的懒惰随机游走进行了新的研究，得到了有关回归概率、最大期望击中时间、会面时间引理和多个随机游走的期望完全合并时间的新结果。

    Jul, 2018

  • 顶点增强随机游动

    本文研究了一类有限状态空间上的非 Markov 离散随机过程，探讨了状态访问次数和先验概率矩阵对转移概率的影响以及分数占用向量的极限行为，证明了极限点集合为满足某些特定条件的二次型的临界点集，具有一定的概率极限，否则极限为 0。

    Apr, 2004

  • 近似计算可逆马尔可夫链的平稳分布

    本文研究马尔可夫链的状态下的稳态概率，并提出一种简单的随机近似算法，以突破小稳态概率难以求解的难题，基于这种方法，可以有效地减少复杂度和计算时间。

    Dec, 2017

  • 度相关随机块模型中的密度演化

    本文考虑二元随机块模型，研究平均误分类顶点的最小分数，结果表明，当群集大小平衡且 μ≠ν 时，平均误分类顶点数量的最小分数由 Q（sqrt（v *））给出，并由局部算法（即置信传播）在边数线性时间内实现，证明技巧基于将群集恢复问题与树重建问题相连，分析置信传播在具有高斯近似的树上的密度演化。

    Sep, 2015

  • 无序网络上选民模型的解析解

    本文将选民模型动力学在异质网络上进行了数学描述，研究得到平均度数为 μ≤2 时系统会指数快速地达到完全有序状态；μ>2 时，则会在完全有序状态之前陷入一个平均密度恒定的准稳态，并且研究了系统的平均寿命时间。

    Mar, 2008

  • 大型图中的命中和通勤时间经常是具有误导性的

    本文研究了大型随机图中击中时间和通勤距离的行为，证明了随着顶点数的增加，击中时间和通勤距离趋于某些表达式，这些表达式不考虑图的全局结构。在随机几何图和具有预期度数的随机图中得出的结论在击中和通勤时间等方面会导致误导性。

    Mar, 2010

  • 一种非马尔可夫算法的覆盖时间研究

    本文以理论角度为出发点，研究负反馈策略在遍历算法中的应用，论证该方法可以在任意图中提高搜索效率，并对经典 UCB 和 MCTS 算法提供新的见解。

    Jun, 2023

  • 一般图上的自我排斥随机游走 - 通过非线性马尔可夫链实现最小采样方差

    通过自反随机游走（SRRW）设计的随机游走者，结合采样和邻域探索的马尔可夫链蒙特卡罗（MCMC）过程，近似目标分布，并在一定程度上提高采样方差

    May, 2023