Вероятность/Задачи/estimate-probability — различия между версиями

Версия 15:49, 20 мая 2020

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

@@ Строка 1: / Строка 1: @@
 Имеется приближенный <m>1 \pm \epsilon </m> алгоритм, который выдает верное значение с вероятностью <m>3/4</m>. Покажите, что можно уменьшить вероятность ошибки с <m>1/4</m> до любой желаемой <m>\delta</m>, выполнив некоторое число <m>\kappa</m> экспериментов и взяв среднее значение. Оценить сверху <m>\kappa</m> как функцию от <m>\delta</m>.
-==Стенина Мария, группа 974==
+[[Категория:Решенные задачи]]
-[[Категория:На проверку]]
-Обозначим <m>A_i</m> --- результат, который вернул алгоритм на i-том запуске. Будем считать эти результаты независимыми одинаково распределенными случайными величинами с дисперсией <m>\sigma^2</m> (будет странно, если запуски будут связаны между собой, или если алгоритм от запуска к запуску возвращает случайные величины из разных распределений). Обозначим <m>x</m> --- правильное решение задачи, <m>\alpha = \epsilon x</m>. Вероятность ошибки по условию --- это вероятность отклонения ответа алгоритма от правильного больше чем на <m>\alpha</m>
-;<m>P(|A_i - x| > \alpha) = \frac{1}{4}</m>.
-Будем считать, что математическое ожидание ответов совпадает с правильным решением <m>x</m>, иначе добавим ответам поправку на смещение. Согласно неравенству Чебышева
-;<m>P(|A_i - x| > \alpha) \leq \frac{\sigma^2}{\alpha^2}</m>.
-Дисперсия случайной величины, равной среднему арифметическому <m>\kappa</m> ответов алгоритма равна
-;<m>D \bar{A} = D \frac{1}{\kappa} \sum_{i=1}^k A_i = \frac{\sigma^2}{\kappa}</m>.
-Неравенство Чебышева для этой величины
-;<m>P(|\bar{A} - x| > \alpha) \leq \frac{\sigma^2}{\kappa\alpha^2}</m>
-Поэтому, если хотим уменьшить вероятность ошибки с уровня 0.25 до уровня <m>\delta</m>, нужно удовлетворить
-;<m>\frac{\sigma^2}{\kappa\alpha^2} \leq \delta</m>.
-Имеем неравенство
-;<m>\frac{1}{4} \leq \frac{\sigma^2}{\alpha^2} \leq \kappa \delta</m>,
-откуда получаем оценку
-;<m>\kappa \geq \frac{1}{4\delta}</m>.

Вероятность/Задачи/estimate-probability — различия между версиями

Версия 15:49, 20 мая 2020

Навигация

Просмотры

Персональные инструменты

Навигация

Поиск

Инструменты