„Roulette-wheel selection via stochastic acceptance”, Physica A 391, 2193 (2012)  (arxiv preprint)

Outline of  implementation:

  1) select (uniformly) one of the n elements, say k-th
  2) accept the selection with probability weight(k)/max, where max is the maximum weight
  3) if not accepted, select anew (step 1)

f77 code:

c----------------------------- roulette-wheel selection --------------------

c code selects one of n elements with probability proportional to weight(k)
        do while (notaccepted)
            call rndgnrt(r) ! generates a random number r (0<r<1)
            k=int(r*n)+1 ! k - randomly drawn integer number (k=1, 2,..., n)
            call rndgnrt(r)
            if (r.LT.weight(k)/MAX) notaccepted=.FALSE. ! MAX - maximum of weights
       end do
       write(6,*) 'selected number=', k

Comment: Typically,  weight(k) are evolving and one should keep track of the max. However, when weight(k) are known to be bounded, e.g., by definition one has  0<weight(k)<BOUND, then BOUND can be used instead of  MAX. It reduces efficiency but simplifies the algorithm.


public class roulette {
	/* program n_select=1000 times selects one of n=4 elements with weights weight[i].
	 * Selections are summed up in counter[i]. For the weights as given in the example 
	 * below one expects that elements 0,1,2 and 3 will be selected (on average) 
	 * 200, 150, 600 and 50 times, respectively.  In good agreement with exemplary run.
public static void main(String [] args) {
	int n=4;
	double [] weight = new double [n];
	double max_weight=1.2;
	int  [] counter = new int[n];
	int n_select=1000;
	int index=0;
	boolean notaccepted;
	for (int i=0; i<n_select; i++){
		while (notaccepted){
			index= (int)(n*Math.random());
			if(Math.random()<weight[index]/max_weight) {notaccepted=false;}
	for (int i=0; i<n; i++){
/* The program uses stochastic acceptance instead of linear (or binary) search. 
 * More on http://arxiv.org/abs/1109.3627
# Exemplary output:
# counter[0]=216
# counter[1]=135
# counter[2]=595
# counter[3]=54