Thanks a lot, Derek, this one is indeed a champion !
On a 2.1GHz machine, Matlab2008a 32-bit,
I got:
t2 = 0.18
VS
t2 within 18-22 for a couple of other tested methods.
Kind regards,
N
Here is a function that beats those above by a mile:
function S = DiscSampVec2(x,p,ns);
%
[~,idx] = histc(rand(1,ns),[0,cumsum(p)]);
S = x(idx);
This is a slight modification of the function on page 47, Kroese, Taimre, and Botev, Handbook of Monte Carlo Methods, Wiley, 2011.
>> ns=10^6; n=10^3; x=1:n;
>> p = rand(1,n); p = p/sum(p);
>> t2=tic;
>> S = DiscSampVec2(x,p,ns);
>> t2=toc(t2)
0.15835
@Derek, I am aware and glad that there are other formulations of this task. 'N' and 'M' are clearly defined in the description above. There is no overt relationship between P and N & M. P is a distribution, in the mathematical sense of the word, and because it describes the probability of picking an index of P, the sum of those values must equal one, i.e. it must be normalized.
For reference:
http://en.wikipedia.org/wiki/Probability_distribution
http://en.wikipedia.org/wiki/Normalizing_constant
ALSO:
See here
http://math.stackexchange.com/questions/48919/generating-a-non-uniform-discrete-random-variable
and here
http://math.stackexchange.com/questions/58060/minimize-expected-value
Comment only