Znalezienie stronniczej monety za pomocą kilku rzutów monetą

Podczas badań pojawił się następujący problem, który jest zaskakująco czysty:

Masz źródło monet. Każda moneta ma stronniczość, a mianowicie prawdopodobieństwo upadku na „głowę”. Dla każdej monety niezależnie istnieje prawdopodobieństwo 2/3, że ma ona stronniczość co najmniej 0,9, a przy pozostałym prawdopodobieństwie jej stronniczość może wynosić dowolną liczbę w [0,1]. Nie znasz stronniczości monet. Na każdym kroku możesz jedynie rzucić monetą i obserwować wynik.

Dla danego n Twoim zadaniem jest znalezienie monety o nastawieniu co najmniej 0,8 z prawdopodobieństwem co najmniej . Czy możesz to zrobić, używając tylko rzutów monetą O (n)? $1-\exp(-n)$

ds.algorithms pr.probability Dana Moshkovitz
źródło

Wydaje mi się bardzo mało prawdopodobne, ponieważ

O (n)

$O(n)$ wydają się być wymagane tylko w celu ustalenia, czy dana moneta ma wysokie nastawienie, czy nie z ufnością

1 - \exp (- n)

$1-\exp(-n)$ . (Równie dobrze możemy założyć, że każda moneta ma nastawienie

0.9

$0.9$ lub

0.8 - ϵ

$0.8-\epsilon$ .) Czy masz coś lepszego niż

O (n^{2})

$O(n^2)$ ?

usul

Nie sprawdziłem matematyki, ale następujący pomysł wygląda obiecująco: Dla każdej monety (kolejno) wykonaj następujący test. Wybierz parametr

p

$p$ , powiedzmy

0.85

$0.85$ i wykonaj losowy spacer po linii za pomocą monety. Na każdym kroku

i

$i$ , jeśli odchylenie od

0

$0$ jest mniejsze niż

p \cdot i

$p \cdot i$ , odrzuć monetę. Monety z odchyleniem .9 powinny przejść ten test ze stałym prawdopodobieństwem, a monety zepsute powinny zawieść po oczekiwanych krokach O (1), z wyjątkiem monet z odchyleniem bardzo zbliżonym do

p

$p$ . Picking

p

$p$ losowo pomiędzy

.84

$.84$ i

.86

$.86$ dla każdej monety może rozwiązać ten problem.

daniello

Czy

byłoby w porządku? Czy znasz rozwiązanie z

O (n \log n)

$O(n\log n)$

o (n^{2})

$o(n^2)$

Robin Kothari

Uwaga 1: Jeśli wiesz, że wszystkie monety mają nastawienie co najmniej 0,9 lub co najwyżej 0,8, byłoby możliwe znalezienie monety o nastawieniu co najmniej 0,9 z prawdopodobieństwem 1-exp (-n) przy użyciu rzutów O (n) : weź monetę, dla i = 1,2,3, ..., rzuć monetą 2 ^ i razy i sprawdź, czy ułamek głów wynosi co najmniej 0,89. Jeśli nie, uruchom ponownie z nową monetą. Kluczowy lemat: jeśli restart w fazie i, to miał rzuty monetą mniej niż 2 ^ {i + 1}, a prob jest co najwyżej exp (- \ Omega (i)).

Dana Moshkovitz

Całkiem możliwe, że przerzucanie O (nlogn) jest konieczne i wystarczające - ale nie mamy na to jeszcze dowodu.

Dana Moshkovitz

Odpowiedzi:

Poniżej przedstawiono dość prosty algorytm podrzucania $O(n \log n)$ .

Załóżmy, że $1-\exp(-n)$ to prawdopodobieństwo błędu, do którego dążymy. Niech $N$ będzie potęgą $2$ która wynosi między powiedzmy $100n$ a $200n$ (tylko wystarczająco duże stałe czasy $n$ ). Utrzymujemy kandydującego zestawu monet $C$ . Początkowo umieścić $N$ monet $C$ .

Teraz dla $i=1,\dots,\log N$ , wykonaj następujące czynności:
Rzuć każdą monetą w $C$ dla $D_i = 2^i 10^{10}$ razy (tylko wystarczająco duża stała).
Trzymaj monety $N/2^i$ z większością głów.

Dowód opiera się na kilku granicach Chernoffa. Główną ideą jest to, że za każdym razem zmniejszamy o połowę liczbę kandydatów, dzięki czemu możemy sobie pozwolić na dwa razy więcej rzutów każdej monety.

Kasper Green Larsen
źródło

(1) Byłoby miło opisać dowód bardziej szczegółowo - duża trudność w tym problemie polega na tym, gdzie umieścić próg dla granicy Chernoffa (ile głów oczekujesz od monet o wartości 0,9?) . (2) Czy możesz wykazać, że rzuty monetą nlogn są konieczne?

Dana Moshkovitz

Subtelność jest taka: zaczynasz od n monet, z wyjątkiem prob exp small in n, jest co najmniej 0,6 n monet o nastawieniu 0,9. Teraz istnieje stały problem, że monety o wartości 0,9 stronniczości tracą konkurencję w stosunku do: 1 monety o nastawieniu mniejszym niż 0,8 (może się zdarzyć, że cały czas spada na głowę!), 2 monet o nastawieniu 0,8 + 1 / logn ... 10 monet z nastawieniem 0,9 - 1 / log n. Kontynuuj w podobny sposób, gdy stronniczość wybranych monet zmniejsza się z każdą iteracją, dopóki nie zostaniesz z monetą stronniczości <0,8.

Dana Moshkovitz

Jest to mniej więcej algorytm eliminacji mediany według Evan-Dar i in. glin. Jak pokazali Mannor i Tsitsiklis w Próbce złożoności eksploracji w problemie wielorękiego bandyty , można go użyć do uzyskania oczekiwanych rzutów monetą

gdy znane jest docelowe odchylenie.

O (n)

$O(n)$

Kristoffer Arnsfelt Hansen

Dzięki za referencje! Interesuje mnie maksymalna liczba rzutów monetą, których potrzebujesz, i w tym przypadku pokazują one dolną granicę n ^ 2. Problem, który uważają, jest jednak inny niż mój. Mają n monet, może być tylko jedna, która jest najbardziej tendencyjna i chcą znaleźć monetę o podobnym nastawieniu. W moim ustawieniu wiem, że jest co najmniej 0,6n monet z akceptowalnym nastawieniem (z wyjątkiem prob wykładniczo małej in).

Dana Moshkovitz

Wydaje mi się, że oczekiwane rzuty

są łatwe dla naszego problemu: zacznij od pierwszej monety i wykonaj

rzuty dla jakiejś dużej stałej w adnotacji

. Jeśli wyjdzie głowica co najmniej

razy, zwróć ją. W przeciwnym razie przejdź do następnej monety. Prawdopodobieństwo prawidłowość jest

i monety wejściowych będących 0,9 Odchylenie niezależnie z prawdopodobieństwem

, prawdopodobieństwo osiągnięcia

O (n)

$O(n)$

m = Θ (n)

$m=\Theta(n)$

Θ (\cdot)

$\Theta(\cdot)$

0.85 m

$0.85m$

1 - \exp (- n)

$1-\exp(-n)$

2 / 3

$2/3$

i

$i$ -tym moneta jest mniejszy niż

, a zatem oczekuje się ilość rzutów jest

(1 / 2)^{i}

$(1/2)^i$

\sum_{i = 0}^{\infty} m / 2^{i} = O (m) = O (n)

$\sum_{i=0}^\infty m/2^i = O(m) = O(n)$

Kasper Green Larsen