Имеется приближенный <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>, иначе добавим ответам поправку на смещение. Согласно неравенству Чебышева
Имеется приближенный алгоритм, который выдает верное значение с вероятностью . Покажите, что можно уменьшить вероятность ошибки с до любой желаемой , выполнив некоторое число экспериментов и взяв среднее значение. Оценить сверху как функцию от .