0
$\begingroup$

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$.

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

1 Answer 1

1
$\begingroup$

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

(see https://en.wikipedia.org/wiki/Weibull_distribution#Reparametrization_tricks)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.