A one-table method for sampling from continuous and discrete distributions (Q1345428)

A practical method for sampling from largely arbitrary distributions \(F\) with density functions \(f(x)\) or probabilities \(P_ k\) (in discrete cases) is developed. The paper deals with the target density \(f(x)\) in the form of a union of a finite number of bounded monotonic pieces or `slopes'. The method in this article is based on J. v. Neumann's acceptance-rejection procedure improved by the stratagem which is called `immediate acceptance'. It consists of an algorithm `TABL' which generates one auxiliary table \((a_ j)\) containing a subdivision of the range of \(f(x)\) and a routine `SAMPL' which produces the samples. In TABL each monotonic slope \(\langle A,B \rangle\) is subdivided into parts \(\langle a_ k = A, a_{k + 1} \rangle\), \(\langle a_{k + 1}, a_{k + 2} \rangle, \dots,\) \(\langle a_ \ell, a_{\ell + 1} \rangle\) by the rule that \(f(a_ j) | a_ j - a_{j + 1} | = C\) is constant. This constant area \(C\) is chosen by stating its reciprocal \(r = 1/C\) in the input to TABL. The \((a_ j)\)-table may contain data for several distributions which can then be used in the same simulation. The organization of the entire array \((a_ j)\) is illustrated by the two examples. The high efficiency of the sampling routine is achieved by means of only one auxiliary table. The formal statements of TABL/SAMPL were derived from most successful computer programs after very long series of experiments with many target distributions. A theorem on the fairly general applicability and `asymptotic efficiency' of the new method is proved. Examples of standard distributions are very helpful as a guideline for devising an input for target distribution. Examples of continuous and discrete distributions demonstrate that the procedure is easy to apply and that its speed does not much depend on the particular target distribution \(F\). In the final some computational experience is reported. Fortran and C programs for the two algorithms with an example of a main program are available on request.