Discrete Alias Urn (DAU)#
Erforderlich: Wahrscheinlichkeitsvektor (PV) oder die PMF zusammen mit einem endlichen Definitionsbereich
Geschwindigkeit
Einrichtung: langsam (linear zur Vektorlänge)
Stichprobenerhebung: sehr schnell
DAU zieht Stichproben aus Verteilungen mit beliebigen, aber endlichen Wahrscheinlichkeitsvektoren (PV) der Länge N. Der Algorithmus basiert auf einer genialen Methode von A.J. Walker und erfordert eine Tabelle von mindestens N Einträgen. Er benötigt eine Zufallszahl und nur einen Vergleich für jede erzeugte Zufallsvariable. Die Einrichtungszeit für die Konstruktion der Tabellen beträgt 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
Standardmäßig beginnt die Indizierung des Wahrscheinlichkeitsvektors bei 0. Dies kann jedoch durch Übergabe eines domain Parameters geändert werden. Wenn domain in Kombination mit dem PV angegeben wird, hat dies den Effekt, die Verteilung von (0, len(pv)) nach (domain[0], domain[0] + len(pv)) zu verschieben. domain[1] wird in diesem Fall ignoriert.
>>> rng = DiscreteAliasUrn(pv, domain=(10, 13), random_state=urng)
>>> rng.rvs()
12 # may vary
Die Methode funktioniert auch, wenn kein Wahrscheinlichkeitsvektor, sondern eine PMF angegeben wird. In diesem Fall muss entweder explizit ein begrenzter (endlicher) Definitionsbereich über den domain Parameter übergeben oder eine support Methode im Verteilungsobjekt bereitgestellt werden.
>>> 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()
Hinweis
Da DiscreteAliasUrn PMFs mit der Signatur def pmf(self, x: float) -> float erwartet, vektorisiert es die PMF zunächst mit np.vectorize und wertet sie dann über alle Punkte im Definitionsbereich aus. Wenn die PMF jedoch bereits vektorisiert ist, ist es deutlich schneller, sie einfach an jedem Punkt des Definitionsbereichs auszuwerten und den erhaltenen PV zusammen mit dem Definitionsbereich zu übergeben. Beispielsweise sind die pmf Methoden von diskreten Verteilungen in SciPy vektorisiert, und ein PV kann wie folgt erhalten werden:
>>> 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)
Der Definitionsbereich ist hier erforderlich, um die Verteilung zu verschieben.
Die Leistung kann durch die Einstellung der Größe der verwendeten Tabelle leicht beeinflusst werden, was durch Übergabe eines urn_factor Parameters geändert werden kann.
>>> # 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
Hinweis
Es wird empfohlen, diesen Parameter unter 2 zu halten.
Weitere Details zu dieser Methode finden Sie unter [1] und [2].