Quelle est la meilleure approximation pour un vote majoritaire?

L'opération de vote majoritaire se produit assez souvent en tolérance aux pannes (et sans doute dans d'autres endroits), où la fonction génère un bit égal à la valeur qui apparaît le plus fréquemment dans la valeur des bits d'entrée. Pour simplifier, supposons que chaque fois que l'entrée contient un nombre égal de bits dans l'état 0 et l'état 1, elle génère 0.

Cela peut être généralisé aux points où il y a plus de 2 possibilités pour chaque entrée en retournant la valeur qui se produit le plus fréquemment dans l'entrée, et dans le cas d'une égalité, en retournant la valeur la plus fréquente qui vient en premier lexicographiquement. Appelons cette fonction "vote pluraliste".

Je m'intéresse à la sortie d'une telle fonction lorsque chaque entrée a une distribution de probabilité fixe (et la distribution est la même pour chaque dit dans l'entrée). Plus précisément, je me soucie de la question suivante.

Etant donné un ensemble , si l'ensemble est échantillonné de façon indépendante fois, avec probabilité de choisir l' élément de chaque fois, pour un choix fixe de quelle est la probabilité que la pluralité de votes de ces sorties ? $S=\{S_1, S_2,... ,S_n\}$ $N$ $p_i$ $i^{th}$ $S$ $v$ $S_v$

Maintenant, il est simple de calculer la réponse exacte à la question ci-dessus comme une somme sur les distributions multinomiales. Cependant, pour mes besoins, ce n'est pas idéal, et une clôture pour approximation serait préférable. Ma question est donc:

Quelle approximation sous forme fermée à la probabilité ci-dessus a la limite la plus stricte sur la distance maximale de la valeur exacte?

co.combinatorics Joe Fitzsimons
la source

Je ne sais pas, mais je suggérerais l'expression de recherche «consensus de la théorie du contrôle» ou «problème du consensus de la théorie du contrôle». C'est un problème différent du problème du consensus de l'informatique distribuée, et c'est peut-être ce dont vous avez besoin.

Aaron Sterling

Cherchez-vous une approximation qui fonctionne bien lorsque N est grand par rapport à n? Si tel est le cas, la règle de départage doit être non pertinente.

Tsuyoshi Ito

@TsuyoshiIto: Oui, je le suis, et en effet cette règle n'est pas pertinente, mais je voulais m'assurer que la question était bien posée. Je ne me soucie pas vraiment de la façon dont les liens sont rompus, car il est facile de limiter cette divergence.

Joe Fitzsimons

Eh bien, voici le dos de l'estimation de l'enveloppe ... Soit

le nombre de fois que vous choisissez l'ensemble

. Il s'agit d'une variable binomiale. Imaginez qu'ils sont indépendants. Maintenant, pour une valeur fixe de

, vous pouvez calculer la probabilité d'obtenir cette valeur de

, et pour cette valeur calculer la probabilité qu'elle l'emporte sur toutes les autres variables. Cela devrait donner une assez bonne limite à la probabilité. Ils ne sont bien sûr pas les plus étroits - plus vous êtes prêt à prendre en compte la dépendance, plus votre estimation sera précise, mais plus vous devrez faire de calculs.

Y_{i}

$Y_i$

S_{i}

$S_i$

Y_{v}

$Y_v$

Y_{v}

$Y_v$

Sariel Har-Peled

Si pour tout , alors $p_v > p_i$ $i \ne v$

P r [outcome is different from v] \leq min_{T} (P r [B (N, p_{v}) \leq T] + P r [\forall i \neq v B (N, p_{i}) \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),$

où est la distribution binomiale et est un seuil arbitraire. En branchant et en utilisant les bornes de Chernoff, on peut limiter cette probabilité par . $B(n, p)$ $T$ $T = N (p_v + \max_{i \ne v} p_v) / 2$ $e^{-\Omega(N)}$

Bien sûr, si n'est pas maximum, alors vous obtenez l'image opposée. Avec une probabilité écrasante, n'est pas le résultat. $p_v$ $v$

ilyaraz
la source

Merci d'avoir pensé au problème, mais ce n'est pas ce que je recherche. Ce n'est pas un formulaire fermé. Il faudrait que je résume un nombre illimité d'exponentielles. Je sais déjà comment écrire la solution exacte et je connais beaucoup d'approximations pour les termes individuels, mais ce n'est pas ce que je veux. Je recherche une approximation sous forme fermée de la solution, pas des termes individuels. J'ai également besoin d'une limite décente sur l'erreur.

Joe Fitzsimons

Vous pouvez obtenir un formulaire fermé en utilisant la même méthode (si vous êtes satisfait du facteur

supplémentaire ). Et pour limiter l'erreur, vous pouvez utiliser le théorème de Berry-Eseen au lieu de lié à Chernoff.

n

$n$

ilyaraz

@ilyaraz J'essaye de comprendre ta première diséquation. Pouvez-vous mieux m'expliquer pourquoi cela tient? Je pense que vous avez utilisé l'union liée d'une manière ou d'une autre, mais je ne comprends pas. Merci :)

AntonioFa

Quelle est la meilleure approximation pour un vote majoritaire?

Réponses: