File: General-Discrete-Distributions.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (167 lines) | stat: -rw-r--r-- 9,088 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: General Discrete Distributions</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: General Discrete Distributions">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: General Discrete Distributions">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Random-Number-Distributions.html#Random-Number-Distributions" rel="up" title="Random Number Distributions">
<link href="The-Poisson-Distribution.html#The-Poisson-Distribution" rel="next" title="The Poisson Distribution">
<link href="The-Dirichlet-Distribution.html#The-Dirichlet-Distribution" rel="previous" title="The Dirichlet Distribution">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="General-Discrete-Distributions"></a>
<div class="header">
<p>
Next: <a href="The-Poisson-Distribution.html#The-Poisson-Distribution" accesskey="n" rel="next">The Poisson Distribution</a>, Previous: <a href="The-Dirichlet-Distribution.html#The-Dirichlet-Distribution" accesskey="p" rel="previous">The Dirichlet Distribution</a>, Up: <a href="Random-Number-Distributions.html#Random-Number-Distributions" accesskey="u" rel="up">Random Number Distributions</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="General-Discrete-Distributions-1"></a>
<h3 class="section">20.29 General Discrete Distributions</h3>

<p>Given <em>K</em> discrete events with different probabilities <em>P[k]</em>,
produce a random value <em>k</em> consistent with its probability.
</p>
<p>The obvious way to do this is to preprocess the probability list by
generating a cumulative probability array with <em>K+1</em> elements:
</p>
<div class="example">
<pre class="example">  C[0] = 0 
C[k+1] = C[k]+P[k].
</pre></div>

<p>Note that this construction produces <em>C[K]=1</em>.  Now choose a
uniform deviate <em>u</em> between 0 and 1, and find the value of <em>k</em>
such that <em>C[k] &lt;= u &lt; C[k+1]</em>.  
Although this in principle requires of order <em>\log K</em> steps per
random number generation, they are fast steps, and if you use something
like <em>\lfloor uK \rfloor</em> as a starting point, you can often do
pretty well.
</p>
<p>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&ndash;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 <em>K</em>,
Marsaglia&rsquo;s lookup table can be quite large.  
</p>
<p>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&ndash;256 (1977); see also Knuth, v2,
3rd ed, p120&ndash;121,139).  This requires two lookup tables, one floating
point and one integer, but both only of size <em>K</em>.  After
preprocessing, the random numbers are generated in O(1) time, even for
large <em>K</em>.  The preprocessing suggested by Walker requires
<em>O(K^2)</em> effort, but that is not actually necessary, and the
implementation provided here only takes <em>O(K)</em> 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 <em>K</em>.
</p>
<p>This method can be used to speed up some of the discrete random number
generators below, such as the binomial distribution.  To use it for
something like the Poisson Distribution, a modification would have to
be made, since it only takes a finite set of <em>K</em> outcomes.
</p>
<dl>
<dt><a name="index-gsl_005fran_005fdiscrete_005fpreproc"></a>Function: <em>gsl_ran_discrete_t *</em> <strong>gsl_ran_discrete_preproc</strong> <em>(size_t <var>K</var>, const double * <var>P</var>)</em></dt>
<dd><a name="index-gsl_005fran_005fdiscrete_005ft"></a>
<a name="index-Discrete-random-numbers"></a>
<a name="index-Discrete-random-numbers_002c-preprocessing"></a>
<p>This function returns a pointer to a structure that contains the lookup
table for the discrete random number generator.  The array <var>P</var>[] contains
the probabilities of the discrete events; these array elements must all be 
positive, but they needn&rsquo;t add up to one (so you can think of them more
generally as &ldquo;weights&rdquo;)&mdash;the preprocessor will normalize appropriately.
This return value is used
as an argument for the <code>gsl_ran_discrete</code> function below.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fran_005fdiscrete"></a>Function: <em>size_t</em> <strong>gsl_ran_discrete</strong> <em>(const gsl_rng * <var>r</var>, const gsl_ran_discrete_t * <var>g</var>)</em></dt>
<dd><a name="index-Discrete-random-numbers-1"></a>
<p>After the preprocessor, above, has been called, you use this function to
get the discrete random numbers.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fran_005fdiscrete_005fpdf"></a>Function: <em>double</em> <strong>gsl_ran_discrete_pdf</strong> <em>(size_t <var>k</var>, const gsl_ran_discrete_t * <var>g</var>)</em></dt>
<dd><a name="index-Discrete-random-numbers-2"></a>
<p>Returns the probability <em>P[k]</em> of observing the variable <var>k</var>.
Since <em>P[k]</em> is not stored as part of the lookup table, it must be
recomputed; this computation takes <em>O(K)</em>, so if <var>K</var> is large
and you care about the original array <em>P[k]</em> used to create the
lookup table, then you should just keep this original array <em>P[k]</em>
around.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fran_005fdiscrete_005ffree"></a>Function: <em>void</em> <strong>gsl_ran_discrete_free</strong> <em>(gsl_ran_discrete_t * <var>g</var>)</em></dt>
<dd><a name="index-Discrete-random-numbers-3"></a>
<p>De-allocates the lookup table pointed to by <var>g</var>.
</p></dd></dl>

<hr>
<div class="header">
<p>
Next: <a href="The-Poisson-Distribution.html#The-Poisson-Distribution" accesskey="n" rel="next">The Poisson Distribution</a>, Previous: <a href="The-Dirichlet-Distribution.html#The-Dirichlet-Distribution" accesskey="p" rel="previous">The Dirichlet Distribution</a>, Up: <a href="Random-Number-Distributions.html#Random-Number-Distributions" accesskey="u" rel="up">Random Number Distributions</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>