# Weighted winner selection in distributed lottery

I have a question that emerged from a programming problem: I need to select a winner among $$n$$ participants with probability proportional to integer weights $$w_1,\dots,w_n$$. Each participant can generate uniform random variables, but I cannot combine these variables or pick among them. Importantly, this means I can't just use one uniform random variable and pick a winner according to $$\frac{w_j}{\sum_i w_i}$$.

My current approach is to have every participant $$i$$ generate $$w_i$$ random variables $$u_{i,1},\dots,u_{i,j},\dots,u_{i,w_i} \sim U(0,1)$$ $$\forall i, j$$ and then pick the winner according to who has the highest number $$i^*=\arg\max_i \max_j u_{i,j}$$. But this requires $$O\left(\sum_i w_i\right)$$ computations. My question is whether there is a way to get this down to $$O(n)$$.

So I'm looking for some transformation $$f(u,w)$$ that takes the weight $$w_i$$ of one participant (edit: it would be ok to also use the total $$\sum_i w_i$$, but if it can be avoided, great) and one uniform random variable $$u_i$$ for that participant and transforms it $$v_i = f(u_i,w_i)$$ such that

$$\mathbb{P}\left(v_i \ge v_j \forall j \in 1,\dots, n\right) = \frac{w_i}{\sum_j w_j}$$

My first thought was to just multiply $$f(u,w)=u\cdot w$$, but that doesn't work: if we have two participants with weights $$w_1=1$$ and $$w_2=2$$, then $$v_1 \sim U(0,1)$$ and $$v_2 \sim U(0,2)$$, but $$\mathbb{P}(v_1\ge v_2) = 0.25 \ne 1/3$$.

• It seems like you are looing for a way to efficiently sample from a categorial distribution with given probabilities $p_i$. Look here Mar 26, 2023 at 13:06

With a single random uniform, $$u_i$$, from each participant, select

$$\arg\max_i\bigg(\frac{\log(u_i)}{w_i}\bigg)$$

Or equivalently,

$$\arg\max_i\Big(u_i^{1/w_i}\Big)$$

Testing with a quick simulation in R:

n <- 6L
w <- 1:n
tabulate(max.col(t(matrix(log(runif(1e6L*n)), n)/w)), n)/1e6
#> [1] 0.047665 0.094986 0.142365 0.189983 0.238822 0.286179
tabulate(max.col(t(matrix(runif(1e6L*n), n)^(1/w))), n)/1e6
#> [1] 0.047389 0.095431 0.142469 0.191077 0.238128 0.285506
w/sum(w)
#> [1] 0.04761905 0.09523810 0.14285714 0.19047619 0.23809524 0.28571429

• thank you! should this be $\arg \min$ instead of $\max$? Apr 1, 2023 at 16:03
• No. $\log(u_i)<0$, so larger $w_i$ will tend to be be less negative (larger). Apr 1, 2023 at 23:04
• ah right, thank you! Apr 3, 2023 at 18:11