„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)
        notaccepted=.TRUE.
        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.

Java

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];
	weight[0]=0.4;
	weight[1]=0.3;
	weight[2]=1.2;
	weight[3]=0.1;
	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++){
		notaccepted=true;
		while (notaccepted){
			index= (int)(n*Math.random());
			if(Math.random()<weight[index]/max_weight) {notaccepted=false;}
		}
		counter[index]++;
	}
	for (int i=0; i<n; i++){
		System.out.println("counter["+i+"]="+counter[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