Transformationsalgorithmen für diskrete Verteilungen

• Wenn Pseudozufallszahlen $x_1,x_2\ldots$ erzeugt werden sollen,
  • die als Realisierungen von diskreten Zufallsvariablen $X_1,X_2\ldots$ aufgefasst werden können,
  • welche jeweils die Werte $a_0,a_1\ldots\in\mathbb{R}$ mit den Wahrscheinlichkeiten $p_j=P(X_i=a_j)\ge0$ für $j=0,1,\ldots$ annehmen.
• Dann ist es manchmal zweckmäßig, wie folgt vorzugehen:
  • Sei $U$ eine $(0,1]$-verteilte Zufallsvariable, und die Zufallsvariable $X$ sei gegeben durch

    $$X=\left\{\begin{array}{ll} a_0\,, &\mbox{falls $U<p_0$,}\\ a_1\,... ...falls $p_0+\ldots+p_{j-1}\le U<p_0+\ldots+p_j$,}\\ \vdots & \end{array}\right.$$ (13)

    
    

  • Dann gilt $P(X=a_j)=p_j$ für jedes $j=0,1,\ldots$.
• Die Pseudozufallszahlen $x_1,\ldots,x_n$ mit
  $$x_i=\left\{\begin{array}{ll} a_0\,, &\mbox{falls $u_i<p_0$,}\\ ... ...s $p_0+\ldots+p_{j-1}\le u_i<p_0+\ldots+p_j$,}\\ \vdots & \end{array}\right.$$
  • können somit als Realisierungen von unabhängigen und ${\mathbf{p}}$-verteilten Zufallsvariablen aufgefasst werden, wobei ${\mathbf{p}}=(p_0,p_1,\ldots)^\top$,
  • falls $u_1,\ldots,u_n$ die Realisierungen von unabhängigen und im Intervall $(0,1]$ gleichverteilten Zufallsvariablen $U_1,\ldots,U_n$ sind.

Beispiel

$\;$ (Geometrische Verteilung) 

• Wir betrachten die folgenden Werte $a_j$ und die zugehörigen (Einzel-) Wahrscheinlichkeiten $p_j$.
  • Sei $a_j=j$ für $j=0,1,\ldots$, und für $0<p<1$ mit $q=1-p$ sei
    $$p_j=\left\{\begin{array}{ll} 0\,, &\mbox{falls $j=0$,}\\ p\,q^{j-1}\,, &\mbox{falls $j\ge 1$.} \end{array}\right.$$

  • Dann gilt für jedes $j\ge 1$

    $$1-(p_1+\ldots+p_j)=p_{j+1}+p_{j+2}+\ldots=p\sum_{i=j}^\infty q^i=q^j$$ (14)

    
    
    bzw. $p_j =q^{j-1}-q^j$.

  
  

• Außerdem betrachten wir die Zufallsvariable

  $$X=\left\lfloor\frac{\log U}{\log q}\right\rfloor +1\,,$$ (15)

  
  
  wobei $U$ eine $(0,1]$-gleichverteilte Zufallsvariable ist und $\left\lfloor z\right\rfloor$ den ganzzahligen Teil von $z$ bezeichnet.

  
  

• Dann gilt $P(X=j)=p\,q^{j-1}$ für jedes $j=1,2,\ldots$, d.h. $X\sim$ Geo$(p)$,
  • denn aus (14) und (15) ergibt sich, dass
    

    $$X \stackrel{(\ref{for.peh.zwe})}{=} \min\Bigl\{j\ge 1:\,j>\;\frac{\log U}{\log q}\Bigr\}$$

    $$= \min\Bigl\{j\ge 1:\,j \log q <\log U\Bigr\}$$

    $$= \min\Bigl\{j\ge 1:\, q^j <U\Bigr\}$$

    $$= \sum\limits_{j=1}^\infty j\;{1\hspace{-1mm}{\rm I}}\bigl(q^j<U\le q^{j-1}\bigr)$$

    $$\stackrel{(\ref{for.peh.ein})}{=} \sum\limits_{j=1}^\infty j\;{1\hspace{-1mm}{\rm I}}\bigl(p_1+\ldots+p_{j-1}\le1-U<p_1+\ldots+p_j\bigr)\Biggr)\,,$$

    
    

  • wobei die Zufallsvariable $1-U$ ebenfalls $(0,1]$-gleichverteilt ist.

  
  

• Die Pseudozufallszahlen $x_1,\ldots,x_n$ mit
  $$x_i=\left\lfloor\frac{\log u_i}{\log q}\right\rfloor +1$$
  • können somit als Realisierungen von unabhängigen und geometrisch verteilten Zufallsvariablen $X_1,\ldots,X_n\sim$ Geo$(p)$ aufgefasst werden,
  • falls $u_1,\ldots,u_n$ die Realisierungen von unabhängigen und im Intervall $(0,1]$ gleichverteilten Zufallsvariablen $U_1,\ldots,U_n$ sind.

Für einige diskrete Verteilungen gibt es spezielle Transformationsalgorithmen, um Pseudozufallszahlen zu erzeugen, die als Realisierungen von Zufallsvariablen mit einer solchen Verteilung aufgefasst werden können.

Beispiele

 

1. Poisson-Verteilung $\;$ (mit kleinem Erwartungswert $\lambda$)
   • Falls $\lambda>0$ eine kleine Zahl ist, dann ist das folgende Verfahren geeignet, um Poisson-verteilte Pseudozufallszahlen durch die Transformation
     • von exponentialverteilten Pseudozufallszahlen (auf ähnliche Weise wie in Abschnitt 3.2.1)
     • oder direkt aus $(0,1]$-gleichverteilten Pseudozufallszahlen
     zu erzeugen.
   • Die Zufallsvariablen $X_1,X_2,\ldots$ seien unabhängig und Exp$(\lambda)$-verteilt.
     • Für die Zufallsvariable $Y=\max\{k\ge 0:\, X_1+\ldots+X_k\le 1\}$ ergibt sich dann aus der Darstellungsformel (11) für die Verteilungsfunktion der Erlang-Verteilung, dass für jedes $j\ge 0$
       

       $$P(Y=j) = P(Y\ge j)-P(Y\ge j+1)$$

       $$= P(X_1+\ldots+X_j\le 1)-P(X_1+\ldots+X_{j+1}\le 1)$$

       $$= \int\limits_0^1\displaystyle\frac{\lambda e^{-\lambda v}(\lambda ... ...;\int\limits_0^1\displaystyle\frac{\lambda e^{-\lambda v}(\lambda v)^j}{j!}\;dv$$

       $$= \int\limits_0^1\displaystyle\frac{d}{dv}\,\Bigl(\,\frac{ e^{-\lambda v}(\lambda v)^j}{j!}\,\Bigr)\,dv$$

       $$= \frac{ e^{-\lambda}\lambda^j}{j!}\;.$$

       
       

     • Mit anderen Worten: Es gilt $Y\sim$ Poi$(\lambda)$.
   • Die Pseudozufallszahlen $y_1,\ldots,y_n$ mit

     $$y_i = \max\{k\ge 0:\,x_1+\ldots+x_k\le i\}-y_{i-1}\,,\qquad\forall\, i=1,\ldots,n\,,$$ (16)

     
     
     bzw.

     $$y_i = \max\{k\ge 0:\,u_1\cdot\ldots\cdot u_k\ge e^{-i\lambda}\}-y_{i-1}\,,\qquad\forall\, i=1,\ldots,n\,,$$ (17)

     
     
     wobei $y_0=0$ und $x_j=-\lambda^{-1}\log u_j$ für $j=1,2,\ldots$,
     • können somit als Realisierungen von unabhängigen und Poi$(\lambda)$-verteilten Zufallsvariablen aufgefasst werden,
     • falls $x_1,x_2\ldots$ die Realisierungen von unabhängigen und Exp$(\lambda)$-verteilten Zufallsvariablen $X_1,X_2\ldots$ sind bzw.
     • falls $u_1,u_2\ldots$ die Realisierungen von unabhängigen und im Intervall $(0,1]$ gleichverteilten Zufallsvariablen $U_1,U_2\ldots$ sind.
   • Beachte 
     • Weil der Erwartungswert der Poi$(\lambda)$-Verteilung gleich $\lambda$ ist, sind bei dem durch (16) bzw. (17) gegebenen Algorithmus im Mittel $\lambda$ gleichverteilte Pseudozufallszahlen erforderlich, um eine neue Poi$(\lambda)$-verteilte Pseudozufallszahl zu erzeugen.
     • Dieser Aufwand lässt sich reduzieren, wenn für große $\lambda$ wie folgt vorgegangen wird.

   
   

2. Poisson-Verteilung $\;$ (mit großem Erwartungswert $\lambda$)
   • Falls $\lambda>0$ eine große Zahl ist, wobei $a_j=j$ und $p_j=e^{-\lambda}\lambda^j/j!$ für $j=0,1,\ldots$,
     • dann ist das unmittelbar auf dem Transformationsansatz (13) beruhende Verfahren besser geeignet, um Poi$(\lambda)$-verteilte Pseudozufallszahlen zu erzeugen,
     • wenn dabei die Gültigkeit der Ungleichungen

       $$U<p_0\,,\quad p_0\le U<p_0+p_1\,,\ldots, p_0+\ldots+p_{j-1}\le U<p_0+\ldots+p_j\,,\ldots$$ (18)

       
       
       in der folgenden Reihenfolge überprüft wird,
     • wobei die Rekursionsformel
       $$p_{j+1}=\frac{\lambda}{j+1}\;p_j\,,\qquad\forall\, j\ge 0\,,$$
       zur Berechnung der Summen $P_j=\sum_{k=0}^j p_k$ für $j\ge 0$ verwendet wird.
   • Sei ${\left\lfloor \lambda\right\rfloor}>0$ der ganzzahlige Teil von $\lambda$. Dann wird zunächst geprüft, ob $U<P_{\left\lfloor \lambda\right\rfloor}$ gilt.
     • Falls diese Ungleichung gilt, dann wird geprüft, ob $U<P_{{\left\lfloor \lambda\right\rfloor}-1},U<P_{{\left\lfloor \lambda\right\rfloor}-2},\ldots$ gilt, wobei in diesem Fall $X=\min\{k:\, U<P_k\}$ gesetzt wird.
     • Falls $U<P_{\left\lfloor \lambda\right\rfloor}$ nicht gilt, dann wird geprüft, ob $U<P_{{\left\lfloor \lambda\right\rfloor}+1},U<P_{{\left\lfloor \lambda\right\rfloor}+2},\ldots$ gilt, wobei erneut $X=\min\{k:\, U<P_k\}$ gesetzt wird.
   • Für den Erwartungswert ${\mathbb{E}\,}V$ der dabei erforderlichen Anzahl $V$ von Überprüfungen gilt dann näherungsweise, dass
     

     $${\mathbb{E}\,}V \approx 1+{\mathbb{E}\,}\vert X-\lambda\vert$$

     $$= 1+\sqrt{\lambda}{\mathbb{E}\,}\Bigl(\frac{\vert X-\lambda\vert}{\sqrt{\lambda}}\Bigr)$$

     $$\approx 1+ 0.798\,\sqrt{\lambda}\,,$$

     
     
     • wobei in der letzten Approximationsformel die Tatsache genutzt wurde, dass die Zufallsvariable $(X-\lambda)/\sqrt{\lambda}$ für große $\lambda$ näherungsweise N$(0,1)$-verteilt ist,
     • was sich aus der Faltungsstabilität der Poisson-Verteilung und aus dem zentralen Grenzwertsatz für Summen von unabhängigen und identisch verteilten Zufallsvariablen (Theorem WR-5.16) ergibt.
   • Bei dieser Vorgehensweise wächst also
     • die im Mittel erforderliche Anzahl von Überprüfungen nur wie die Quadratwurzel $\sqrt{\lambda}$ von $\lambda$,
     • wogegen bei dem vorher diskutierten Verfahren zur Erzeugung Poi$(\lambda)$-verteilter Pseudozufallszahlen die jeweils im Mittel erforderliche Anzahl von Standard-Pseudozufallszahlen wie $\lambda$ wächst.

   
   

3. Binomial-Verteilung 
   • Bei der Erzeugung von binomialverteilten Pseudozufallszahlen kann man ähnlich wie im Fall der Poisson-Verteilung vorgehen.
     • Für beliebige, jedoch fest vorgegebene Zahlen $n\in\mathbb{N}$ und $p\in(0,1)$ mit $q=1-p$ sei
       $$a_j=j$$   und$$\qquad p_j=\frac{n!}{j!\,(n-j)!}\;p^j\,q^{n-j}\,,\qquad\forall\, j=0,1,\ldots,n\,.$$

     • Für $j=0,1,\ldots,n$ werden dann die Summen $P_j=\sum_{k=0}^j p_k$ mit der Rekursionsformel
       $$p_{j+1}=\frac{n-j}{j+1}\;\frac{p}{q}\;p_j\,,\qquad\forall\, j=0,1,\ldots,n-1$$
       berechnet.
   • Falls $np>0$ klein ist, dann wird
     • die Gültigkeit der Ungleichungen (18) in der natürlichen Reihenfolge überprüft,
     • wobei mit $U<p_0$ begonnen und $X=\min\{k:\, U<P_k\}$ gesetzt wird.
   • Falls $np$ groß ist,
     • dann ist es effizienter, die Gültigkeit der Ungleichungen (18) in der folgenden Reihenfolge zu verifizieren. Dabei wird zunächst geprüft, ob $U<P_{\left\lfloor np\right\rfloor}$ gilt.
     • Falls diese Ungleichung gilt, dann wird geprüft, ob $U<P_{{\left\lfloor np\right\rfloor}-1},U<P_{{\left\lfloor np\right\rfloor}-2},\ldots$ gilt, wobei in diesem Fall $X=\min\{k:\, U<P_k\}$ gesetzt wird.
     • Falls $U<P_{\left\lfloor np\right\rfloor}$ nicht gilt, dann wird geprüft, ob $U<P_{{\left\lfloor np\right\rfloor}+1},U<P_{{\left\lfloor np\right\rfloor}+2},\ldots$ gilt, wobei erneut $X=\min\{k:\, U<P_k\}$ gesetzt wird.