Was ist der beste Näherungswert für die Mehrheitswahl?

Die Mehrheitsabstimmungsoperation tritt relativ häufig in Bezug auf Fehlertoleranz (und zweifellos an anderen Stellen) auf, wo die Funktion ein Bit ausgibt, das dem Wert entspricht, der im Wert der Eingabebits am häufigsten vorkommt. Nehmen wir der Einfachheit halber an, dass der Eingang immer dann, wenn er die gleiche Anzahl von Bits in Zustand 0 und Zustand 1 enthält, 0 ausgibt.

Dies kann auf Punkte verallgemeinert werden, bei denen es mehr als zwei Möglichkeiten für jede Eingabe gibt, indem der Wert zurückgegeben wird, der am häufigsten in der Eingabe vorkommt, und im Falle eines Gleichstands der häufigste Wert, der zuerst lexikographisch kommt. Nennen wir diese Funktion "plural vote".

Ich interessiere mich für die Ausgabe einer solchen Funktion, wenn jeder Eingang eine feste Wahrscheinlichkeitsverteilung hat (und die Verteilung für jeden Punkt im Eingang gleich ist). Konkret geht es mir um folgende Frage.

Gegeben ist eine Menge , wenn die Menge mal unabhängig zufällig abgetastet wird, mit der Wahrscheinlichkeit , das -Element von jedes Mal für eine feste Wahl zu wählen von wie ist die Wahrscheinlichkeit, dass die Mehrzahl dieser Ausgänge ? $S=\{S_1, S_2,... ,S_n\}$ $N$ $p_i$ $i^{th}$ $S$ $v$ $S_v$

Nun ist es einfach, die exakte Antwort auf die obige Frage als Summe über Multinomialverteilungen zu berechnen. Für meine Zwecke ist dies jedoch weniger als ideal, und eine Annäherung wäre besser. Meine Frage lautet also:

Welche Annäherung in geschlossener Form an die obige Wahrscheinlichkeit hat die engste Grenze für den maximalen Abstand vom exakten Wert?

co.combinatorics Joe Fitzsimons
quelle

Ich weiß es nicht, aber ich würde den Suchbegriff "Kontrolltheoretischer Konsens" oder "Kontrolltheoretisches Konsensproblem" vorschlagen. Dies ist ein anderes Problem als das Konsensproblem bei verteilten Computern und möglicherweise das, was Sie benötigen.

Aaron Sterling

Suchen Sie eine Näherung, die gut funktioniert, wenn N im Vergleich zu n groß ist? In diesem Fall muss die Abbruchregel irrelevant sein.

Tsuyoshi Ito

@ TsuyoshiIto: Ja, das bin ich, und diese Regel ist in der Tat irrelevant, aber ich wollte sicherstellen, dass die Frage gut gestellt war. Es ist mir eigentlich egal, wie die Krawatten gebrochen sind, da es leicht ist, diese Diskrepanz zu binden.

Joe Fitzsimons

Nun, hier ist die Rückseite der Hüllkurvenschätzung ... Sei

die Häufigkeit, mit der Sie die Menge

auswählen . Dies ist eine Binomialvariable. Tu so, als wären sie unabhängig. Nun können Sie für einen festen Wert von

die Wahrscheinlichkeit berechnen, diesen Wert von

, und für diesen Wert die Wahrscheinlichkeit, mit der alle anderen Variablen gewonnen werden. Dies sollte die Wahrscheinlichkeit ziemlich gut einschränken. Sie sind natürlich nicht die engsten - je mehr Abhängigkeit Sie berücksichtigen möchten, desto genauer wird Ihre Schätzung sein, aber desto mehr Berechnungen müssen Sie durchführen.

Y_{i}

$Y_i$

S_{i}

$S_i$

Y_{v}

$Y_v$

Y_{v}

$Y_v$

Sariel Har-Peled

Wenn für alles , dann $p_v > p_i$ $i \ne v$

P r [Ergebnis ist anders als v] \leq \underset{T}{Mindest} (P r [B (N, p_{v}) \leq T] + P r [\forall ich \neq v B (N, p_{ich}) \geq T]),

$\mathrm{Pr}[\mbox{outcome is different from $v$}] \leq \min_T \left(Pr[B(N, p_v) \leq T] + Pr[\forall i \ne v \quad B(N, p_i) \geq T]\right),$

wobei eine Binomialverteilung ist und eine beliebige Schwelle ist. Aufstecken und unter Verwendung von Chernoff Grenzen kann eine obere gebundene diese Wahrscheinlichkeit als . $B(n, p)$ $T$ $T = N (p_v + \max_{i \ne v} p_v) / 2$ $e^{-\Omega(N)}$

Wenn nicht maximal ist, erhalten Sie natürlich das entgegengesetzte Bild. Mit überwältigender Wahrscheinlichkeit ist kein Ergebnis. $p_v$ $v$

Ilyaraz
quelle

Vielen Dank, dass Sie über das Problem nachgedacht haben, aber das ist nicht das, wonach ich suche. Es ist keine geschlossene Form. Ich müsste über eine unbegrenzte Anzahl von Exponentialen summieren. Ich weiß bereits, wie man die exakte Lösung schreibt, und ich kenne viele Näherungswerte für einzelne Begriffe, aber das ist nicht das, was ich will. Ich suche eine geschlossene Annäherung an die Lösung, nicht an einzelne Begriffe. Ich brauche auch eine anständige Grenze für den Fehler.

Joe Fitzsimons

Sie können das Formular mit der gleichen Methode schließen (wenn Sie mit dem zusätzlichen Faktor

zufrieden sind ). Und um den Fehler einzugrenzen, können Sie den Satz von Berry-Eseen anstelle des Satzes von Chernoff verwenden.

n

$n$

Ilyaraz

@ilyaraz Ich versuche deine erste Ungleichung zu verstehen. Kannst du mir besser erklären, warum es gilt? Ich denke, Sie haben in irgendeiner Weise gewerkschaftlich gebunden, aber ich kann es nicht verstehen. Danke :)

AntonioFa

Was ist der beste Näherungswert für die Mehrheitswahl?

Antworten: