Order statistics in population protocols via simple dynamics

We study simple dynamics in the population protocol model, in which 𝑛 agents start with totally ordered initial opinions 𝑥1, 𝑥2, . . . , 𝑥𝑛 and, in each round, a randomly chosen agent changes its opinion as a function of the opinion of other randomly chosen agents. Such dynamics often converge to consensus on a single fixation value 𝑋ˆ. This paper asks how to control the distribution of 𝑋ˆ as a randomised choice among the initial opinions by designing suitable simple dynamics. Writing the sorted initial values as 𝑥(1) ≤ · · · ≤ 𝑥(𝑛) , we design two protocols that realise natural target laws over order statistics. First, for a parameter 𝑝 ∈ (0, 1), our geometric protocol biases toward larger opinions and satisfies P 𝑋ˆ = 𝑥(𝑘) ∝ 𝑝 𝑛−𝑘 , for 𝑘 = 1, . . . , 𝑛. Equivalently, P 𝑋ˆ = 𝑥(𝑘) = (1 − 𝑝)𝑝 𝑛−𝑘 /(1 − 𝑝 𝑛 ). Second, our binomial protocol assigns a shifted binomial law to the ranks in ascending order: if 𝐾 −1 ∼ Bin(𝑛−1, 1−𝑝), then 𝑋ˆ = 𝑥(𝐾) , i.e., P 𝑋ˆ = 𝑥(𝑘) = 𝑛−1 𝑘−1
𝑝 𝑛−𝑘 (1 − 𝑝) 𝑘−1 , for 𝑘 = 1, . . . , 𝑛. Applications of this include computing the Top-𝑘 values for small 𝑘 on general interaction graphs. A central contribution of this work is that, in contrast to most population protocols, we can characterise the fixation distribution in closed form. This is enabled by a novel analysis technique, which also yields applications: we derive new results for the Median protocol that extend the state of the art.