[Rd] efficiency of sample() with prob.

[Bo Peng]

On 6/21/05, Vadim Ogranovich <vograno at 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