Randomly order data with weights

jessexknight 0
Viewed 13

I have some data x = 1:10 and weights w = 1:10. I want to generate a randomly re-ordered version of x (all 10 elements), where the order is weighted by w. For example, the x[10] should have 10-times the probability of appearing first vs x[1].

One approach is to sample elements one-at-a-time, each time with weights w (adjusted for non-replacement), but obviously this is slow. Another approach could use the integer weights (special case) as follows:

x[order(match(x,sample(rep(x,w))))]

but this scales badly in memory. FWIW this implementation replicates each x[i] w[i] times, then shuffles this randomly. Then, finds the first occurrence of each x[i] in the replicated data and uses this to define the final order.

Question: How can I efficiently, randomly order x with (non-integer) weights w?

random r
1 Answers

It turns out, the sample function, with replace=FALSE, size=length(x) (default), and prob=w as the weights, seems to naturally order the result by weights w, presumably due to some internal procedure like the first case described above, which is still implemented in a fast way.

So, it's as simple as: sample(x,prob=w)

As a simple illustration, we can plot the mean values over a large number (1e4) of repetitions:

set.seed(0)
X = sapply(1:1e4,function(z){ sample(x,prob=w) })
plot(rowMeans(X))

which is monotonic (although not linear) decreasing, as expected. Aside: It's not linear because a w = 9 vs w = 10 has less influence compared to w = 1 vs w = 2. To get the linear result we can use weights a^w for any exponent base a.

jessexknight0
Related