Nieprzechodnie kostki i ruletki

W roku 1970 Martin Gardner opisał w dziale matematycznym czasopisma Scientific American kostki do gry odkryte kilka lat wcześniej przez statystyka Bradleya Efrona...

Kostki te (oznaczmy je $|A,$ oraz $D$ ) różnią się od zwykłej kostki tym, że na ich ściankach umieszczone są inne liczby oczek:

kostka $A$ - ma dwie ścianki puste, a na każdej z pozostałych czterech ścianek umieszczone są po 4 oczka;
kostka $|B$ - na każdej ściance znajdują się 3 oczka;
kostka $C$ - na czterech ściankach znajdują się po 2 oczka, a na dwóch po 6;
kostka $D$ - na trzech ściankach znajduje się po 1 oczku, a na pozostałych po 5.

Rzucając kostkami $A$ i $B |$ z prawdopodobieństwem $|23,$ uzyskamy więcej oczek na kostce $|A$ niż na $B. |$ Gdy rzucimy $B$ oraz $C,$ to z prawdopodobieństwem $|2 3$ uzyskamy więcej oczek na kostce $|B$ niż na $|C.$ W podobny sposób (za każdym razem z prawdopodobieństwem $2 |3$ ) kostka $C$ okazuje się lepsza od $, D |$ zaś $D$ lepsza od $A.$ Czyli wśród tych czterech kostek nie ma najlepszej! Ujmując to inaczej: dla każdej kostki z tego zestawu można znaleźć w tym zestawie kostkę lepszą. Przy sortowaniu kostek od najgorszej do najlepszej powstaje cykl (patrz rysunek). Relacja między kostkami, polegająca na byciu lepszą, nie jest przechodnia! Ta nieprzechodniość fascynowała nie tylko matematyków, ale również socjologów i ekonomistów (którzy powiązali ją z teorią wyboru i z modelami użyteczności losowej).

Rozważmy dwuosobową grę: pierwszy gracz wybiera jedną z kostek $|A,$ drugi wybiera jedną z pozostałych, a następnie obaj rzucają wybranymi kostkami. Wygrywa ten, kto uzyska więcej oczek. Okazuje się, że w tej grze lepiej być drugim graczem, bo wybierając odpowiednio kostkę, wygrywa się z prawdopodobieństwem $|2. 3$

Gra $n$ "kostkami"

Załóżmy, że mamy jakiś inny skończony zbiór przyrządów do losowania liczb (niekoniecznie sześciennych kostek), który dawałby w analogicznej grze dużą szansę wygrania drugiemu graczowi. Jak duża może być ta szansa? Niech $1 X$ będzie dowolnym przyrządem z tego zbioru, zaś $2,X3,...X$ określamy w ten sposób, że $k X$ jest tym przyrządem, który wybrałby gracz drugi, gdyby gracz pierwszy wybrał przyrząd $k−1. X$ Ponieważ przyrządów jest skończenie wiele, to w którymś momencie muszą zacząć się powtarzać, powstanie cykl. Możemy usunąć ze zbioru wszystkie przyrządy spoza tego cyklu - to może co najwyżej zwiększyć szansę drugiego gracza. Oznaczmy przez $1,X2,...,Xn} {X$ zbiór takich tworzących cykl przyrządów. Niech odpowiedzią gracza drugiego na $X k−1$ będzie $X k$ (dla $k = 1,...,n$ ). Przyjmijmy $0=Xn. |X$ Prawdopodobieństwo tego, że przy optymalnej grze obu graczy drugi wygra, wynosi $k−1<Xk). |min1DkDnP(X$

Wykażemy, że dla $n$ przyrządów, tworzących cykl, prawdopodobieństwo to może przyjąć wartość co najwyżej

π = 1− ----1----. n 4 cos2 18n0+X2

Dla zbioru $n$ przyrządów prawdopodobieństwo to jest co najwyżej takie, jak dla pewnego cyklu zawartego w tym zbiorze, a więc nie przekracza $| πn.$ Z drugiej strony, gdy wszystkie elementy zbioru należą do cyklu długości $|n,$ to może ono być równe $π n.$

Trójkąty $AEC |$ i $BCD |$ są podobne, a stąd wynika, że
$AE BC AC --- --- --- AC BD BD$
(ostatnia równość wynika z równoramienności $Q ABC$ ), czyli $BAC2. AE |$

Geometryczne narzędzia

Powtórzmy teraz wielokrotnie wcześniejszą obserwację.

Niech $n | ⩾ 2$ i $180X α = n+2.$ Wówczas $|?BCA$ Jeśli punkty $0=A,D1,D2,...,Dn=BD$ wybierzemy na boku $AB$ w taki sposób, że $kCDk−1=α?D$ dla $k = 1,...,n,$ to zachodzi $k⋅Dk−1B=AC2. |AD$

Jesteśmy gotowi, by skonstruować $n |$ przyrządów losujących, pozwalających graczowi drugiemu wygrać z prawdopodobieństwem $πn.$

Konstrukcja ruletek

Nawińmy odcinek $|AB$ (czyli najdłuższy bok trójkąta) na koło o środku $|O$ i promieniu $AB2 |-π$ tak, by stał się on obwodem koła. Punkty $0 A$ oraz $nB = D$ ulegną sklejeniu, tworząc jeden punkt, który wraz z punktami $| 1,D2,...,Dn−1D$ dzieli obwód na $| n$ części. Punkty te, oczywiście, nie są równomiernie rozmieszczone na obwodzie, tak samo jak nie były na boku trójkąta. Przyrząd $k X$ (gdzie $k = 0,1,...,n$ ) to ruletka, którą otrzymujemy, dzieląc koło promieniami $OA$ oraz $k OD |$ na dwa sektory, w które wpisujemy liczby $k$ oraz $|n+ k$ w sposób pokazany na rysunku.

Z lewej szablon do zbudowania $n$ przyrządów, z prawej przyrząd $k. X$

Ruletka działa w naturalny sposób - można, na przykład, zamocować w środku wskazówkę i wprawić ją w ruch, każda jej wynikowa pozycja jest tak samo prawdopodobna, a wynikiem losowania będzie liczba wpisana w pole, na którym się ona zatrzyma. Prawdopodobieństwo uzyskania wyniku $|k$ na przyrządzie $k X$ wynosi $k AD- |AB$ (stosunek długości łuków), zaś prawdopodobieństwo uzyskania wyniku $n | +k$ wynosi $B D k |AB.$ Ruletki $0X$ oraz $n X$ są identyczne - zwracają jedynie wynik $n.$ Dla przykładu, dla $|n = 6$ uzyskujemy następujące ruletki:

Aby obliczyć prawdopodobieństwo tego, z jakim $k−1 X$ jest mniejsze od $,X k$ zauważmy, że $X k−1$ może przyjąć tylko wartości $|k− 1$ lub $|k− 1+ n,$ zaś $k X$ tylko wartości $|k$ lub $|k+ n.$ Zatem $k−1 X$ jest mniejsze od $k X$ zawsze z wyjątkiem sytuacji, gdy $k=k X$ oraz $k−1=k−1+n. X$ Wynika stąd, że dla $k = 1,...,n$

$pict$

Na kolejnym rysunku zilustrowane są obliczenia dla $n = 6$ oraz przyrządów $| 4X$ i $| 5. X$ Odcinek $| AB$ nawijamy na ruletkę $| 4 X$ (trójkąt z lewej) i $| 5 X$ (trójkąt nad kwadratem) w pokazany sposób. Zaznaczamy odpowiednie sektory. Prawdopodobieństwo $4⩾X5)=1−P(X4<X5) |P(X$ jest równe stosunkowi pól zacieniowanego prostokąta i kwadratu $AA$ Ponieważ trójkąty $| ACDk$ i $′ |′ k−1 B C$ są podobne, to stosunek ten dla dowolnych ruletek $k−1,Xk |X$ i dowolnego $|n ⩾2$ wynosi

k⋅D′k−1B′ AD AC 1 ------------ = ---------= -----2-. AB AB 4 cos α

Wszystkie prostokąty $′k−1HkkD AD$ mają takie samo pole równe $AC2.$ Punkty $|H$ leżą na jednej hiperboli. Wykazaliśmy, jak zbudować $|n$ przyrządów realizujących szansę $π n$ na wygraną drugiego gracza.

Dlaczego nie można uzyskać więcej niż $|ß ? n$

Załóżmy, że $Y1,...,Yn$ są takimi niezależnymi zmiennymi losowymi, że $|P(Y < Y ) > π k−1 k n$ dla wszystkich $k = 1,...,n$ (gdzie $Y = Y 0 n$ ). Okazuje się (dowód tego faktu nie jest łatwy), że modyfikując odpowiednio nasze zmienne losowe, można założyć, że $|Yn$ jest stała (tak, jak w przypadku kostki $|B$ w zestawie Efrona oraz ruletki $n X$ ). Określmy liczby $|y ,y,...,y 0 1 n$ następująco: niech $y k$ będzie takie, że $k P (Y ⩽ y ) ⩾ AD- k k AB$ oraz $kkB AD- D-- |P(Yk ⩾yk) ⩾ 1− AB= AB$ (taka liczba $yk |$ to kwantyl rzędu $k AD- |AB$ rozkładu zmiennej losowej $Yk$ ). Ponieważ $|Y0 = Yn$ jest stała, więc można liczby $|y0$ oraz $|yn$ określić tak, by $y0 = yn.$ Niech $yj$ będzie najmniejszą spośród liczb $y ,...,y . 1 n$ Wówczas $y ⩾ y . j −1 j$ Wynika stąd, że jeśli $|Y j⩽ y j$ oraz $|Y j−1⩾yj −1,$ to $Yj −1⩾ Y j.$ Zatem

$pict$

Otrzymaliśmy sprzeczność. Oznacza to, że takie zmienne losowe nie istnieją.

Ponieważ ciąg $(π ) n$ jest rosnący i zbieżny do $3, 4$ więc prawdopodobieństwo zwycięstwa drugiego gracza jest zawsze mniejsze niż $3 4.$

Zauważmy, że $π = 1− ---1---= 2, 4 4cos230X 3$ czyli kostki Efrona stanowią optymalny przykład dla $n = 4.$ W ciągu $πn,$ oprócz $π4,$ tylko $1 π 2 = 2$ jest liczbą wymierną (wtedy gra nie ma większego sensu, ale takie kostki bez problemu można wskazać). Pozostałe wartości są niewymierne, więc nie można ich zrealizować za pomocą kostek (nawet takich, które mają inną niż $6$ liczbę ścian). Na przykład $---1--- -5−1 1 π3 = 1− 4cos236X = 2 = ϕ =ϕ − 1$ jest stosunkiem długości krótszej do dłuższej części w złotym podziale odcinka ( $ϕ$ to złota proporcja), $π 6 = -1, 2$ $|π8 = -ϕ-, 5$ zaś $√ -- π 10 = 3 − 1.$ Jeszcze inne szczególne wartości $πn$ to $----1---- π2n−2 = 1− 2+ 2+⋅⋅⋅+ --2$ dla $n ⩾ 2$ (mamy tu $n − 1$ dwójek oraz $|n− 2$ pierwiastki) oraz $|π3⋅2n− 2 = 1 − ---1-- -- 2+ 2+⋅⋅⋅+ 3$ (tym razem $n ⩾ 1$ i mamy $|n− 1$ dwójek, jedną trójkę oraz $n −1$ pierwiastków).