Wichtelrunde 2020

[euklid]

Hab ich richtig gerechnet, dass die Wahrscheinlichkeit, genau einen Zykel (sorry: Rundweg :-) zu ziehen, 1/13 beträgt?

Kann man einfach begründen (also ohne Rechnung), warum die Chance auf einen einzigen Zykel bei n Teilnehmer/innen immer exakt 1/n ist?

[ibag]

Naja, es gibt n! Anordnungen und (n-1)! Zyklen, also ist die Wahrscheinlichkeit 1/n.

[euklid]

Cool, Danke!

Dass es (n-1)! Zykeln gibt, wusste ich nicht (d.h. hab es noch nie gehört und hab noch nie darüber nachgedacht). Kann es aber leicht nachvollziehen, keine Hexerei...

[uvo]

Bei Fragen, die eine Auslosung und daraus resultierende Wahrscheinlichkeiten betreffen, muss man folgendes beachten: Die Wahrscheinlichkeit eines bestimmten Ereignisses kann vom verwendeten Losverfahren abhängen. Das wird hier vermutlich nicht der Fall sein, jedes plausible Losverfahren dürfte zum gleichen Ergebnis führen.

Vor ein paar Jahren ist mir mal eine Situation begegnet, wo das Losverfahren massive Auswirkungen haben konnte.

In einer bestimmten Sportart, nennen wir sie Bridge, soll ein kleiner lokaler Bezirkspokal mit acht Teams stattfinden. Diese Teams verteilen sich geographisch wie folgt:
Nord: A, B
Mitte: C, D, E
Süd: F, G, H
Gesucht ist eine Auslosung der ersten Pokalrunde (also vier Matches) mit den Nebenbedingungen, dass erstens kein Nord- gegen ein Südteam spielen darf (die Teilnehmer wollen nicht so weit reisen) und zweitens die beiden Vorjahresfinalisten A und C nicht gegeneinander spielen dürfen.
Wie groß ist die Wahrscheinlichkeit, dass A gegen B spielt?

[HuDu]

Ich gebe mal einen ersten Tipp ab: 55,6%.

In jedem Fall eine interessante Aufgabenstellung.

[Schachus]

Ich erhalte das gleiche Ergebnis wie HuDu, falls alle Auslosungen, die die Nebenbedingungen erfüllen, mit gleicher Wahrscheinlichkeit vom Losverfahren gewählt werden.

[Statistica]

Das Problem erinnert mich an das Auslosungsprocedere bei den Achtfinals der Fussball-Championsleague. Dort kommen aus acht Vorrundengruppen immer die beiden besten zwei ins Achtelfinale. Dort werden die acht Paarungen so gelost, dass

a) Ein Gruppensieger immer gegen einen Gruppenzweiten spielt und
b) Teams, die in der Vorrunde in einer Gruppe waren, nicht gegeneinander spielen dürfen und
c) Teams aus einem Land nicht gegeneinander spielen können.

Wie so etwas in der Praxis funktioniert sieht man hier: https://www.youtube.com/watch?v=E1kTVGhYMx0 (Start ab 11:15)
Die Frage ist schon, ob bei diesem Procedere alle Möglichkeiten gleichwahrscheinlich sind...?

[uvo]

Ja, wenn man jede komplette Auslosung (es gibt 27 Stück) mit gleicher Wahrscheinlichkeit haben will, macht man am besten 27 Lose und zieht eines, dann kommt man auf die genannten 15/27 oder 55,6%.

Jetzt könnte der Ausloser aber wie folgt vorgehen: Man mache 8 Lose, für jedes Team eines.
Schritt 1: Ziehe zufällig zwei Lose. Wenn es sich um eine legale Paarung handelt, nimm diese, andernfalls lege die Lose zurück und wiederhole Schritt 1, solange bis du eine legale Paarung erhältst.
Schritt 2: Dasselbe nochmal. Wenn die vier verbleibenden Teams nicht mehr kompatibel sind, lege die Lose zurück und wiederhole Schritt 2, solange bis du eine legale Paarung mit kompatiblen Restteams erhältst.
Schritt 3: Dasselbe nochmal.

Mit diesem Verfahren ergibt sich aber ein anderes Ergebnis, nämlich nur ca. 54,3% (modulo Rechenfehler).

Woran liegt das?

Nun, auch mit diesem Verfahren erhält man sämtliche möglichen Auslosungen, jede außerdem 24mal (weil man die vier Paarungen auch in 4! möglichen Reihenfolgen erhält). Aber diese 27*24 Möglichkeiten werden nicht alle mit gleicher Wahrscheinlichkeit gezogen, beispielsweise hat

CF, AB, DH, EG

die Wahrscheinlichkeit 1/21*1/11*1/6 (für Schritt 1 gibt es 21 Möglichkeiten, für Schritt 2 noch 11 und für Schritt 3 noch 6), hingegen hat

DF, AB, CH, EG

die Wahrscheinlichkeit 1/21*1/9*1/6, weil es im zweiten Schritt nur 10 legale Möglichkeiten gibt und eine davon (BE) zu inkompatiblen Restteams führt.

[Schachus]

Ich habe nicht nachgerechnet, aber mir scheint es intuitiv sehr plausibel, dass die Wahrscheinlichkeit auf diese Weise geringer ist.

Meine Heuristik geht so: AB ist deswegen relativ wahrscheinlich, weil durch das auswählen von AB automatisch alle Nebenbedingungen erfüllt sind (deshalb ist es wahrscheinlicher, als das A gegen D oder E spielt). Wenn man einen "Greedy"-Ansatz wie beschrieben wählt, gibt es eine Chance, dass bereits früh entschieden wird, ob AB zustande Kommt oder nicht (das Ergebnis des ersten Zugs wird ja "eingeloggt", wenn dort A oder B dabei waren, steht bereits fest, ob sie gegeneinander spielen). In diesem ersten Zug sind aber alle legalen Paarungen gleichberechtigt, "der Vorteil" dass spätere Konflikte ausgeschlossen werden, kommt also nicht zzum tragen. Ist das eine nachvollziehbare Heuristik

Mann vergleiche mit dem modifizierten Losverfahren 2:
Schritt 1 wie oben.
Schritt 2 und 3 ebenfalls wie oben, aber wenn ein unmögliches Los gezogen wird, wird nicht nur dieses Los neu gezogen, sondern von 0 angefangen.

Damit sollten alle 27 Kombinationen (oder 24* 27 mit Reihenfolge), die gleiche Change haben (jedes dieser 24 * 27 kommt nach dem ersten Dutrchlauf aller Schritte bis zum Ende oder zum Abbruch Losdurchgang mit Wsk. 1/2520 vor, in den restlichen Fällen wird irgendwann abgebrochen und es geht von 0 los).
Es ist intuitiv, dass Losverfahren 2 der Kombination AB mehr Chancen gibt. Denn wenn AB im ersten oder zweiten Schritt gezogen wird, ist nach wie vor sicher, dass AB rauskommt (ein späterer Abbruch kann nicht vorkommen, alle Nebenbedingungen sind bereits erfüllt). Wird aber im ersten Schritt etwas anderes gezogen (was für die Chancen der Paarung AB schlecht wäre), kann das noch "annuliert" werden, und doch noch AB rauskommen. Das ist natürlich kein Beweis, ( auch nicht alle anderen ersten Züge sind schlecht für AB, ein erster Zug D gegen E wäre für die Chancen von AB z.B. auch sehr gut ), es ist nur meine Intuition

Ich könnte mir sogar vorstellen, dass so etwas allgemein gilt: (Vermutung) Wenn ich 2n Mannschaften habe und eine Menge verbotener Paarungen mit der Eigenschaft, dass alle verbotenen Paarungen genau eines von 2 Teams A,B, beinhalten. Dann ist die Chance, dass A, B gegeneinander Spielen, bei einem Greedy-Losverfahren wie von uvo beschrieben kleiner oder gleich der Wahrscheinlichkeit, die sich bei einer Gleichverteilung aller legalen Kombinationen von n Paarungen ergibt. Ich denke mal drüber nach.

[olima]

Ich sollte doch häufiger in das Forum hier schauen... wirklich schön, wie hier aus dem Thema Wichteln eine Denk-Sport-Aufgabe wurde.