Tuesday, August 26, 2014

Simulate the roll of a bias or weighted dice.

Recently I can across this problem and find it really interesting, so i thought why not write a code and share it.

There is a probability distribution given for a n sided dice in form an array. Write a code in java to simulate the roll of dice?

I came up with a solution initially which I am not proud of involving caching the outcomes and then based on that rolling the dice. But some googling pointed me finally to this Stackoverflow post:


Which explains the algorithm for the same:

down voteaccepted
In general, if your probabilities are {p1,p2, ...,p6}, construct the following helper list:
{a1, a2, ... a5} = { p1, p1+p2, p1+p2+p3, p1+p2+p3+p4, p1+p2+p3+p4+p5}  
Now get a random number X in [0,1]
        X <= a1  choose 1 as outcome  
   a1 < X <= a2  choose 2 as outcome 
   a2 < X <= a3  choose 3 as outcome  
   a3 < X <= a4  choose 4 as outcome  
   a4 < X <= a5  choose 5 as outcome  
   a5 < X        choose 6 as outcome 
Or, more efficient pseudocode
   if     X > a5 then N=6
   elseif X > a4 then N=5
   elseif X > a3 then N=4
   elseif X > a2 then N=3
   elseif X > a1 then N=2
   else               N=1
This is equivalent to the roulette wheel selection you mention in your question update as shown in this picture:
enter image description here

I decide why don't i write a Java code for the hep of others:

package com.biplav.algorithms;

import java.util.Random;

public class WeightedDiceSimulation {
private static Random r= new Random();

public static int roll(int[] n) {
int[] wieghtedSum = new int[n.length];
wieghtedSum[0] = n[0];
for(int i=1;ilength
;i++) {
wieghtedSum[i] = wieghtedSum[i-1]+n[i];
int p = r.nextInt(100);
for(int i=0;ilength
-1;i++) {
if(p <= wieghtedSum[i]) 
return i+1;
else if(p > wieghtedSum[i] && p<=wieghtedSum[i+1]) {
return i+2;
return n.length;
public static void main(String[] args) {
int[] n = new int[] {20,30,10,0,20,20};
for(int i=0;i<10 i="" p="">