| 第2,013行： |
第2,013行： |
| | ===生成泊松分布随机变量=== | | ===生成泊松分布随机变量=== |
| | 给出了一个产生随机泊松分布数(伪随机数抽样)的简单算法: | | 给出了一个产生随机泊松分布数(伪随机数抽样)的简单算法: |
| − | 算法：泊松随机数 Knuth : | + | 算法：泊松随机数 Knuth |
| − | 初始化:
| + | 初始化： |
| − | 设 L ← ''e''<sup>−λ</sup>, k ← 0 且 p ← 1.
| + | 设 L ← ''e''<sup>−λ</sup>, k ← 0 且 p ← 1. |
| − | 执行
| + | 执行： |
| − | k ← k + 1.
| + | k ← k + 1. |
| − | 在[0,1]中生成均匀随机数 u 并且设 p ← p × u。
| + | 在[0,1]中生成均匀随机数 u 并且设 p ← p × u。 |
| − | 而 p > L.
| + | 同时 p > L. |
| − | 返回 k − 1.
| + | 返回 k − 1. |
| | | | |
| | | | |
| 第2,026行： |
第2,026行： |
| | | | |
| | | | |
| | + | 对于λ较大的值，L = ''e''<sup>−λ</sup>的值可能非常小，以至于很难表示。这可以通过改变算法来解决，该算法使用附加参数 STEP，使得''e''<sup>−STEP</sup>不会下溢: |
| | | | |
| − | For large values of λ, the value of L = ''e''<sup>−λ</sup> may be so small that it is hard to represent. This can be solved by a change to the algorithm which uses an additional parameter STEP such that ''e''<sup>−STEP</sup> does not underflow: {{Citation needed|reason=Original source is missing|date=March 2019}}
| |
| | | | |
| − | For large values of λ, the value of L = e<sup>−λ</sup> may be so small that it is hard to represent. This can be solved by a change to the algorithm which uses an additional parameter STEP such that e<sup>−STEP</sup> does not underflow:
| + | 算法：泊松随机数 Junhao（基于 Knuth） : |
| | + | 初始化： |
| | + | 设Let''' λLeft ← λ, k ← 0 且 p ← 1. |
| | + | 执行： |
| | + | k ← k + 1. |
| | + | 在(0,1)中生成均匀随机数 u 并且设p ← p × u |
| | + | 而 p < 1 and λLeft > 0: |
| | + | 如果 λLeft > STEP: |
| | + | p ← p × ''e''<sup>STEP</sup> |
| | + | λLeft ← λLeft − STEP |
| | + | 或者: |
| | + | p ← p × ''e''<sup>λLeft</sup> |
| | + | λLeft ← 0 同时 p > 1。 |
| | + | 返回 k − 1. |
| | | | |
| − | 对于较大的值，l = e </sup >-</sup > 的值可能非常小，以至于很难表示。这可以通过改变算法来解决，该算法使用附加参数 STEP，使得 e < sup >-STEP </sup > 不会底流:
| |
| | | | |
| − | --[[用户:fairywang|fairywang]]([[用户讨论:fairywang|讨论]]) 【审校】“底流”改为“下溢”
| + | STEP 的选择取决于溢出阈值。对于双精度浮点格式，阈值接近''e''<sup>700</sup>，因此500应该是一个安全的 STEP。 |
| | | | |
| − | '''algorithm''' ''poisson random number (Junhao, based on Knuth)'':
| |
| | | | |
| − | algorithm poisson random number (Junhao, based on Knuth):
| + | 其他λ的大数值的求解包括抑制取样和使用'''高斯近似 Gaussian approximation'''。 |
| | | | |
| − | 泊松随机数算法(Junhao，基于 Knuth) :
| |
| | | | |
| − | '''init''':
| + | 逆变换采样对于λ小数值的样本是简单有效的，并且每个样本只需要一个均匀一致的随机数''u''。依次检查累积概率，直到其超过''u''。 |
| | | | |
| − | init:
| |
| | | | |
| − | 初始化: | + | 算法：基于顺序检索反演的泊松发生器算法 Algorithm Poisson generator: |
| | + | 初始化: |
| | + | 设 x ← 0, p ← ''e''<sup>−λ</sup>, s ← p. |
| | + | 在[0,1]中生成均匀随机数 u，同时 u > s |
| | + | 执行： |
| | + | x ← x + 1. |
| | + | p ← p × λ / x. |
| | + | s ← s + p. |
| | + | 返回 x |
| | | | |
| − | '''Let''' λLeft ← λ, k ← 0 and p ← 1.
| + | <br> |
| − | | |
| − | Let λLeft ← λ, k ← 0 and p ← 1.
| |
| − | | |
| − | Let λLeft ← λ, k ← 0 and p ← 1.
| |
| − | | |
| − | '''do''':
| |
| − | | |
| − | do:
| |
| − | | |
| − | 做:
| |
| − | | |
| − | k ← k + 1.
| |
| − | | |
| − | k ← k + 1.
| |
| − | | |
| − | k ← k + 1.
| |
| − | | |
| − | Generate uniform random number u in (0,1) and '''let''' p ← p × u.
| |
| − | | |
| − | Generate uniform random number u in (0,1) and let p ← p × u.
| |
| − | | |
| − | 在(0,1)中生成均匀随机数 u 并且设 p ← p u。
| |
| − | | |
| − | '''while''' p < 1 and λLeft > 0:
| |
| − | | |
| − | while p < 1 and λLeft > 0:
| |
| − | | |
| − | while p < 1 and λLeft > 0:
| |
| − | | |
| − | '''if''' λLeft > STEP:
| |
| − | | |
| − | if λLeft > STEP:
| |
| − | | |
| − | if λLeft > STEP:
| |
| − | | |
| − | p ← p × ''e''<sup>STEP</sup>
| |
| − | | |
| − | p ← p × e<sup>STEP</sup>
| |
| − | | |
| − | p ← p × e<sup>STEP</sup>
| |
| − | | |
| − | λLeft ← λLeft − STEP
| |
| − | | |
| − | λLeft ← λLeft − STEP
| |
| − | | |
| − | λLeft ← λLeft − STEP
| |
| − | | |
| − | '''else''':
| |
| − | | |
| − | else:
| |
| − | | |
| − | 其他:
| |
| − | | |
| − | p ← p × ''e''<sup>λLeft</sup>
| |
| − | | |
| − | p ← p × e<sup>λLeft</sup>
| |
| − | | |
| − | p ← p × e<sup>λLeft</sup>
| |
| − | | |
| − | λLeft ← 0
| |
| − | | |
| − | λLeft ← 0
| |
| − | | |
| − | λLeft ← 0
| |
| − | | |
| − | '''while''' p > 1.
| |
| − | | |
| − | while p > 1.
| |
| − | | |
| − | 同时 p > 1。
| |
| − | | |
| − | '''return''' k − 1.
| |
| − | | |
| − | return k − 1.
| |
| − | | |
| − | return k − 1.
| |
| − | | |
| − | | |
| − | | |
| − | The choice of STEP depends on the threshold of overflow. For double precision floating point format, the threshold is near ''e''<sup>700</sup>, so 500 shall be a safe ''STEP''.
| |
| − | | |
| − | The choice of STEP depends on the threshold of overflow. For double precision floating point format, the threshold is near e<sup>700</sup>, so 500 shall be a safe STEP.
| |
| − | | |
| − | STEP 的选择取决于溢出''' 阈值Threshold'''。对于双精度浮点格式，''' 阈值Threshold'''接近 e < sup > 700 </sup > ，因此500应该是一个安全的 STEP。
| |
| − | | |
| − | | |
| − | | |
| − | Other solutions for large values of λ include [[rejection sampling]] and using Gaussian approximation.
| |
| − | | |
| − | Other solutions for large values of λ include rejection sampling and using Gaussian approximation.
| |
| − | | |
| − | 其他λ的大数值的求解包括抑制取样和使用''' 高斯近似Gaussian approximation'''。
| |
| − | | |
| − | | |
| − | | |
| − | [[Inverse transform sampling]] is simple and efficient for small values of λ, and requires only one uniform random number ''u'' per sample. Cumulative probabilities are examined in turn until one exceeds ''u''.
| |
| − | | |
| − | Inverse transform sampling is simple and efficient for small values of λ, and requires only one uniform random number u per sample. Cumulative probabilities are examined in turn until one exceeds u.
| |
| − | | |
| − | 逆变换采样对于λ小数值的样本是简单有效的，并且每个样本只需要一个均匀一致的随机数 u。依次检查累积概率，直到其超过 u。
| |
| − | | |
| − | | |
| − | | |
| − | '''algorithm''' ''Poisson generator based upon the inversion by sequential search'':{{r|Devroye1986|p=505}}
| |
| − | | |
| − | algorithm Poisson generator based upon the inversion by sequential search:
| |
| − | | |
| − | 基于顺序检索反演的''' 泊松发生器算法Algorithm Poisson generator ''':
| |
| − | | |
| − | '''init''':
| |
| − | | |
| − | init:
| |
| − | | |
| − | 初始化:
| |
| − | | |
| − | '''Let''' x ← 0, p ← ''e''<sup>−λ</sup>, s ← p.
| |
| − | | |
| − | Let x ← 0, p ← e<sup>−λ</sup>, s ← p.
| |
| − | | |
| − | Let x ← 0, p ← e<sup>−λ</sup>, s ← p.
| |
| − | | |
| − | Generate uniform random number u in [0,1].
| |
| − | | |
| − | Generate uniform random number u in [0,1].
| |
| − | | |
| − | 在[0,1]中生成均匀随机数 u。
| |
| − | | |
| − | '''while''' u > s '''do''':
| |
| − | | |
| − | while u > s do:
| |
| − | | |
| − | 做以下步骤:
| |
| − | | |
| − | x ← x + 1.
| |
| − | | |
| − | x ← x + 1.
| |
| − | | |
| − | x ← x + 1.
| |
| − | | |
| − | p ← p × λ / x.
| |
| − | | |
| − | p ← p × λ / x.
| |
| − | | |
| − | p ← p × λ / x.
| |
| − | | |
| − | s ← s + p.
| |
| − | | |
| − | s ← s + p.
| |
| − | | |
| − | s ← s + p.
| |
| − | | |
| − | '''return''' x.
| |
| − | | |
| − | return x.
| |
| − | | |
| − | 返回 x。
| |
| | | | |
| | == 历史 == | | == 历史 == |