论文标题
通过随机近似和马尔可夫进程的逻辑收敛定律
Logical convergence laws via stochastic approximation and Markov processes
论文作者
论文摘要
由于Soda'05的Kleinberg和Kleinberg的论文证明，具有退化的优先附着随机图至少3并不遵守第一阶0-1 Law，因此没有开发一般方法来研究具有任意变性模型的递归随机图形逻辑限制法律。即使在（可能是最简单的）统一附件的情况下，仍然不知道该模型中的一阶收敛定律是否存在。我们证明，统一的附件随机图遵守一阶收敛定律。为了证明法律，我们使用马尔可夫链描述了随机图的一阶等效类的动力学。收敛定律遵循考虑的马尔可夫链的极限分布的存在。为了显示后一种收敛，我们使用随机近似过程。
Since the paper of Kleinberg and Kleinberg, SODA'05, where it was proven that the preferential attachment random graph with degeneracy at least 3 does not obey the first order 0-1 law, no general methods were developed to study logical limit laws for recursive random graph models with arbitrary degeneracy. Even in the (possibly) simplest case of the uniform attachment, it is still not known whether the first order convergence law holds in this model. We prove that the uniform attachment random graph with bounded degrees obeys the first order convergence law. To prove the law, we describe dynamics of first order equivalence classes of the random graph using Markov chains. The convergence law follows from the existence of a limit distribution of the considered Markov chain. To show the latter convergence, we use stochastic approximation processes.
