„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.4;
weight=0.3;
weight=1.2;
weight=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=216
# counter=135
# counter=595
# counter=54```