从离散分布生成随机数的算法？

Question

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].

有些我无法理解提示，因此无法找到解决方案..

Answer 1

有很多方法可以解决这个问题。 <强> This article 描述了多种方法、它们的优点、缺点和运行时间。它以一种算法结束，该算法需要 O(n) 的预处理时间，然后每个生成时间为 O(1) 的数字。

您正在寻找的特定方法在“轮盘赌选择”中进行了描述。

希望这对您有所帮助!