Is there an f(x) such that P[f(a) >= f(b)] = a/(a+b) given a set of possible values for a and b?

Question

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.

Answer 1

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.