Jakie jest najlepsze przybliżenie dla większości głosów?

Większość operacji głosowania pojawia się dość często w tolerancji na uszkodzenia (i bez wątpienia w innych miejscach), gdzie funkcja generuje bit równy, która zawsze pojawia się najczęściej w wartości bitów wejściowych. Dla uproszczenia załóżmy, że ilekroć wejście zawiera taką samą liczbę bitów w stanie 0 i stanie 1, wyprowadza 0.

Można to uogólnić na dits, dla których istnieją więcej niż 2 możliwości dla każdego wejścia, zwracając wartość, która występuje najczęściej na wejściu, aw przypadku remisu, zwracając najczęstszą wartość, która pojawia się najpierw leksykograficznie. Nazwijmy tę funkcję „głosowaniem pluralnym”.

Interesuje mnie wyjście takiej funkcji, gdy każde wejście ma ustalony rozkład prawdopodobieństwa (a rozkład jest taki sam dla każdego wejścia na wejściu). Szczególnie zależy mi na następującym pytaniu.

Dla danego zbioru , jeżeli ustalone jest niezależnie losowo razy, z prawdopodobieństwem doboru element każdorazowo przez ustalony wyboru , co jest prawdopodobieństwo, że głos wiele z tych wyjść ? $S=\{S_1, S_2,... ,S_n\}$ $N$ $p_i$ $i^{th}$ $S$ $v$ $S_v$

Teraz łatwo jest obliczyć dokładną odpowiedź na powyższe pytanie jako sumę rozkładów wielomianowych. Jednak dla moich celów jest to mniej niż idealne, a zamknięcie dla przybliżenia byłoby lepsze. Więc moje pytanie brzmi:

Jakie przybliżone przybliżenie do powyższego prawdopodobieństwa ma największy związek z maksymalną odległością od dokładnej wartości?

co.combinatorics Joe Fitzsimons
źródło

Nie wiem, ale sugerowałbym szukaną frazę „konsensus teorii sterowania” lub „problem konsensusu teorii sterowania”. Jest to problem inny niż problem konsensusu w zakresie przetwarzania rozproszonego i może być tym, czego potrzebujesz.

Aaron Sterling

Czy szukasz przybliżenia, które działa dobrze, gdy N jest duże w porównaniu do n? Jeśli tak, zasada rozstrzygania remisów musi być nieistotna.

Tsuyoshi Ito,

@TsuyoshiIto: Tak, i rzeczywiście ta zasada jest nieistotna, ale chciałem się upewnić, że pytanie jest dobrze postawione. Naprawdę nie dbam o to, jak zerwane są więzi, ponieważ łatwo jest powiązać tę rozbieżność.

Joe Fitzsimons,

Cóż, tutaj jest z tyłu szacunków koperty ... Niech

jest kilka razy wybrać zestaw

. Jest to zmienna dwumianowa. Udawaj, że są niezależni. Teraz, dla stałej wartości

, możesz obliczyć prawdopodobieństwo uzyskania tej wartości

, a dla tej wartości obliczyć prawdopodobieństwo, że wygra ona dla wszystkich innych zmiennych. To powinno dać całkiem dobre granice prawdopodobieństwa. Oczywiście nie są one najściślejsze - im większa zależność, którą chcesz wziąć pod uwagę, tym dokładniejsze będzie twoje oszacowanie, ale im więcej będziesz musiał wykonać obliczeń.

Y_{i}

$Y_i$

S_{i}

$S_i$

Y_{v}

$Y_v$

Y_{v}

$Y_v$

Sariel Har-Peled

Jeśli dla wszystkich , to $p_v > p_i$ $i \ne v$

P. r [wynik jest inny niż v] \leq min_{T.} (P. r [b (N., p_{v}) \leq T.] + P. r [\forall ja \neq v b (N., p_{ja}) \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),$

gdzie jest rozkładem dwumianowym, a jest arbitralnym progiem. Podłączanie $B(n, p)$ $T$ i używając granic Chernoffa, można przekroczyć to prawdopodobieństwo jako . $T = N (p_v + \max_{i \ne v} p_v) / 2$ $e^{-\Omega(N)}$

Oczywiście, jeśli nie jest maksymalne, otrzymasz odwrotny obraz. Z ogromnym prawdopodobieństwem nie jest wynikiem. $p_v$ $v$

ilyaraz
źródło

Dzięki za przemyślenie problemu, ale nie tego szukam. To nie jest zamknięta forma. Musiałbym zsumować ponad nieograniczoną liczbę wykładniczych. Wiem już, jak napisać dokładne rozwiązanie i znam wiele przybliżeń dla poszczególnych terminów, ale nie tego chcę. Szukam zbliżonego formularza do rozwiązania, a nie do poszczególnych warunków. Potrzebuję też przyzwoitego ograniczenia błędu.

Joe Fitzsimons,

Możesz uzyskać zamknięty formularz przy użyciu tej samej metody (jeśli jesteś zadowolony z dodatkowego czynnika

). Aby ograniczyć błąd, możesz użyć twierdzenia Berry'ego-Eseena zamiast ograniczenia Chernoffa.

n

$n$

ilyaraz

@ilyaraz Próbuję zrozumieć twoje pierwsze zejście. Czy możesz mi wyjaśnić, dlaczego tak się dzieje? Myślę, że w jakiś sposób wykorzystaliście związki, ale nie rozumiem. Dzięki :)

AntonioFa

Jakie jest najlepsze przybliżenie dla większości głosów?

Odpowiedzi: