Random Sampling By A Given Probability Distribution

Problem Definition:

Random select a number i (i >= 1 and i < = n), from 1 to n where n >= 1 given a probability discrete distribution P: Pr(1) = p1, Pr(2) = p2, …, Pr(n) = pn, such that p1 + p2 + … pn = 1, that is, the probability i would be selected should be equal to Pr(i).

Source code:

The whole process is quite like a spin process, imagine a wheel of area 1 which is separated into n sector and the, Sector i is of area Pr(i). There is a needle at the 12 clock, and then we spin the wheel, we choose the sector k where the needle stays at in the when the wheel stops. The following is the matlab source code with a simplified implementation:

function sel = spin(prob)
% @Desc     this function takes a probability distribution
%           and a candidate i will be returned with probability prob(i)
% @Param    sum(prob) should be 1
%	    prob is n * 1 column vector
%

if sum(prob) - 1 > eps
	error('Error occurred in spin(prob): sum(prob) != 1\n');
end

rnd_value = rand(); % between 0 and 1
n = size(prob, 1);

sel = 0;            % undefined!
cum = 0.0;
for i = 1:n
	cum = cum + prob(i);
	if cum >= rnd_value
		sel = i;
		break;
	end
en

To summarize, I give a matlab implementation for how to randomly select a number out of a set of numbers with given probability.

Written on August 29, 2014