Erzeugen einer uniformen Verteilung

22.03.2021, 02:39

schlauchsteher123

Erzeugen einer uniformen Verteilung

Meine Frage:
Sei A ein probabilistischer Algorithmus, welcher immer nach einer endlichen Anzahl Schritte terminiert und dessen Ausgabe eine uniform verteilte Zufallsvariable
U_{n} \in {1, . . . , n}
ist, d.h., mit
P_{U_{n}}(u) = \frac{1}{n} für u ? {1, . . . , n}.
Algorithmus A hat eine Quelle von beliebig vielen uniform zufälligen Bits zur Verfügung aber keine anderen Zufallsquellen.
Beweisen Sie, dass kein solcher Algorithmus A existiert, ausser wenn n = 2^{k} für ein k ? \mathbb N.

Meine Ideen:
Also ich komme zum Ansatz, dass ich eine Funktion denfienieren müsste die von einer Menge mit m = 2^{k} Elementen, für ein k ? \mathbb N, auf eine andere Menge mit n Elementen, sodass n nicht m teilt oder umgekehrt. Aber aus der Definition erschliesst es sich, dass ich eine Funktion erstellen müsste die mit einer W'keit 1/p für jedes Element in der Grundmenge auf mehrere Elemente der Zielmenge gehen müsste. Für das p gilt eigentlich nur die Forderung, dass p \neq 2^{k} für alle k \in \mathbb Z. Dies geht aber nicht, solange ich nicht eine beliebige Zufallsvariable generieren kann, sodass ich alle Primzahlen uniform abbilden kann. Wie ich dies nun mathematisch formulieren kann? Hier komme ich nicht weiter...

22.03.2021, 09:47

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von schlauchsteher123
Algorithmus A hat eine Quelle von beliebig vielen uniform zufälligen Bits zur Verfügung aber keine anderen Zufallsquellen.

Beliebig viel soll aber doch heißen endlich viel in dem Sinne, dass man eine obere Schranke $\begin{eqnarray*} s \end{eqnarray*}$ für die zur Verfügung stehene Bitzahl hat.

Das bedeutet dann, dass man sich in einem Laplaceschen Wahrscheinlichkeitsraum $\begin{eqnarray*} \Omega \end{eqnarray*}$ mit $\begin{eqnarray*} |\Omega| = 2^s \end{eqnarray*}$ bewegt, in dem alle - ausnahmslos alle - Ereignisse dann eine Wahrscheinlichkeit aufweisen, die ein ganzzahliges Vielfaches von $\begin{eqnarray*} \frac{1}{|\Omega|}=\frac{1}{2^s} \end{eqnarray*}$ ist.

Für die diskrete Gleichverteilung auf $\begin{eqnarray*} \{1,2,\ldots,n\} \end{eqnarray*}$ benötigen wir Ereignisse mit Wahrscheinlichkeit $\begin{eqnarray*} \frac{1}{n} \end{eqnarray*}$ . Nun bedeutet $\begin{eqnarray*} \frac{1}{n}\stackrel{?}{=}\frac{k}{2^s} \end{eqnarray*}$ umgestellt $\begin{eqnarray*} 2^s\stackrel{?}{=}k\cdot n \end{eqnarray*}$ , was nur für Zweierpotenzen $\begin{eqnarray*} n \end{eqnarray*}$ möglich ist.

Praktisches Beispiel: Wenn man aus einem 32Bit-Integer-Randomwert $\begin{eqnarray*} R \end{eqnarray*}$ (d.h. $\begin{eqnarray*} R\in \left\{0,1,\ldots,2^{32}-1\right\} \end{eqnarray*}$ ) eine Gleichverteilung auf $\begin{eqnarray*} \{1,\ldots,7\} \end{eqnarray*}$ generieren will, dann geht man gewöhnlich so vor:

$\begin{eqnarray*} X = 1 + \left(R\bmod 7\right) \end{eqnarray*}$

Das Ergebnis ist dann aber NICHT $\begin{eqnarray*} P(X=k) = \frac{1}{7} \end{eqnarray*}$ für $\begin{eqnarray*} k=1,\ldots,7 \end{eqnarray*}$ , sondern stattdessen

$\begin{eqnarray*} P(X=1) = P(X=2) = P(X=3) = P(X=4) = \frac{613\,566\,757}{2^{32}} \end{eqnarray*}$ und $\begin{eqnarray*} P(X=5) = P(X=6) = P(X=7) = \frac{613\,566\,756}{2^{32}} \end{eqnarray*}$ .

Der "Fehler" $\begin{eqnarray*} 0.997\cdot 10^{-10} < \left|P(X=k)-\frac{1}{7}\right|< 1.34\cdot 10^{-10} \end{eqnarray*}$ ist vermutlich für die meisten Belange tolerierbar, aber er ist da.

Neue Frage »

Antworten »

Erzeugen einer uniformen Verteilung

Verwandte Themen