Discrete Guide Table (DGT)#

  • Erforderlich: Wahrscheinlichkeitsvektor (PV) oder die PMF zusammen mit einem endlichen Definitionsbereich

  • Geschwindigkeit

    • Einrichtung: langsam (linear mit der Vektorlänge)

    • Sampling: sehr schnell

DGT sampelt aus beliebigen, aber endlichen Wahrscheinlichkeitsvektoren. Zufallszahlen werden mit der Inversionsmethode generiert, d.h.

  1. Generiere eine Zufallszahl U ~ U(0,1).

  2. Finde die kleinste ganze Zahl I, so dass F(I) = P(X<=I) >= U.

Schritt (2) ist der entscheidende Schritt. Die sequentielle Suche erfordert O(E(X)) Vergleiche, wobei E(X) der Erwartungswert der Verteilung ist. Die indizierte Suche verwendet jedoch eine Führungstabelle, um zu einem in der Nähe von I liegenden I' <= I zu springen, um X in konstanter Zeit zu finden. Tatsächlich wird die erwartete Anzahl von Vergleichen auf 2 reduziert, wenn die Führungstabelle die gleiche Größe wie der Wahrscheinlichkeitsvektor hat (dies ist die Standardeinstellung). Für größere Führungstabellen wird diese Zahl kleiner (ist aber immer größer als 1), für kleinere Tabellen wird sie größer.

Andererseits beträgt die Einrichtungszeit für die Führungstabelle O(N), wobei N die Länge des Wahrscheinlichkeitsvektors bezeichnet (für Größe 1 ist keine Vorverarbeitung erforderlich). Darüber hinaus können bei sehr großen Führungstabellen Speicherabhängigkeiten die Geschwindigkeit des Algorithmus sogar reduzieren. Daher empfehlen wir nicht die Verwendung von Führungstabellen, die mehr als dreimal so groß sind wie der gegebene Wahrscheinlichkeitsvektor. Wenn nur wenige Zufallszahlen generiert werden müssen, sind (viel) kleinere Tabellengrößen besser. Die Größe der Führungstabelle relativ zur Länge des gegebenen Wahrscheinlichkeitsvektors kann über den Parameter guide_factor eingestellt werden

>>> 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

Standardmäßig wird der Wahrscheinlichkeitsvektor ab 0 indiziert. Dies kann jedoch durch Übergabe eines Parameters domain geändert werden. Wenn domain in Kombination mit dem PV übergeben 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 = DiscreteGuideTable(pv, random_state=urng, domain=(10, 13))
>>> rng.rvs()
10   # may vary

Die Methode funktioniert auch, wenn anstelle eines Wahrscheinlichkeitsvektors eine PMF gegeben ist. In diesem Fall muss ein begrenzter (endlicher) Definitionsbereich entweder durch explizite Übergabe des Parameters domain oder durch Bereitstellung einer support-Methode im Verteilungsobjekt angegeben 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 = DiscreteGuideTable(dist, random_state=urng)
>>> rng.rvs()
9     # may vary

Hinweis

Da DiscreteGuideTable PMFs mit der Signatur def pmf(self, x: float) -> float erwartet, vektorisiert es zunächst die PMF mit np.vectorize und wertet sie dann über alle Punkte im Definitionsbereich aus. Wenn die PMF jedoch bereits vektorisiert ist, ist es viel schneller, sie einfach an jedem Punkt des Definitionsbereichs auszuwerten und den erhaltenen PV zusammen mit dem Definitionsbereich zu übergeben. Zum Beispiel sind die pmf-Methoden von SciPys diskreten Verteilungen vektorisiert, und ein PV kann durch Folgendes erhalten werden:

>>> 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)

Hier wird der Definitionsbereich benötigt, um die Verteilung zu verschieben

Die Größe der Führungstabelle relativ zum Wahrscheinlichkeitsvektor kann mit dem Parameter guide_factor eingestellt werden. Größere Führungstabellen führen zu schnellerer Generierungszeit, erfordern jedoch eine teurere Einrichtung.

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

Leider ist die PPF selten in geschlossener Form verfügbar oder zu langsam, wenn sie verfügbar ist. Der Benutzer muss nur den Wahrscheinlichkeitsvektor angeben, und die PPF (inverse CDF) kann mit der Methode ppf ausgewertet werden. Diese Methode berechnet die (exakte) PPF der gegebenen Verteilung.

Um beispielsweise die PPF einer Binomialverteilung mit \(n=4\) und \(p=0.1\) zu berechnen: können wir eine Führungstabelle wie folgt einrichten

>>> 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

Weitere Details zu dieser Methode finden Sie unter [1] und [2].

Referenzen#

Auf dieser Seite