1
$\begingroup$

I need a function $f(x)$ such that given a set of values $X=\{x1, x2, ...\}$ and a function $rand()$ that returns a value between 0 and 1, $f(x)$ returns a value that increases with x such that the probability that $f(a)$ returns a value greater than $f(b)$ is based on their relative sizes: $P[f(a) \ge f(b)] = \frac{a}{a+b} \forall\ a,b\ \epsilon \ X$

Basically, I'm trying to find a more efficient way to pick a random order of items that have associated weights that determine their probability of being picked earlier. For example, if I had items A, B, and C with weights 1, 2, and 4, respectively, the current algorithm picks a random number 1-7 and picks A if it is 1, B if it is 2 or 3, and C if it is 4-7. So, A has a 1/7 chance of being 1st, B has a 2/7 chance, and C a 4/7 chance. The picked value is removed from the set, and the algorithm repeats with the smaller set.

If I could find a way to instead map these weights to a random value such that ordering them by that value gives the same distribution of selected permutations, that would be cool.

$\endgroup$
1
  • 2
    $\begingroup$ Is saying that there's a 1/7 chance that $f(1)$ is the largest the same thing as saying that $f(1)\gt f(2)$ with probability 1/3 and $f(1)\gt f(4)$ with probability 1/5 (as you seem to imply)? And do you want $a/(a+b)$, as in the body, or $a/b$, as in the title? I vote to close, pending clarification. $\endgroup$ Feb 2, 2011 at 11:55

1 Answer 1

5
$\begingroup$

If I interpret your question correctly, the answer is that the exponential random variable $\xi$ (density $e^{-x}$) has the property that for two independent copies $\xi_1,\xi_2$ of $\xi$, one has $P(a\xi_1\le b\xi_2)=\int_{y_1\le ry_2}e^{-y_1-y_2}dy_1dy_2=\frac r{1+r}$ with $r=\frac ba$, which is exactly what you wanted (in the first paragraph, at least; the second paragraph problem is completely different from the first paragraph one; I hope you realize that). To convert the uniform variable into the exponential, just take the natural logarithm.

Edit: OK, since you modified the question, I'll modify the answer. The exponential distribution still works but with a twist. Suppose that your weights are $x_1,\dots,x_n$. The probability of the order $1,2,\dots,n$ with your current algorithm is $\prod_{j=1}^n\frac{x_j}{\sum_{k=j}^n x_k}$. Now take $Y_j=x_j^{-1}\xi_j$ and compute the probability that $Y_1<Y_2<\dots<Y_n$. $Y_j$ has density $p_j(t)=x_je^{-x_jt}$. So, the desired probability is $\int_{y_1<y_2<\dots<y_n}x_1x_2\dots x_ne^{-x_1y_1+x_2y_2+x_3y_3+\dots+x_ny_n}dy_1\dots dy_n$. If you now start integrating from $y_n$ down, you'll get the same expression. Thus, you can reduce your simulation to computing logarithms of $n$ uniform on $[0,1]$ random variables, dividing the resulting negative numbers by the weights and sorting.

$\endgroup$
1
  • $\begingroup$ Thank you! This has made my code much simpler and way more efficient. $\endgroup$
    – Dan Barry
    Feb 5, 2011 at 1:30

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.