Re: [Rd] efficiency of sample() with prob.

From: Bo Peng <ben.bob_at_gmail.com>
Date: Wed 22 Jun 2005 - 18:14:02 GMT

On 6/21/05, Vadim Ogranovich <vograno@evafunds.com> wrote:
> In his "Introduction to Probability Models" Sheldon Ross describes (sec
> 11.4.1, 8th edition) the alias method for such weighted sampling.
> It is based on some decomposition of the original distribution (the
> weights) into a mixture of two-point distributions.

This sounds like Walker's alias method for weighted sampling. I looked through Knoth's 'the art of computer programming' and find this algorithm. I implemented this one but it is just as efficient as the bisection lookup method in my case. The reason is that the setup of this algorithm is complicated so it is suited for getting large sample from short weighted sequences. Anyway, I do suggest R developers try this algorithm for sample with replacement. A sample code can be found at http://statistik.wu-wien.ac.at/arvag/monograph/arvag-src/algo03_03.c .

BTW, does anyone know a quicker algorithm to set up the internal table of the alias method?

Bo



R-devel@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel Received on Thu Jun 23 04:15:48 2005

This archive was generated by hypermail 2.1.8 : Mon 20 Feb 2006 - 03:21:09 GMT