离散引导表 (DGT)#

  • 需要：概率向量 (PV) 或 PMF 以及有限域

  • 速度

    • 设置：缓慢（随向量长度线性增长）

    • 采样：非常快

DGT 从任意但有限的概率向量中采样。随机数是通过反演法生成的，即

  1. 生成一个随机数 U ~ U(0,1)。

  2. 找到最小的整数 I，使得 F(I) = P(X<=I) >= U。

步骤 (2) 是关键步骤。使用顺序搜索需要 O(E(X)) 次比较，其中 E(X) 是分布的期望值。然而，索引搜索使用引导表跳转到 I 附近某个 I' <= I，以便在恒定时间内找到 X。事实上，当引导表的大小与概率向量相同（这是默认值）时，预期的比较次数减少到 2。对于更大的引导表，这个数字会更小（但始终大于 1），对于更小的表，这个数字会更大。

另一方面，引导表的设置时间为 O(N)，其中 N 表示概率向量的长度（对于大小 1，不需要预处理）。此外，对于非常大的引导表，内存效应甚至可能会降低算法的速度。因此，我们不建议使用比给定概率向量大三倍以上的引导表。如果只需要生成少量随机数，则使用（更）小的表尺寸会更好。引导表相对于给定概率向量长度的大小可以通过 guide_factor 参数设置。

>>> import numpy as np
>>> from scipy.stats.sampling import DiscreteGuideTable
>>>
>>> pv = [0.18, 0.02, 0.8]
>>> urng = np.random.default_rng()
>>> rng = DiscreteGuideTable(pv, random_state=urng)
>>> rng.rvs()
2    # may vary

默认情况下，概率向量从 0 开始索引。但是，这可以通过传递 domain 参数来更改。当 domain 与 PV 结合使用时，它会将分布从 (0, len(pv)) 重新定位到 (domain[0], domain[0] + len(pv))。在这种情况下，domain[1] 被忽略。

>>> rng = DiscreteGuideTable(pv, random_state=urng, domain=(10, 13))
>>> rng.rvs()
10   # may vary

当没有给出概率向量而是给出 PMF 时，该方法也适用。在这种情况下，必须通过显式传递 domain 参数或在分布对象中提供 support 方法来给出有限域。

>>> class Distribution:
...     def __init__(self, c):
...             self.c = c
...     def pmf(self, x):
...             return x ** self.c
...     def support(self):
...             return 0, 10
...
>>> dist = Distribution(2)
>>> rng = DiscreteGuideTable(dist, random_state=urng)
>>> rng.rvs()
9     # may vary

注意

由于 DiscreteGuideTable 期望 PMF 具有签名 def pmf(self, x: float) -> float，因此它首先使用 np.vectorize 将 PMF 向量化，然后在域中的所有点上对其进行评估。但是，如果 PMF 已经向量化，则在域中的每个点上对其进行评估并传递获得的 PV 以及域会更快。例如，SciPy 离散分布的 pmf 方法是向量化的，可以通过以下方式获得 PV

>>> from scipy.stats import binom
>>> from scipy.stats.sampling import DiscreteGuideTable
>>> dist = binom(10, 0.2)  # distribution object
>>> domain = dist.support()  # the domain of your distribution
>>> x = np.arange(domain[0], domain[1] + 1)
>>> pv = dist.pmf(x)
>>> rng = DiscreteGuideTable(pv, domain=domain)

此处需要域来重新定位分布

可以使用 guide_factor 参数设置引导表相对于概率向量的大小。更大的引导表会导致更快的生成时间，但需要更昂贵的设置。

>>> guide_factor = 2
>>> rng = DiscreteGuideTable(pv, random_state=urng, guide_factor=guide_factor)
>>> rng.rvs()
2     # may vary

不幸的是，PPF 很少以封闭形式给出，或者在给出时太慢。用户只需要提供概率向量，并且可以使用 ppf 方法评估 PPF（逆 CDF）。此方法计算给定分布的（精确）PPF。

例如，要计算二项式分布的 PPF，其中 \(n=4\) 且 \(p=0.1\)：我们可以按如下方式设置引导表

>>> import scipy.stats as stats
>>> n, p = 4, 0.1
>>> dist = stats.binom(n, p)
>>> rng = DiscreteGuideTable(dist, random_state=42)
>>> rng.ppf(0.5)
0.0

有关此方法的更多详细信息，请参见 [1] 和 [2]。

参考文献#

本页内容