News for hackers. Stuff that matters.
Re:Ask HN: Fast sampling and update of weighted items? (data... by mjtokelly on Wednesday March 25, 2009 @03:21PM (#532281)
Here's a sampling algorithm that will work, as long as the maximum weight isn't too much greater than the average weight:

1) Determine the maximum weight mw. (This is O(N) the first time, O(K) subsequent times.)

2) Repeat until an index i is accepted:

  a) Generate a random pair (i, x), where i is a uniform integer over [1,N], and x is a uniform float over [0,mw].

  b) Accept index i if weight(i) < x.
3) Return the accepted index i.

This gives you the desired distribution in time O(mw/aw) (maximum weight over average weight).

Re:Ask HN: Fast sampling and update of weighted items? (data... by bravura on Wednesday March 25, 2009 @04:21PM (#532369)
Rejection sampling is perhaps not a good option, because the assumption does not hold: "the maximum weight isn't too much greater than the average weight"

In learning algorithms, the distribution of the weights can get piqued.

Re:Ask HN: Fast sampling and update of weighted items? (data... by mjtokelly on Wednesday March 25, 2009 @03:50PM (#532330)
An example of Rejection Sampling:

http://en.wikipedia.org/wiki/Rejection_sampling