Finden einer voreingenommenen Münze mit ein paar Münzwürfen

Das folgende Problem trat während der Recherche auf und es ist überraschend sauber:

Sie haben eine Münzquelle. Jede Münze hat eine Tendenz, nämlich eine Wahrscheinlichkeit, dass sie auf den "Kopf" fällt. Für jede Münze gibt es eine Wahrscheinlichkeit von 2/3, dass sie einen Bias von mindestens 0,9 hat, und mit der restlichen Wahrscheinlichkeit kann ihr Bias eine beliebige Zahl in [0,1] sein. Sie kennen die Vorurteile der Münzen nicht. Alles, was Sie in einem Schritt tun können, ist eine Münze zu werfen und das Ergebnis zu beobachten.

Für ein gegebenes n besteht Ihre Aufgabe darin, eine Münze mit einem Bias von mindestens 0,8 und einer Wahrscheinlichkeit von mindestens . Können Sie das nur mit O (n) Münzwürfen machen? $1-\exp(-n)$

ds.algorithms pr.probability Dana Moshkovitz
quelle

Scheint mir sehr unwahrscheinlich, da -Würfe erforderlich zu sein scheinen, um zu bestimmen, ob eine bestimmte Münze eine hohe Tendenz aufweist oder nicht, und zwar mit Zuversicht . (Wir können auch davon ausgehen, dass jede Münze entweder eine Vorspannung von oder .) Haben Sie etwas Besseres als -Würfe?

O (n)

$O(n)$

1 - \exp (- n)

$1-\exp(-n)$

0.9

$0.9$

0.8 - ϵ

$0.8-\epsilon$

O (n^{2})

$O(n^2)$

USUL

Ich habe die Mathematik nicht überprüft, aber die folgende Idee sieht vielversprechend aus: Führen Sie für jede Münze (nacheinander) den folgenden Test durch. Wählen Sie einen Parameter , sagen wir und führen Sie mit der Münze einen zufälligen Lauf auf der Linie durch. Bei jedem Schritt wird die Münze weggeworfen , wenn die Abweichung von geringer als ist. Münzen mit einer Vorspannung von 0,9 sollten diesen Test mit konstanter Wahrscheinlichkeit bestehen, und fehlerhafte Münzen sollten nach O (1) Schritten der Erwartung versagen, mit Ausnahme der Münzen mit einer Vorspannung, die sehr nahe an . Picking zufällig zwischen und für jede Münze könnte dieses Problem beheben.

p

$p$

0.85

$0.85$

i

$i$

0

$0$

p \cdot i

$p \cdot i$

p

$p$

p

$p$

.84

$.84$

.86

$.86$

daniello

Wäre in Ordnung? Kennen Sie eine Lösung mit -Würfen?

O (n \log n)

$O(n\log n)$

o (n^{2})

$o(n^2)$

Robin Kothari

Beobachtung Nr. 1: Wenn Sie gewusst hätten, dass alle Münzen einen Bias von mindestens 0,9 oder höchstens 0,8 haben, wäre es möglich gewesen, eine Münze mit einem Bias von mindestens 0,9 mit einer Wahrscheinlichkeit von 1-exp (-n) unter Verwendung von O (n) -Würfen zu finden : nimm eine Münze, für i = 1,2,3, ... wirf die Münze 2 ^ i-mal und überprüfe, ob der Bruchteil der Köpfe mindestens 0,89 beträgt. Wenn nicht, starten Sie mit einer neuen Münze neu. Das Schlüssel-Lemma: Wenn der Neustart in Phase i durchgeführt wird, werden weniger als 2 ^ {i + 1} geworfen, und der Prob ist höchstens exp (- \ Omega (i)).

Dana Moshkovitz

Es ist gut möglich, dass O (nlogn) -Flips notwendig und ausreichend sind - aber wir haben noch keinen Beweis dafür.

Dana Moshkovitz

Antworten:

Das Folgende ist ein ziemlich direkter $O(n \log n)$ -Toss-Algorithmus.

Angenommen, $1-\exp(-n)$ ist die angestrebte Fehlerwahrscheinlichkeit. Sei $N$ eine Potenz von $2$ , die zwischen etwa $100n$ und $200n$ (gerade einige ausreichend große konstante Zeiten $n$ ). Wir pflegen einen Kandidatensatz von Münzen, $C$ . Zunächst setzen wir $N$ Münzen in $C$ .

Jetzt für $i=1,\dots,\log N$ , gehen Sie wie folgt vor :
Toss jede Münze in $C$ für $D_i = 2^i 10^{10}$ mal (nur einige groß genug , um konstant).
Behalte die $N/2^i$ Münzen mit den meisten Köpfen.

Der Beweis basiert auf ein paar Chernoff-Schranken. Die Hauptidee ist, dass wir jedes Mal die Hälfte der Anzahl der Kandidaten haben und uns so doppelt so viele Würfe von jeder Münze leisten können.

Kasper Green Larsen
quelle

(1) Es wäre schön, den Beweis detaillierter aufzuschreiben - ein Großteil der Schwierigkeit bei diesem Problem besteht darin, wo die Schwelle für die Chernoff-Grenze zu platzieren ist (wie viele Köpfe erwarten Sie von den 0,9-Bias-Münzen?) . (2) Können Sie zeigen, dass ein Münzwurf mit nlogn notwendig ist?

Dana Moshkovitz

Die Subtilität ist folgende: Sie beginnen mit n Münzen, und mit Ausnahme von prob exp small in n gibt es mindestens 0,6n Münzen mit einem Bias von 0,9. Jetzt ist die Wahrscheinlichkeit konstant, dass die 0,9-Bias-Münzen die Konkurrenz verlieren: 1 Münze mit einem Bias von weniger als 0,8 (kann die ganze Zeit auf den Kopf fallen!), 2 Münzen mit einem Bias von 0,8 + 1 / logn, ..., n / 10 Münzen mit einer Vorspannung von 0,9 - 1 / log n. Fahren Sie auf ähnliche Weise fort, wobei sich die Vorspannung der ausgewählten Münzen mit jeder Iteration verringert, bis die Vorspannungsmünze <0,8 übrig bleibt.

Dana Moshkovitz

Dies ist mehr oder weniger der Median Elimination-Algorithmus von Evan-Dar et. al. Wie von Mannor und Tsitsiklis in " Die Komplexität der Erkundungsbeispiele für das mehrarmige Banditenproblem" gezeigt , kann es verwendet werden, um erwartete

-Münzwürfe zu erhalten, wenn die Zielvorspannung wie in diesem Fall bekannt ist.

O (n)

$O(n)$

Kristoffer Arnsfelt Hansen

Danke für den Hinweis! Ich interessiere mich für die maximale Anzahl von Münzwürfen, die benötigt werden, und für diesen Fall zeigen sie eine Untergrenze von n ^ 2. Das Problem, das sie in Betracht ziehen, unterscheidet sich jedoch von meinem. Sie haben n Münzen, es könnte nur eine geben, die am meisten verzerrt ist, und sie möchten eine Münze mit einer ähnlichen Verzerrung finden. In meinem Setup weiß ich, dass es mindestens 0,6n Münzen mit akzeptabler Verzerrung gibt (außer bei wahrscheinlich exponentiell kleinen in n).

Dana Moshkovitz

Ich vermute, dass

-Würfe für unser Problem einfach sind: Beginnen Sie mit der ersten Münze und tun Sie

-Würfe für eine große Konstante in der

-Notation. Wenn das mindestens

mal herauskommt , geben Sie es zurück. Ansonsten weiter zur nächsten Münze. Die Richtigkeit Wahrscheinlichkeit ist

, und durch die Eingangs Münzen 0,9 Bias unabhängig mit Wahrscheinlichkeit ist

, die Wahrscheinlichkeit für das Erreichen

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$ -te Münze kleiner als

und damit die erwartete Anzahl von Würfen ist

(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