Какое наилучшее приближение для большинства голосов?

Операция с большинством голосов встречается довольно часто в отказоустойчивом (и, без сомнения, в других местах), где функция выводит бит, равный тому, какое значение всегда появляется в значении входных битов. Для простоты предположим, что всякий раз, когда вход содержит одинаковое количество битов в состоянии 0 и состоянии 1, он выводит 0.

Это может быть обобщено на точки, где имеется более 2 возможностей для каждого входа, возвращая значение, которое чаще всего встречается на входе, а в случае привязки - наиболее частое значение, которое появляется первым лексикографически. Давайте назовем эту функцию «множественным голосованием».

Я заинтересован в выводе такой функции, когда каждый вход имеет фиксированное распределение вероятностей (и распределение одинаково для каждого входа на входе). Конкретно меня волнует следующий вопрос.

Принимая во внимание множество , если множество независимо случайная выборка раза, с вероятностью выбор элемента каждый раз при фиксированном выборе какова вероятность того, что множество голоса из этих выходов ? $S=\{S_1, S_2,... ,S_n\}$ $N$ $p_i$ $i^{th}$ $S$ $v$ $S_v$

Теперь прямо вычислить точный ответ на поставленный выше вопрос как сумму по полиномиальным распределениям. Тем не менее, для моих целей, это не идеально, и закрытое для приближения было бы лучше. Итак, мой вопрос:

Какое приближение замкнутой формы к указанной вероятности имеет самую тесную границу на максимальном расстоянии от точного значения?

co.combinatorics Джо Фитцсимонс
источник

Я не знаю, но я бы предложил поисковую фразу «консенсус теории управления» или «проблема консенсуса теории управления». Это проблема, отличная от консенсусной задачи распределенных вычислений, и может быть то, что вам нужно.

Аарон Стерлинг

Вы ищете приближение, которое хорошо работает, когда N больше по сравнению с n? Если это так, правило разрыва связи не должно иметь значения.

Цуеши Ито

@TsuyoshiIto: Да, и действительно, это правило не имеет значения, но я хотел убедиться, что вопрос поставлен правильно. Меня не волнует, как нарушаются связи, так как эту несдержанность легко связать.

Джо Фитцзимонс

Ну, вот обратная сторона оценки огибающей ... Пусть

будет количеством раз, когда вы выбираете множество

. Это биноминальная переменная. Притворись, что они независимы. Теперь, для фиксированного значения

, вы можете вычислить вероятность получения этого значения

, и для этого значения вычислите вероятность того, что оно выиграет над всеми другими переменными. Это должно дать довольно хорошие границы вероятности. Они, конечно, не самые строгие - чем больше зависимости вы готовы принять во внимание, тем более точной будет ваша оценка, но чем больше вычислений вам придется делать.

Y_{i}

$Y_i$

S_{i}

$S_i$

Y_{v}

$Y_v$

Y_{v}

$Y_v$

Сариэль Хар-Пелед

Если для всех , то $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),$

где - биномиальное распределение, а - произвольный порог. Подставляя и используя границы Чернова, можно оценить верхнюю вероятность как . $B(n, p)$ $T$ $T = N (p_v + \max_{i \ne v} p_v) / 2$ $e^{-\Omega(N)}$

Конечно, если $p_v$ не является максимальным, то вы получите противоположную картину. С подавляющей вероятностью не является результатом. $v$

ilyaraz
источник

Спасибо, что подумали о проблеме, но это не то, что я ищу. Это не закрытая форма. Мне нужно было бы суммировать по неограниченному числу экспонент. Я уже знаю, как написать точное решение, и я знаю много приближений для отдельных терминов, но это не то, что я хочу. Я ищу приближенную форму решения, а не отдельные термины. Мне также нужна достойная оценка ошибки.

Джо Фитцзимонс

Вы можете получить закрытую форму, используя тот же метод (если вас устраивает дополнительный фактор

). И чтобы ограничить ошибку, вы можете использовать теорему Берри-Эзина вместо границы Черноффа.

n

$n$

Ильяраз

@ilyaraz Я пытаюсь понять твое первое нарушение. Можете ли вы объяснить мне лучше, почему это так? Я думаю, что вы каким-то образом использовали объединение, но я не могу понять. Спасибо :)

AntonioFa

Какое наилучшее приближение для большинства голосов?

Ответы: