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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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>.
 
Имеется приближенный <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==
+
[[Category:Решенные задачи]]
−
[[Категория:На проверку]]
+
−
 
+
−
Обозначим <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>.
+

Версия 12:04, 24 декабря 2014

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

Источник — «https://discopal.ispras.ru/index.php?title=Вероятность/Задачи/estimate-probability&oldid=3322»