Algorithm for generating random numbers from a discrete distribution?
algorithm, math, random
Solution
There are many ways to answer this problem. This article describes numerous approaches, their strengths, their weaknesses, and their runtimes. It concludes with an algorithm that takes O(n) preprocessing time, then generates numbers in time O(1) each.
The particular approach you're looking for is described under "roulette wheel selection."
Hope this helps!
Problem
Design a fast algorithm to repeatedly generate numbers from the discrete distribution: Given an array a[] of non negative real numbers that sum to 1, the goal is to return index i with probability a[i] I found this question in a an online algorithm book, Introduction to Programming in Java, chapter 4.2: Sorting and Searching (http://introcs.cs.princeton.edu/java/42sort/) . the hint says: Form an array s[] of cumulated sums such that s[i] is the sum of the first i elements of a[]. Now, generate a random real number r between 0 and 1, and use binary search to return the index i for which s[i] ≤ s[i+1]. some how I am not able to understand the hint and hence cant find the solution..