离散引导表 (DGT)#

必需：概率向量 (PV) 或概率质量函数 (PMF) 以及有限域
速度：
- 设置：慢（与向量长度成线性关系）
- 采样：非常快

DGT 从任意但有限的概率向量中进行采样。随机数的生成采用逆变换方法，即：

生成一个随机数 U ~ U(0,1)。
找到最小的整数 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    # 可能会有所不同

默认情况下，概率向量从 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   # 可能会有所不同

当没有给出概率向量而是给出了 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     # 可能会有所不同

注意

由于 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)  # 分布对象
>>> domain = dist.support()  # 你的分布的域
>>> 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     # 可能会有所不同

遗憾的是，PPF（分位点函数）很少有封闭形式的解，或者在可用时计算速度太慢。用户只需提供概率向量，PPF（逆CDF）可以通过``ppf``方法进行评估。该方法计算给定分布的（精确）PPF。

例如，要计算参数为 \(n=4\) 和 \(p=0.1\) 的二项分布的PPF，我们可以如下设置引导表：

>>> 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]_。

离散引导表 (DGT)#

参考文献#