离散引导表 (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 的表，不需要预处理）。此外，对于非常大的引导表，内存效应甚至可能会降低算法的速度。因此，我们不建议使用比给定概率向量大三倍以上的引导表。如果只需要生成少量随机数，则较小的表大小会更好。（much）引导表相对于给定概率向量长度的大小可以通过 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 需要具有签名 def pmf(self, x: float) -> float 的 PMF，它首先使用 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。
例如，要计算 \(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