1

I want the program to choose something with a set probability. For example, there is 0.312 probability of choosing path A and 0.688 probability of choosing path B. The only way I can think is a naive way to select randomly from the interval 0-1 and checking if <=0.312. Is there some better approach that extends to more than 2 elements?

avmohan
  • 1,820
  • 3
  • 20
  • 39
  • The phrases to search for are "weighted random selection" and "weighted random choice". – DSM Nov 18 '13 at 01:18
  • To randomly select from a set of many outcomes with unequal probabilities, I recommend [alias tables](http://stackoverflow.com/questions/17250568/randomly-choosing-from-a-list-with-weighted-probabilities/17253335#17253335). If your implementing language allows function pointers or dynamic method dispatch, you could store the function/method as the value and dispatch to it directly based on the alias table's generated value. Otherwise, you could use the generated value with a switch-type statement to control which logic applies. – pjs Nov 18 '13 at 03:11

1 Answers1

0

Following is a way to do it with more efficiently than multiple if else statements: -

Suppose

a = 0.2, b = 0.35, c = 0.15, d = 0.3. Make an array where p[0] corresponds to a and p[1] corresponds to b and so on run a loop evaluating sum of probabilties

p[0] = 0.2
p[1] = 0.2 + 0.35 = 0.55
p[2] = 0.55 + 0.15 = 0.70
p[3] = 0.70 + 0.30 = 1

Generate a random number in [0,1]. Do binary search on p for random number. The interval that search returns will be your branch

eg. 

random no = 0.6
result = binarySearch(0.6)
result = 2 using above intervals
2 => branch c
Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19
  • For N outcomes this is O(N) to set up and O(log N) for each use. The alias table approach is O(N log N) to set up, and O(1) for each use. – pjs Nov 18 '13 at 05:11
  • Yes but it doesnot matter if N is not that big.I suspect number of branches wont be so large – Vikram Bhat Nov 18 '13 at 07:45