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]
我在一本在线算法书籍 Introduction to Programming in Java, chapter 4.2: Sorting and Searching (http://introcs.cs.princeton.edu/java/42sort/) 中发现了这个问题。
提示说:
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].
有些我无法理解提示，因此无法找到解决方案..
最佳答案
有很多方法可以解决这个问题。 <强> This article 描述了多种方法、它们的优点、缺点和运行时间。它以一种算法结束，该算法需要 O(n) 的预处理时间，然后每个生成时间为 O(1) 的数字。
您正在寻找的特定方法在“轮盘赌选择”中进行了描述。
希望这对您有所帮助!
关于从离散分布生成随机数的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10064344/