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.



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


