A leader-election procedure using records
Alsmeyer, Kabluchko, Marynych · math.PR · 2016-11-14 · 原文
The study of the number of collisions in a Poisson-Dirichlet coalescent leads to the analysis of the following version of a stochastic leader-elec\-tion algorithm. Consider an infinite family of persons, labeled by 1,2,3,\ldots, who generate iid random numbers from an arbitrary continuous distribution. Those persons who have generated a record value, that is, a value larger than the values of all previous persons, stay in the game, all others must leave. The remaining persons are relabeled by 1,2,3,\ldots maintaining their order in the first round, and the election procedure is repeated independently from the past and indefinitely. We prove limit theorems for a number of relevant functionals for this procedure, notably the number of rounds T(M) until all persons among 1,\ldots,M, except the first one, have left (as M\to\infty). For example, we show that the sequence (T(M)-\log^{*}M)_{M\in\mathbb{N}}, where \log^{*} denotes the iterated logarithm, is tight, and study its weak subsequential limits. We further provide an appropriate and apparently new kind of normalization (based on tetrations) such that the original labels of persons who stay in the game until round n
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
The study of the number of collisions in a Poisson-Dirichlet coalescent leads to the analysis of the following version of a stochastic leader-elec\-tion algorithm.
Consider an infinite family of persons, labeled by 1,2,3,\ldots, who generate iid random numbers from an arbitrary continuous distribution.
2. 领域脉络
本文类目：math.PR，属于其所在研究脉络的最新进展。
3. 机制拆解
Those persons who have generated a record value, that is, a value larger than the values of all previous persons, stay in the game, all others must leave.
4. 证据与数字
The remaining persons are relabeled by 1,2,3,\ldots maintaining their order in the first round, and the election procedure is repeated independently from the past and indefinitely.
We prove limit theorems for a number of relevant functionals for this procedure, notably the number of rounds T(M) until all persons among 1,\ldots,M, except the first one, have left (as M\to\infty).
5. 反例与边界
For example, we show that the sequence (T(M)-\log^{*}M)_{M\in\mathbb{N}}, where \log^{*} denotes the iterated logarithm, is tight, and study its weak subsequential limits.
6. 跨领域连接与意外收获
思考本文机制能否迁移到你正在跟进的问题。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。