Given K discrete events with different probabilities P[k], produce a random value k consistent with its probability.
discrete random variable distribution, generate random number.
比如 给你 [0.2, 0.3, 0.5] 输出0 with probability 0.2, 1 with prob 0.3, 2 with prob 0.5
Follow up : how to speed up
This is an important problem with many applications, especially in Monte-Carlo simulations. There are several solutions to it. They all start with a standard random number u that is uniformly distributed in the interval [0,1). The simplest algorithm would then proceed as follows:
if u<p[0] then return 0; else if u<p[0]+p[1] then return 1; else if u<p[0]+p[1]+p[2] then return 2; ... and so on ...
This algorithm is O(n). Using binary search, it can be brought down to O(log(n)).
However, there is another solution that is O(1). It uses precomputed arrays. Effort for this precomputation is O(n). Drawing a representative event requires just drawing of u plus two array lookups plus little arithemetics, independent of n. This ingenious algorithm is called the alias method. It is due to Walker (1974/77), with refinements by Vose (1991). It is the preferred method for M > > n > > 1, where M is the number of drawings.
The obvious way to do this is to preprocess the probability list by generating a cumulative probability array with K+1 elements:
C[0] = 0 C[k+1] = C[k]+P[k].
Note that this construction produces C[K]=1. Now choose a uniform deviate u between 0 and 1, and find the value of k such that C[k] <= u < C[k+1]. Although this in principle requires of order \log K steps per random number generation, they are fast steps, and if you use something like \lfloor uK \rfloor as a starting point, you can often do pretty well.
But faster methods have been devised. Again, the idea is to preprocess the probability list, and save the result in some form of lookup table; then the individual calls for a random discrete event can go rapidly. An approach invented by G. Marsaglia (Generating discrete random variables in a computer, Comm ACM 6, 37–38 (1963)) is very clever, and readers interested in examples of good algorithm design are directed to this short and well-written paper. Unfortunately, for large K, Marsaglia’s lookup table can be quite large.
A much better approach is due to Alastair J. Walker (An efficient method for generating discrete random variables with general distributions, ACM Trans on Mathematical Software 3, 253–256 (1977); see also Knuth, v2, 3rd ed, p120–121,139). This requires two lookup tables, one floating point and one integer, but both only of size K. After preprocessing, the random numbers are generated in O(1) time, even for large K. The preprocessing suggested by Walker requiresO(K^2) effort, but that is not actually necessary, and the implementation provided here only takes O(K) effort. In general, more preprocessing leads to faster generation of the individual random numbers, but a diminishing return is reached pretty early. Knuth points out that the optimal preprocessing is combinatorially difficult for large K.
下面给出O(logN)的解法:
public static int discreteRandom(double[] A) { int n = A.length; double[] C = new double[n+1]; for(int i=0; i<n; i++) { C[i+1] = C[i] + A[i]; } double r = new Random().nextDouble(); int l = 0, h = n-1; while(l <= h) { int m = (l + h)/2; if(r >= C[m] && r < C[m+1]) { return m; } else if(r < C[m]) { h = m - 1; } else { l = m + 1; } } return l; } // Test Case public static void main(String[] args) { double[] B = {0.2, 0.3, 0.5}; int[] D = {0, 0, 0}; for(int i=1; i<10000000; i++) { D[discreteRandom(B)]++; } System.out.println(Arrays.toString(D)); //output: [2001045, 3001794, 4997160] }
References:
http://en.wikipedia.org/wiki/Pseudo-random_number_sampling
http://en.wikipedia.org/wiki/Alias_method
https://github.com/argh/hacks/tree/master/non-uniform-distributions
http://oroboro.com/non-uniform-random-numbers
http://www.keithschwarz.com/darts-dice-coins/
http://apps.jcns.fz-juelich.de/doku/sc/ransampl
https://www.gnu.org/software/gsl/manual/html_node/General-Discrete-Distributions.html
相关推荐
Solution-Manual-for-Discrete-Time-Signal-Processing,-3-E-3rd-Edition-Alan-V.-Oppenheim,-Ronald-W.-Schafer
PyTorch中的SAC-Discrete 这是SAC-Discrete 的PyTorch实现。 我试图使读者更容易理解算法。 请让我知道,如果你有任何问题。 更新 2020.5.10 重构代码并修复SAC-Discrete算法的错误。 实现优先体验重放 ,N步...
本文献《James-Baglama_Decomposition-methods-for-large-linear-discrete-ill-posed-problems_Journal-of-Computational-and-Applied-Mathematics_2007》主要探讨了通过迭代方法求解大型线性离散病态问题的有效策略...
ExtremeLearningMachine资源共享-Nonlinear-discrete-time-neural-network-observer_2013_Neurocomputing.pdf 小弟准备学习ELM,才收集到一些相关资料,发现论坛中并无相关资料,因此把自己手头上收集到的共享给...
Lovász - Discrete Mathematics Lecture Notes #### 知识点概览: 1. **离散数学基础** - 引言:本部分简要介绍了离散数学的概念及其重要性。 - 计数原理:通过具体的例子(如聚会问题)引入基本的计数方法。 ...
标题 "[MMS_052836]Analog in - discrete out.rar" 提供的信息表明,这是一个关于模拟输入(Analog in)和离散输出(Discrete out)的示例程序,可能针对Allen Bradley(AB)品牌的可编程逻辑控制器(PLC)。...
标题中的"twanyformation-discrete.rar_网络编程"暗示了这是一个关于网络编程的资源包,特别是涉及到了离散信号处理的方面。从描述来看,这个程序着重于实现逆快速傅里叶变换(IFFT)以及与连续变换的比较,同时探讨...
计算机科学家需要的离散数学
书名(英文):Discrete Mathematics and Its Applications (7th Edition) 书名(中文):离散数学及其应用 (第七版) 原作者:Kenneth H.Rosen 【注】离散数学方面的经典教材。 书名(英文):Concrete ...
《Scale-Space for Discrete Signals 1990》是一份深入探讨离散信号尺度空间理论的学术资源,由相关领域的专家在1990年撰写。尺度空间理论是计算机视觉、图像处理和模式识别领域中的核心概念,它提供了一种理解和...
A 1.8 165mW Discrete Wavelet MultiTone Baseband Receiver for Cognitive Radio application
time = 0:32588; figure; subplot(2, 1, 1); plot(time,Int_data_all(6:32594,4)); % 离线组合 hold on;...plot(time,Int_data_all(6:32594,13));...legend('离线组合','gps测量');...plot(time,Int_data_all(6:32594,4)-Int...
Provides easy learning and understanding of DWT from a signal processing point of view,解压密码 share.weimo.info
层次分析matlab代码基于离散约束的车辆模型 这是《基于离散约束的车辆建模和动力分析》文章的模型MATLAB代码,2017年1月国际车辆设计杂志。涉及离散约束模型和经典模型。 运行文件mymode2.m可以得到结果。...
1.版本:matlab2019a,内含运行结果,不会运行可私信 2.领域:基础教程 3.内容:整数优化matlab代码Integer_Discrete Optimization.zip 4.适合人群:本科,硕士等教研学习使用
连续离散立方体卡尔曼滤波器(CDCKF)是一种高级的估计理论技术,用于融合连续时间系统和离散时间观测的数据。在导航、控制、信号处理和许多其他领域,这种滤波器能提供对动态系统状态的精确估计。...
matlab论文图示例代码最佳运输 该存储库包含我的 Valentin Hartmann 的学士以及与 Dominic Schuhmacher 合着的算法的实现。 即欧几里得成本函数从连续测量到离散测量的(半离散)最优传输的计算和可视化。...
Simple-Discrete-Event-Simulation Use c# Winform to simulate the simple discrete event system Single -Server Queue 模拟单一server的服务系统,且基于以下两点假设 先进先出原则。每个job依照抵达时间先后...