Zastanawiałem się kiedyś, jak można przy pomocy jednej monety dokonać losowania wśród \(\displaystyle{ n}\) osób. Wymyśliłem następującą metodę: rozgrywamy "turniej" przy pomocy monety, to znaczy każdy zawodnik wykonuje z każdym rzut monetą i ktoś zawsze wygrywa, ktoś przegrywa. Jeśli po zakończeniu turnieju znajdzie się zawodnik, który wygrał ze wszystkimi pozostałymi, to wygrywa losowanie. Jeśli nie ma takiego zawodnika, to powtarzamy zabawę.
Jest raczej jasne, że nikt nie jest tutaj faworyzowany, ale można oczywiście ściśle pokazać, że prawdopodobieństwo wygranej ustalonego gracza wynosi \(\displaystyle{ \frac1n}\). Pamiętam, że zacząłem rozmyślać, jak można by zmniejszyć liczbę pojedynków do tych koniecznych, i wtedy przyszedł mi do głowy jakiś pomysł, który uznałem za krótszy i bardziej elegancki. Jestem prawie pewien, że nie wymagał wykonywania potencjalnie dowolnie wielu rzutów. Chyba kazałem im rzucać razem w jakichś seriach, tak że po wykonaniu iluś rzutów ktoś bezspornie zwyciężał.
No i teraz za nic w świecie nie mogę sobie przypomnieć tego mojego sprytnego pomysłu… Może ktoś coś fajnego wymyśli?
Losowanie wśród n osób przy użyciu jednej monety
-
Dasio11
- Moderator
- Posty: 10222
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Losowanie wśród n osób przy użyciu jednej monety
Jeśli \(\displaystyle{ n}\) nie jest potęgą dwójki, to nie istnieje algorytm losowania wśród \(\displaystyle{ n}\) osób za pomocą rzutów (symetryczną) monetą, taki że:
- każdy krok algorytmu - włącznie z podaniem wyniku - zależy wyłącznie od wyników rzutów monetą,
- prawdopodobieństwo wylosowania każdej osoby wynosi \(\displaystyle{ \frac{1}{n}}\),
- istnieje takie \(\displaystyle{ m \in \NN}\), że w żadnym przypadku algorytm nie każe wykonać więcej niż \(\displaystyle{ m}\) rzutów monetą.
Dowód: przypuśćmy nie wprost, że taki algorytm istnieje. Niech \(\displaystyle{ \Omega}\) będzie zbiorem wszystkich takich ciągów binarnych \(\displaystyle{ x = (x_0, \ldots, x_{k-1})}\) długości \(\displaystyle{ k \le m}\), że istnieje przebieg algorytmu, w którym wykonanych zostaje \(\displaystyle{ k}\) rzutów monetą i ciąg \(\displaystyle{ x}\) opisuje wyniki tych rzutów. W takim przypadku niech \(\displaystyle{ w(x) \in \{ 1, \ldots, n \}}\) oznacza wynik zwrócony przez algorytm (który z założenia zależy tylko od \(\displaystyle{ x}\)). W ten sposób określiliśmy funkcję \(\displaystyle{ w : \Omega \to \{ 1, \ldots, n \}}\).
Łatwo zauważyć, że dla \(\displaystyle{ 1 \le j \le n}\) prawdopodobieństwo wylosowania \(\displaystyle{ j}\)-tej osoby wynosi
\(\displaystyle{ p_j = \sum_{\substack{x \in \Omega \\ w(x) = j}} \frac{1}{2^{|x|}}}\),
gdzie \(\displaystyle{ |x|}\) oznacza długość ciągu \(\displaystyle{ x}\). Sprowadzając do wspólnego mianownika, dostajemy
\(\displaystyle{ p_j = \frac{t}{2^k}}\)
dla pewnego \(\displaystyle{ k \le m}\) i nieparzystego \(\displaystyle{ t \in \NN}\). Z założenia jednak \(\displaystyle{ p_j = \frac{1}{n}}\), a wobec tego \(\displaystyle{ nt = 2^k}\). Stąd łatwo dostajemy \(\displaystyle{ t = 1}\) i \(\displaystyle{ n = 2^k}\), wbrew założeniu.
W skrócie: \(\displaystyle{ m}\) rzutów symetryczną monetą może podzielić przestrzeń probabilistyczną na kawałki, których prawdopodobieństwa są całkowitymi wielokrotnościami \(\displaystyle{ \frac{1}{2^m}}\). Nie jest więc możliwe, aby taki kawałek miał prawdopodobieństwo \(\displaystyle{ \frac{1}{n}}\), chyba że \(\displaystyle{ n}\) jest potęgą dwójki.
- każdy krok algorytmu - włącznie z podaniem wyniku - zależy wyłącznie od wyników rzutów monetą,
- prawdopodobieństwo wylosowania każdej osoby wynosi \(\displaystyle{ \frac{1}{n}}\),
- istnieje takie \(\displaystyle{ m \in \NN}\), że w żadnym przypadku algorytm nie każe wykonać więcej niż \(\displaystyle{ m}\) rzutów monetą.
Dowód: przypuśćmy nie wprost, że taki algorytm istnieje. Niech \(\displaystyle{ \Omega}\) będzie zbiorem wszystkich takich ciągów binarnych \(\displaystyle{ x = (x_0, \ldots, x_{k-1})}\) długości \(\displaystyle{ k \le m}\), że istnieje przebieg algorytmu, w którym wykonanych zostaje \(\displaystyle{ k}\) rzutów monetą i ciąg \(\displaystyle{ x}\) opisuje wyniki tych rzutów. W takim przypadku niech \(\displaystyle{ w(x) \in \{ 1, \ldots, n \}}\) oznacza wynik zwrócony przez algorytm (który z założenia zależy tylko od \(\displaystyle{ x}\)). W ten sposób określiliśmy funkcję \(\displaystyle{ w : \Omega \to \{ 1, \ldots, n \}}\).
Łatwo zauważyć, że dla \(\displaystyle{ 1 \le j \le n}\) prawdopodobieństwo wylosowania \(\displaystyle{ j}\)-tej osoby wynosi
\(\displaystyle{ p_j = \sum_{\substack{x \in \Omega \\ w(x) = j}} \frac{1}{2^{|x|}}}\),
gdzie \(\displaystyle{ |x|}\) oznacza długość ciągu \(\displaystyle{ x}\). Sprowadzając do wspólnego mianownika, dostajemy
\(\displaystyle{ p_j = \frac{t}{2^k}}\)
dla pewnego \(\displaystyle{ k \le m}\) i nieparzystego \(\displaystyle{ t \in \NN}\). Z założenia jednak \(\displaystyle{ p_j = \frac{1}{n}}\), a wobec tego \(\displaystyle{ nt = 2^k}\). Stąd łatwo dostajemy \(\displaystyle{ t = 1}\) i \(\displaystyle{ n = 2^k}\), wbrew założeniu.
W skrócie: \(\displaystyle{ m}\) rzutów symetryczną monetą może podzielić przestrzeń probabilistyczną na kawałki, których prawdopodobieństwa są całkowitymi wielokrotnościami \(\displaystyle{ \frac{1}{2^m}}\). Nie jest więc możliwe, aby taki kawałek miał prawdopodobieństwo \(\displaystyle{ \frac{1}{n}}\), chyba że \(\displaystyle{ n}\) jest potęgą dwójki.
-
Majeskas
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Losowanie wśród n osób przy użyciu jednej monety
Tam jest usterka techniczna (może czegoś nie widzę). Ułamek \(\displaystyle{ \frac t{2^k}}\) nie musi mieć nieparzystego licznika, ale można go zawsze skrócić tak, żeby miał nieparzysty licznik, a w mianowniku nadal potęgę dwójki.
Było dla mnie jasne, że jeśli po prostu odbędzie się ileś rzutów, to mamy tę potęgę dwójki w mianowniku i zazwyczaj nie uzyskamy \(\displaystyle{ \frac1n}\), ale jakoś wydawało mi się, że jeśli w różnych sytuacjach rzucimy różną liczbę razy, to może się uda. Wielkie dzięki za demaskację!
Zatem mój niegdysiejszy pomysł nie eliminował problemu długich serii rzutów. Chyba po prostu był taki, żeby już po jednej serii było wiadomo, czy się udało, czy gramy dalej — bez turniejów. Najprostsze, co mi teraz przyszło do głowy, to żeby wszyscy rzucili raz i żeby zwyciężył ten, kto jako jedyny będzie miał orła lub jako jedyny reszkę. Czy o to mi kiedyś chodziło? Wątpię, zważywszy, że szansa na szybkie rozstrzygnięcie choćby przy pięciu osobach jest znikoma…
Jakby ktoś wpadł na pomysł, jak przy serii rzutów wymyślić zdarzenie tego typu jak wyżej, które łatwo wyróżni jedną osobę spośród reszty i będzie miało trochę lepszą szansę niż \(\displaystyle{ \frac1{2^{n-1}}}\), to ekstra!-- 16 lipca 2019, 03:04 --Przemyślałem trochę sprawę (i przeliczyłem). Podzielę się wnioskami (może komuś się to kiedyś przyda).
Jak już wiemy dzięki Dasiowi11, w wypadku, gdy \(\displaystyle{ n}\) nie jest potęgą dwójki, potrzebujemy eksperymentu losowego, przy którym pewne zdarzenia elementarne będą oznaczały powtórkę rzutów. Wystarczy wskazać dowolną rodzinę \(\displaystyle{ n}\) zdarzeń rozłącznych jednakowo prawdopodobnych, które nie wypełnią \(\displaystyle{ \Omega}\). Każde takie zdarzenie będzie kodować wygraną ustalonej osoby, zaś zdarzenie przeciwne do ich sumy będzie oznaczało powtórkę.
Wówczas prawdopodobieństwo wygranej dowolnego gracza jest równe \(\displaystyle{ \tfrac1n}\). Jeśli teraz oznaczymy przez \(\displaystyle{ p}\) prawdopodobieństwo rozstrzygnięcia konkursu w jednej próbie (pewnej serii rzutów), to takich prób potrzeba będzie średnio \(\displaystyle{ \tfrac1p}\) (co wymaga pewnych rachunków albo odwołania się do wiadomości o rozkładzie geometrycznym).
Przy metodzie turnieju średnia liczba rzutów potrzebnych do rozstrzygnięcia nie przekracza \(\displaystyle{ (n-1)\cdot2^{n-2}}\) (często nie musimy przeprowadzać pełnego turnieju, żeby wiedzieć, czy będzie rozstrzygnięty, choć czasem jest to konieczne). Słabo.
W drugiej zaproponowanej przeze mnie metodzie wartość oczekiwana nie przekracza \(\displaystyle{ 2^{n-1}}\) (i tu zazwyczaj nie wszyscy muszą rzucić, żeby było wiadomo co i jak). Trochę lepiej.
Najlepsza metoda: Bierzemy najmniejszą taką liczbę \(\displaystyle{ k}\), że \(\displaystyle{ 2^k\ge n}\). Każdemu przypisujemy jeden ciąg orłów i reszek długości \(\displaystyle{ k}\). Rzucamy \(\displaystyle{ k}\) razy monetą. Jeśli \(\displaystyle{ n}\) jest potęgą dwójki, to każdy ciąg kogoś wyznacza i ten ktoś wygrywa. Jeśli nie jest, to pewne ciągi zostają puste i w takim wypadku powtarzamy rzuty. Wówczas średnio potrzebujemy najwyżej \(\displaystyle{ 2\log_2n+2}\) rzutów. Najlepiej!
Było dla mnie jasne, że jeśli po prostu odbędzie się ileś rzutów, to mamy tę potęgę dwójki w mianowniku i zazwyczaj nie uzyskamy \(\displaystyle{ \frac1n}\), ale jakoś wydawało mi się, że jeśli w różnych sytuacjach rzucimy różną liczbę razy, to może się uda. Wielkie dzięki za demaskację!
Zatem mój niegdysiejszy pomysł nie eliminował problemu długich serii rzutów. Chyba po prostu był taki, żeby już po jednej serii było wiadomo, czy się udało, czy gramy dalej — bez turniejów. Najprostsze, co mi teraz przyszło do głowy, to żeby wszyscy rzucili raz i żeby zwyciężył ten, kto jako jedyny będzie miał orła lub jako jedyny reszkę. Czy o to mi kiedyś chodziło? Wątpię, zważywszy, że szansa na szybkie rozstrzygnięcie choćby przy pięciu osobach jest znikoma…
Jakby ktoś wpadł na pomysł, jak przy serii rzutów wymyślić zdarzenie tego typu jak wyżej, które łatwo wyróżni jedną osobę spośród reszty i będzie miało trochę lepszą szansę niż \(\displaystyle{ \frac1{2^{n-1}}}\), to ekstra!-- 16 lipca 2019, 03:04 --Przemyślałem trochę sprawę (i przeliczyłem). Podzielę się wnioskami (może komuś się to kiedyś przyda).
Jak już wiemy dzięki Dasiowi11, w wypadku, gdy \(\displaystyle{ n}\) nie jest potęgą dwójki, potrzebujemy eksperymentu losowego, przy którym pewne zdarzenia elementarne będą oznaczały powtórkę rzutów. Wystarczy wskazać dowolną rodzinę \(\displaystyle{ n}\) zdarzeń rozłącznych jednakowo prawdopodobnych, które nie wypełnią \(\displaystyle{ \Omega}\). Każde takie zdarzenie będzie kodować wygraną ustalonej osoby, zaś zdarzenie przeciwne do ich sumy będzie oznaczało powtórkę.
Wówczas prawdopodobieństwo wygranej dowolnego gracza jest równe \(\displaystyle{ \tfrac1n}\). Jeśli teraz oznaczymy przez \(\displaystyle{ p}\) prawdopodobieństwo rozstrzygnięcia konkursu w jednej próbie (pewnej serii rzutów), to takich prób potrzeba będzie średnio \(\displaystyle{ \tfrac1p}\) (co wymaga pewnych rachunków albo odwołania się do wiadomości o rozkładzie geometrycznym).
Przy metodzie turnieju średnia liczba rzutów potrzebnych do rozstrzygnięcia nie przekracza \(\displaystyle{ (n-1)\cdot2^{n-2}}\) (często nie musimy przeprowadzać pełnego turnieju, żeby wiedzieć, czy będzie rozstrzygnięty, choć czasem jest to konieczne). Słabo.
W drugiej zaproponowanej przeze mnie metodzie wartość oczekiwana nie przekracza \(\displaystyle{ 2^{n-1}}\) (i tu zazwyczaj nie wszyscy muszą rzucić, żeby było wiadomo co i jak). Trochę lepiej.
Najlepsza metoda: Bierzemy najmniejszą taką liczbę \(\displaystyle{ k}\), że \(\displaystyle{ 2^k\ge n}\). Każdemu przypisujemy jeden ciąg orłów i reszek długości \(\displaystyle{ k}\). Rzucamy \(\displaystyle{ k}\) razy monetą. Jeśli \(\displaystyle{ n}\) jest potęgą dwójki, to każdy ciąg kogoś wyznacza i ten ktoś wygrywa. Jeśli nie jest, to pewne ciągi zostają puste i w takim wypadku powtarzamy rzuty. Wówczas średnio potrzebujemy najwyżej \(\displaystyle{ 2\log_2n+2}\) rzutów. Najlepiej!