Die Wahrscheinlichkeit von Bogosort

Question

Aufgabe:

Wie wahrscheinlich ist es, dass die Menge [2, 2, 18, 33, 7, 99, 1, 2] durch zufälliges Ziehen bereits aufsteigend (ai+1 grössergleich ai) sortiert ist? (2=2 ist dabei das Gleiche wie 2=2)

Problem/Ansatz:

Bogosort, aber wie berechne ich die Wahrscheinlichkeit davon?

Answer 1

Aloha :)

Es muss zuerst die \(1\) gezogen werden. Die Wahrscheinlichkeit dafür ist \(\frac{1}{8}\).

Von den sieben verbliebenen Zahlen müssen die drei \(2\)en als nächstes gezogen werden. Die Wahrscheinlichkeit dafür ist \(\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}\)

Dann muss die \(7\) gezogen werden. Das passiert mit der Wahrscheinlichkeit \(\frac{1}{4}\).

Es müssen die \(18\) mit der Wahrscheinlichkeit \(\frac{1}{3}\), die \(33\) mit der Wahrscheinlichkeit \(\frac{1}{2}\) und schließlich als letztes die \(99\) mit der Wahrscheinlichkeit \(\frac{1}{1}=1\) folgen.

Fassen wir alles zusammen, ist die Wahrscheinlichkeit, die Zahlen in sortierter Reihenfolge zu ziehen:$$p=\frac{1}{8}\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}\cdot\frac{1}{4}\cdot\frac{1}{3}\cdot\frac{1}{2}\cdot\frac{1}{1}=\frac{3!}{8!}=\frac{1}{6720}$$

Answer 2

Wie wahrscheinlich ist es, dass die Menge [2, 2, 18, 33, 7, 99, 1, 2] durch zufälliges Ziehen aufsteigend sortiert ist?

1/8·3/7·2/6·1/5·1/4·1/3·1/2·1/1 = 1/6720