離散別名甕 (DAU)#
需求：機率向量 (PV) 或 PMF 以及有限域
速度
設定：慢速（與向量長度呈線性關係）
抽樣：非常快速
DAU 從長度為 N 的任意但有限的機率向量 (PV) 的分佈中取樣。該演算法基於 A.J. Walker 的巧妙方法，並且需要大小（至少）為 N 的表格。對於每個產生的隨機變量，它需要一個隨機數和僅一次比較。建構表格的設定時間為 O(N)。
>>> import numpy as np
>>> from scipy.stats.sampling import DiscreteAliasUrn
>>>
>>> pv = [0.18, 0.02, 0.8]
>>> urng = np.random.default_rng()
>>> rng = DiscreteAliasUrn(pv, random_state=urng)
>>> rng.rvs()
0 # may vary
預設情況下，機率向量的索引從 0 開始。但是，可以透過傳遞 domain 參數來變更此設定。當 domain 與 PV 結合使用時，它具有將分佈從 (0, len(pv)) 重新定位到 (domain[0], domain[0] + len(pv)) 的效果。domain[1] 在這種情況下會被忽略。
>>> rng = DiscreteAliasUrn(pv, domain=(10, 13), random_state=urng)
>>> rng.rvs()
12 # 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 = DiscreteAliasUrn(dist, random_state=urng)
>>> rng.rvs()
10 # may vary
>>> import matplotlib.pyplot as plt
>>> from scipy.stats.sampling import DiscreteAliasUrn
>>> 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)
>>> urng = np.random.default_rng()
>>> rng = DiscreteAliasUrn(dist, random_state=urng)
>>> rvs = rng.rvs(1000)
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> x = np.arange(1, 11)
>>> fx = dist.pmf(x)
>>> fx = fx / fx.sum()
>>> ax.plot(x, fx, 'bo', label='true distribution')
>>> ax.vlines(x, 0, fx, lw=2)
>>> ax.hist(rvs, bins=np.r_[x, 11]-0.5, density=True, alpha=0.5, color='r',
... label='samples')
>>> ax.set_xlabel('x')
>>> ax.set_ylabel('PMF(x)')
>>> ax.set_title('Discrete Alias Urn Samples')
>>> plt.legend()
>>> plt.show()
注意
由於 DiscreteAliasUrn 期望 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 DiscreteAliasUrn
>>> 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 = DiscreteAliasUrn(pv, domain=domain)
此處需要域來重新定位分佈。
效能可能會受到設定使用表格大小的輕微影響，而表格大小可以透過傳遞 urn_factor 參數來變更。
>>> # use a table twice the length of PV.
>>> urn_factor = 2
>>> rng = DiscreteAliasUrn(pv, urn_factor=urn_factor, random_state=urng)
>>> rng.rvs()
2 # may vary
注意
建議將此參數保持在 2 以下。