Продолжение Чернова

13

Я ищу ссылку (не доказательство того, что я могу сделать) на следующее расширение Черноффа.

Пусть $X_1,..,X_n$ - булевы случайные величины, не обязательно независимые . Вместо этого гарантируется, что $Pr(X_i=1|C)<p$ для каждого $i$ и каждого события $C$ которое зависит только от $\{X_j|j\neq i\}$ .

$\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$

Заранее спасибо!

reference-request pr.probability chernoff-bound любопытный
источник

26

Вам нужна обобщенная граница , которая предполагает только для любого подмножества S переменных индексов. Последнее следует из вашего предположения, поскольку для , Импальяццо и Кабанец недавно дали альтернативное доказательство оценки Чернова, в том числе обобщенное. В их статье вы можете найти все соответствующие ссылки на предыдущие работы: http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ $S=\{i_1,\ldots,i_{|S|}\}$

P (\underset{i \in S}{⋀} X_{i}) = P (X_{i_{1}} = 1) P (X_{i_{2}} = 1 | X_{i_{1}} = 1) \dots P (X_{i_{| S |}} = 1 | X_{i_{1}}, . . ., X_{i_{| S | - 1}} = 1) \leq p^{| S |}

$P(\bigwedge_{i\in S} X_{i}) = P(X_{i_1} = 1)P(X_{i_2}=1|X_{i_1}=1)\cdots P(X_{i_{|S|}}=1|X_{i_1},...,X_{i_{|S|-1}}=1)\leq p^{|S|}$

Дана Мошковиц
источник

Благодарю за разъяснение! На самом деле их состояние подразумевается как тем, что я имею, так и отрицательными корреляциями. Так что это действительно качественно сильнее (я как-то упустил тот момент, когда услышал разговор Валентина). Теперь доказательство того, что мне нужно, становится настолько коротким, что я с радостью отмечаю свой вопрос как ответивший, большое спасибо !!

любопытно

3

В вашем случае вы можете просто создать субмартингал из ваших переменных и использовать классическое неравенство Азумы с тем же эффектом. Чтобы это работало, вам нужно только, чтобы что подразумевается вашим предположением.

P r [X_{i} = 1 | X_{1}, \dots, X_{i - 1}] < p

$Pr[X_i=1|X_1, \ldots, X_{i-1}] < p$

MCH

7

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

Поскольку ваше обобщение не трудно доказать, возможно, никто не потрудился написать его.

Лев Рейзин
источник

Вы правы, это было также ближе всего, что я нашел (в "Концентрация ... для анализа ... алгоритмов"). Дело в том, что моя рукопись становится слишком длинной, и я хотел бы избежать еще одного побочного эффекта, если это возможно. Если нет, у меня не будет выбора ...

любопытно

3

это то, для чего нужны Приложения :)

Лев Рейзин

2

Эй, ребята, это было доказано ранее, и я дал ссылку в своем ответе (где вы также можете найти все другие соответствующие ссылки).

Дана Мошковиц

Ой - круто. Я как-то не заметил твой ответ!

Лев Рейзин

3

Альтернативной ссылкой может быть Лемма 1.19 в Б. Доерре, Анализ эвристики рандомизированного поиска: Инструменты из теории вероятностей, Теория эвристики рандомизированного поиска (А. Ожер и Б. Доерр, ред.), World Scientific Publishing, 2011, стр. 1- 20.

Проще говоря, это показывает, что когда с вероятностью независимо от того, на каких условиях вы ставите , тогда удовлетворяют всем границам Черноффа-Хоффдинга, которые действительны для независимых двоичные случайные величины с вероятностью успеха соответственно. Доказательство является элементарным, а результат - естественным, так что, я думаю, никто не чувствовал необходимости писать его. $X_i=1$ $p_i$ $X_1, \dots, X_{i-1}$ $X_1, \ldots, X_n$ $Y_1, \ldots, Y_n$ $p_1, \ldots, p_n$

Бенджамин Доерр
источник

Продолжение Чернова

Ответы: