{"id":"arxiv/2603.20060","url":"https://arxiv.org/abs/2603.20060","tags":["cs.DS","math.PR"],"score":0,"title":"Power laws and power-of-two-choices","domain":"cs.DS","source":"arxiv","authors":["Amanda Redlich"],"reviews":0,"subject":"cs.DS","summary":"This paper analyzes a variation on the well-known \"power of two choices\" allocation algorithms. Classically, the smallest of $d$ randomly-chosen options is selected. We investigate what happens when the largest of $d$ randomly-chosen options is selected. This process generates a power-law-like distribution: the $i^{th}$-smallest value scales with $i^{d-1}$, where $d$ is the number of randomly-chosen options, with high probability. We give a formula for the expectation and show the distribution is concentrated around the expectation","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-20","reactions":{}}