1

This question is extension of the question below the link.

Weighted random numbers

My question is sampling weighted random number with additional condition that the weights of each element are dynamically changed frequently.

EDIT Suppose there are N elements to pick with different weights.

For static weights, Walker's alias method requires O(N) time to setup the alias but sampling cost is O(1) so it is one of the best to achieve my goal.

And binary search method requires also O(N) to make cumulative array and sampling cost is log(N)

However in my case, because the weights are frequently changed, the time complexity to modifying weights is also important.

So I want to know there are existing library or algorithm with the time complexity for both modifying the data structure and sampling less than O(N).

EDIT While I read the comments, I realize I need to impose additional conditions. Each modification phase, only few numbers(mostly two) of weights are modified, also those modifications does not change the total sum of weight(normalization condition).

If there is a solution, I also want to know if it can be used when the weights are real numbers too.

Community
  • 1
  • 1
Sungmin
  • 2,499
  • 3
  • 26
  • 32
  • N is the number of elements/ In the link, N =3 { 1, 2, 3} – Sungmin Jun 14 '12 at 11:39
  • Ok, I see. Presumably the overall complexity depends on how often you need to modify the weights; are you saying that you need to do this on every single iteration? – Oliver Charlesworth Jun 14 '12 at 11:43
  • Yes, in my problem, the weights is changed by previously sampled element. So I need to modify the weights every iteration. – Sungmin Jun 14 '12 at 11:51
  • Are you modifying all of the weights every iteration (in which case you're probably out of luck), or just a few? – Michael Anderson Jun 14 '12 at 13:35
  • What if only O(1) mostly just two weights are modified?? also if the modification doesn't change the total weight so no need to normalize? – Sungmin Jun 14 '12 at 14:00

1 Answers1

2

I'm facing the same problem. I will describe my current plan for solving it, but will be grateful for any other suggestions and/or implementation pointers.

My current plan is to adapt the algorithm for Dynamic Order Statistics, as described in Section 14.1 of "Introduction to Algorithms" by Cormen/Leiserson/Rivest. You put your elements into a balanced binary tree, such as a red-black tree, with weights as keys. You augment the tree so that each node stores the sum of the weights in its subtree. The root then stores the sum of weights in the whole tree, say S. The subtree sums can be updated during tree operations in the same way as subtree sizes for dynamic order statistics. To do weighted sampling, you sample a number in [0..S] uniformly, say x; then search down tree for the node N such that the sum of weights of nodes preceding N in in-order traversal is <x, but the sum plus N's weight is >x -- similar to the OS-Select operation for dynamic order statistics.

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
user410315
  • 696
  • 5
  • 8