Permutationen

02.11.2019, 23:15

Zucker

Permutationen

Hallo,

Ich arbeite an einer Übungsaufgabe und komme nicht weiter. Und zwar ist die Aufgabenstellung wie folgt:

Sei $\begin{eqnarray*} A(1,...,n) = (1, ..., n) \end{eqnarray*}$ ein Vektor. Nun denke man sich einen Algorithmus, welcher eine zufällige Permutation der Einträge von $\begin{eqnarray*} A \end{eqnarray*}$ erzeugt, d.h. INPUT = A, OUTPUT = A', wobei $\begin{eqnarray*} A'(1,...,n) \end{eqnarray*}$ ein Vektor ist, dessen Einträge eben eine Permutation der Vektoreinträge von $\begin{eqnarray*} A \end{eqnarray*}$ sind.

"Um zu zeigen, dass jede zufällig erzeugte Permutation mit gleicher Wahrscheinlichkeit auftritt, reicht es nicht, zu zeigen, dass für jedes Element $\begin{eqnarray*} A(i) \end{eqnarray*}$ die Wahrscheinlichkeit, dass $\begin{eqnarray*} A(i) = A'(j) \end{eqnarray*}$ ist gleich $\begin{eqnarray*} \tfrac{1}{n} \end{eqnarray*}$ ist. Finden Sie ein Gegenbeispiel, wo zweiteres erfüllt ist, aber ersteres nicht."

Weiß hier jemand weiter? Bin für jede Hilfe dankbar.

Grüße,

Zucker

02.11.2019, 23:31

HAL 9000

Auf diesen Beitrag antworten »

Nimm einfach einen Algorithmus, der nur eine gleichverteilte Zufallszahl $\begin{eqnarray*} s\in\{1,\ldots,n\} \end{eqnarray*}$ auswürfelt und definiere dann $\begin{eqnarray*} A' \end{eqnarray*}$ gemäß $\begin{eqnarray*} A'(k) := A(1+((k+s-1)\bmod n)) \end{eqnarray*}$ für $\begin{eqnarray*} k=1,\ldots,n \end{eqnarray*}$ .

D.h., es wird nur unter $\begin{eqnarray*} n \end{eqnarray*}$ Permutationen ausgewürfelt statt wie gefordert unter allen $\begin{eqnarray*} n! \end{eqnarray*}$ Permutationen. Ist natürlich erst für $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ wirklich ein Gegenbeispiel, aber so ist es ja womöglich auch gemeint.

02.11.2019, 23:36

Zucker

Auf diesen Beitrag antworten »

Danke für die schnelle Antwort!

Hm, ja, es stellt sich nun die Frage, wie die Angabe gemeint ist. Wenn darin von "jede zufällig erzeugte Permutation" die Rede ist, sind da tatsächlich alle möglichen Permutationen gemeint, oder nur die die ein bestimmter Algorithmus auch als möglichen Output liefern kann.

Soll heißen, wenn ich z.B. einen Algorithmus habe, der eine zufällige zyklische Permutationen von (1,...,n) ausgibt, und nur eine solche zyklische, soll ich dann zeigen, dass unter diesen zyklischen Permutationen jede zyklische Permutation gleich wahrscheinlich ist, oder ist die Tatsache, dass nur zyklische Permutationen als Output vorkommen bereits die Lösung der Aufgabe (weil alle anderen Permutationen Wahrscheinlichkeit 0 haben)? Wäre ersteres zu zeigen denn überhaupt möglich?

LG,

Zucker

03.11.2019, 01:40

HAL 9000

Auf diesen Beitrag antworten »

RE: Permutationen

Zitat:

Original von Zucker
Finden Sie ein Gegenbeispiel, wo zweiteres erfüllt ist, aber ersteres nicht.

Das habe ich oben getan, und habe auch erläutert, dass dieses Beispiel ersteres nicht erfüllt. Ich habe nun dir überlassen zu zeigen, dass es zweiteres erfüllt - alles wollte ich dir ja nun nicht brühwarm vorkauen.

Neue Frage »

Antworten »

Permutationen

Verwandte Themen