Какова вероятность, что будет выполнено более половины скобок?
Какова вероятность, что будет выполнено более половины скобок?
−
[[Категория:На проверку]]
+
[[Category:Решенные задачи]]
−
+
−
===Стенина Мария, группа 974===
+
−
+
−
<latex>
+
−
Оценим вероятность, что после $t$ выборов выполнено не более половины скобок. Это значит, что каждый выбранный набор переменных обеспечивает выполнение не более $\frac{m}{2}$ скобок.
+
−
Обозначим количество итераций $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i \leq \frac{m}{2})$, где $z_i$ --- значение $i$-той скобки (0 или 1).
+
−
Теперь оценим $\alpha$. Пусть $i$-тая скобка содержит $k_i$ литералов. Чтобы значение скобки было равно нулю, необходимо, чтобы значения всех литералов были равны нулю. Вероятность такого события $2^{-k_i}$. Следовательно, вероятность $\mathbb{P}(z_i = 0) \leq \frac{1}{2}$. Если предположить, что все $z_i$ независимые случайные величины, то $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i \leq \frac{m}{2}) \leq \frac{1}{2}$. Если же $z_i$ зависимы, то из неравенства $\mathbb{P}(A, B) \leq \mathbb{P}(A) + \mathbb{P}(B)$ получаем ту же оценку на $\alpha$. Отсюда имеем оценку вероятности выполнения не более половины скобок не больше $2^{-t}$. Поэтому искомая вероятность не меньше, чем $1 - 2^{-t}$.
+
−
</latex>
+
Версия 10:10, 24 декабря 2014
Рассмотрим следующий алгоритм для задачи MAX-SAT.
t раз, случайно (равномерное распределение) выбираем набор — значения переменных
выбираем лучший результат
Какова вероятность, что будет выполнено более половины скобок?