Das Abstimmungsproblem (ballot problem) Grundlagen: Binomialkoeffizienten n   Die Anzahl der Möglichkeiten aus n Objekten k auszuwählen. Die Reihenfolge wird k  nicht beachtet. k ≤ n Es gilt: n n!   =  k  k!*(n − k )! Aufgabenstellung: Bei einer Wahl standen sich die Kandidaten A und B gegenüber und im Ergebnis dieser Wahl fielen a Stimmen auf den Kandidaten A und b Stimmen auf den Kandidaten B, wobei a>b gelten soll. Wir wollen die Wahrscheinlichkeit Pa,b dafür berechnen, dass während der Auszählung der Stimmen der Kandidat A die ganze Zeit vor dem Kandidaten B lag. 1,5 1 x 0,5 0 -0,5 -1 -1,5 n Variablen: n: Länge des Weges, Anzahl der Stimmen, a + b=n x: Differenz der Stimmen, a - b = x Den Verlauf der Auszählung von n Stimmen, bei der zum Schluss A mit x Stimmen vor B lag, identifizieren wir mit einem Weg von (0,0) nach (n,x). Nn,x: Anzahl aller möglichen Wege von (0,0) nach (n,x) a: Anzahl der Schritte nach oben b: Anzahl der Schritte nach unten n n Satz 1: Nn,x =   =    a b  Beweis: Die Gleichheit gilt, da es egal ist, ob wir aus einer n-elementigen Menge a Elemente aussuchen oder b Elemente nicht aussuchen. Nun wollen wir noch a und b in Abhängigkeit von n und x darstellen. Dazu formen wir die Gleichung a + b = n nach b [nach a] um und setzen in die Gleichung a – b = x für b = n - a [a = n - b] ein. Dann erhalten wir: a - (n - a) = x (n - b) – b = x 2a = n + x n - x = 2b n+x n−x a= b= 2 2  n  n n+x     Satz 1 besagt also, dass Nn,x =  n + x  =  n − x  mit n ≥ 1 ; ∈ N. 2      2   2  68 Dass die Gleichwahrscheinlichkeit der Wege gilt, zeigen wir anschaulich an einem Beispiel: 1 2 2 3 a 1 b b 1 a a 1 a 1 3 1 2 1 3 b a 1 1 3 1 3 Zurück zur Ausgangsfrage: Wir wollen einen Weg S+, der oberhalb der n-Achse verläuft, finden. Die Anzahl der positiven Wege S+ heißt N+n,x. Die Wahrscheinlichkeit von S+ ist N+ Anzahl der günstigen Wege P(S+) = n , x = Anzahl aller möglichen Wege N n,x Spiegelungsprinzip: Um N +n, x zu bestimmen, benutzen wir als Hilfsmittel das Spiegelungsprinzip: Es seien m, n, r, s positive ganze Zahlen. Die Anzahl der Wege von A(m,r) nach B(n,s), die die n-Achse in einem Punkt (q,0) schneiden oder berühren, ist gleich der Anzahl der Wege von A’(m,-r) nach B(n,s). Aus dem Diagramm wird offensichtlich, dass die Anzahl der Wege von A nach (q,0) gleich der Anzahl der Wege von A’ nach (q,0) ist. Die Anzahl der Wege vom ersten Punkt (q1,0) nach B sind für A und A’ dann gleich. 4 3 2 x 1 0 -1 -2 -3 n Um N +n, x zu finden, müssen wir nun von der Gesamtheit aller Wege Nn,x alle die Wege abziehen, die die n-Achse schneiden oder berühren. Das sind alle die Wege von A’ nach B. Da alle positiven Wege von (0/0) nach (1/1) gehen müssen und (0/0) nicht an der n-Achse gespiegelt werden kann, nehmen wir für A den Punkt (1/1). Wir verschieben das Koordinatensystem; aus n wird n-1 und aus x wird x-1. N +n, x = Nn-1,x-1 – Nn-1,x+1 69   n −1 n −1     =  n −1 + x −1 −  n −1 + x + 1     2 2     n −1  n −1      = n+ x −2−n+ x     2    2  = = = = = (n − 1)! (n − 1)! n+ x n+x n+x n+ x − 1)!*(n − ( )! ( )!*(n − − 1)! 2 2 2 2 n+x n+x (n − 1)!*( ) − (n − 1)!*(n − ) 2 2 n+x n+ x ( )!*(n − )! 2 2 (n − 1)!*x n+ x n+x ( )!*(n − )! 2 2 (n − 1)!*x x n * * n+ x n+x n x ( )!*(n − )! 2 2 x * Nn,x n - n! Nn,x = ( n+x n+ x )!*(n − )! 2 2 Wir bezeichnen mit Pa,b die Wahrscheinlichkeit dafür, dass der Kandidat A die ganze Zeit vor dem Kandidaten B lag. x * N n, x N n+, x x a−b n Pa,b = = = = n a+b N n,x N n, x Eigenschaften von Pa,b: Wenn a ein Vielfaches k von b ist, dann hängt die Wahrscheinlichkeit nur noch von dem k −1 Verhältnis ab und nicht mehr von der Anzahl a und b der Stimmen, denn k +1 kb − b b(k − 1) k − 1 = = a=k*b => Pa,b = kb + b b(k + 1) k + 1 Peter und Paul -Problem Aufgabenstellung: Peter und Paul spielen. Peters Ziel ist es, ein Spiel vor Paul zu liegen, also ein Mal mehr zu gewinnen als Paul. p: Wahrscheinlichkeit, dass Peter gewinnt q: Wahrscheinlichkeit, dass Paul gewinnt Zusammenhang: p = 1 - q, da q + p immer 1 sein muss. 70 Wir betrachten den Fall, dass Paul doppelt so häufig gewinnt wie Peter, d.h. p = 1 und q = 3 2 . 3 fn: Wahrscheinlichkeit, dass Peter nach dem n-ten Spiel zum ersten Mal ein Spiel vor Paul liegt. h: Wahrscheinlichkeit, dass Peter überhaupt einmal ein Spiel vor Paul liegt h = f1 + f2 + f3 + ... 1 1 , weil p = w0 = 1 3 3 f2 = 0, weil Peter und Paul entweder je ein Spiel gewonnen haben oder Paul beide Spiele gewonnen hat (Peter muss das erste Spiel verloren haben, ansonsten sind wir schon fertig). Analog gilt: fn = 0 für alle geraden n. f1 = f3 = 2 1 1 * * , weil Peter das erste Spiel verloren und die nächsten beiden gewonnen haben 3 3 3 muss, um eins in Führung zu liegen. w1 = 1 3 2 1  2 f5 = 2*   *   , weil Peter zunächst verlieren muss, das zweite und dritte Spiel jeweils 3  3 einmal gewinnen und verlieren muss und er die letzten beiden Spiele gewinnen muss. Der Koeffizient 2 kommt durch die doppelte Anzahl der Möglichkeiten. w2 = 2 Allgemein gilt für die Wahrscheinlichkeit, dass Peter nach 2k+1 Spielen zum ersten Mal vor Paul liegt: 1 f2k+1 = wk *   3 k +1 2 *  3 k wk ist die Anzahl der möglichen Wege, die zum Ziel führen. Der Exponent von größer sein als der Exponent von 1 muss um 1 3 2 , da Peter ein Spiel mehr gewinnen als verlieren muss. 3 Daraus folgt für h: h = w0 * p + w1 * p² * q + w2 * p³ * q² + … Jetzt versuchen wir h auf eine andere Weise zu ermitteln. Peter soll nun zwei Spiele vor Paul liegen. 1,5 1 x 0,5 p h 0 -0,5 q h -1 -1,5 n 71 Aus dem Diagramm ist ersichtlich: h = p + q*h² h p 0 = h² - + q q 1 ± 1 − 4qp 2q Umformung des Terms unter der Wurzel: 1 - 4pq = 1 - 4q * (1 - q) = 1 - 4q + 4q² = (1 - 2q)² 1 + 1 − 2q 1 − 1 − 2q h1 = und h2 = 2q 2q 1 1 p und für h2 = 1. Eine Fallunterscheidung nach q < und q > liefert für h1 = 2 2 q p Für p > q ist >1, was unmöglich ist, da eine Wahrscheinlichkeit nicht größer als 1 sein q kann. Also ist h = 1. p Für p = q folgt = 1, d.h. h = 1. q 1 1 1 1 + a) Für p < q muss p < sein. Sei a = - p, dann ist p * q = p * (1 - p) = ( - a) * (1 2 2 2 2 1 1 1 1 = ( - a) * ( + a) = - a² < . 2 2 4 4 Dann gilt: 1 p< 2 mit p-q-Formel: h1,2 = p²q = p(pq) < 1 1 1 * =  2 4 2 3 2 5 3 7 1 1 1 p³q² = p(pq)² < *   =   2 4 2 1 1 1 p q³ = p(pq)³ < *   =   2 4 2 Wir sehen, dass jeder Term der linken Reihe für h kleiner ist als der Term der rechten Reihe für 1. p folgt. Daraus folgt: h < 1, woraus wiederum h = q Die Wahrscheinlichkeit, dass Peter jemals zwei Spiele vor Paul liegt, beträgt h². Analog gilt für die Wahrscheinlichkeit, dass Peter jemals mit k Spielen vor Paul liegt hk. Für hk gilt:  1 wenn p ≥ q  k h =   p k    wenn p < q  q  4 Wir wollen nun die Anzahl der Wege wk bestimmen. Diese verlaufen von A(1/-1) nach B(2n/0) ohne die n-Achse zu schneiden. Um diese Wege zu zählen, müssen wir das Spiegelungsprinzip anwenden und die n-Achse um eins nach oben verschieben. Alle Wege, die diese neue Achse vor B berühren oder schneiden, bedeuten, dass Peter sein Ziel bereits erreicht hat. 72 4 3 2 1 x 0 -1 -2 -3 -4 A’ B A n Aus der Grafik ist ersichtlich, dass p – q = 1 und p + q = 2n – 1 sowie p´- q´= -3 und p´+ q´= 2n-1 Daraus folgt: p = n p´= n-2 Um die Anzahl aller Wege von A nach B zu finden, die die neue n-Achse weder berühren noch schneiden, müssen wir von der Gesamtanzahl aller Wege von A nach B diejenigen Wege abziehen, die die neue n-Achse berühren oder schneiden. Das sind nach dem Spiegelungsprinzip alle die, die von A´(1/3) nach B verlaufen. Demnach ist N- = wk = Nges – NA´ N- = wk  n   n´  =   -    p   p´  2n − 1  2n − 1  -   =   n − 2  n (2n − 1)! (2n − 1)! = n!(2n − 1 − n)! (n − 2)!(2n − 1 − n + 2)! (2n − 1)! (2n − 1)! (2n − 1)!(n + 1 − n + 1) = = n!(n − 1)! (n − 2)!(n + 1)! (n + 1)!(n − 1)! 2(2n − 1)! 1 2n(2n − 1)! = * = (n + 1)!(n − 1)! n + 1 n!n! 1 2n! 1  2n  * = *  = n + 1 n!n! n + 1  n  Für Wahrscheinlichkeit h ergibt sich dann: ∞  2n  1 *   * pn+1 * qn h =∑ n =0 n + 1  n  73