2025/08/26 by Amir, Gideon, Nazarov, Fedor, Peres, Yuval · 1 citation
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2508.19411
We consider the following dynamics on a connected graph (V,E) with n vertices. Given p>1 and an initial opinion profile f0:V → [0,1], at each integer step t ≥ 1 a uniformly random vertex v=vt is selected, and the opinion there is updated to the value ft(v) that minimizes the sum ∑w ∼ v |ft(v)-ft-1(w)|p over neighbours w of v. The case p=2 yields linear averaging dynamics, but for all p ≠ 2 the dynamics are nonlinear. In the limiting case p=∞ (known as Lipschitz learning), ft(v) is the average of the largest and smallest values of ft-1(w) among the neighbours w of v. We show that the number of steps needed to reduce the oscillation of ft below ε is at most nβp (up to logarithmic factors in n and ε), where βp:=max((2p)/(p-1),3); we prove that the exponent βp is optimal. The phase transition at p=3 is a new phenomenon. We also derive matching upper and lower bounds for convergence time as a function of n and the average degree; these are the most challenging to prove.