Вероятность/Задачи/estimate-probability — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 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== |
| + | [[Категория:На проверку]] | ||
| + | |||
| + | Обозначим <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>. | ||
Версия 11:42, 10 октября 2014
Имеется приближенный алгоритм, который выдает верное значение с вероятностью . Покажите, что можно уменьшить вероятность ошибки с до любой желаемой , выполнив некоторое число экспериментов и взяв среднее значение. Оценить сверху как функцию от .
Стенина Мария, группа 974
Обозначим --- результат, который вернул алгоритм на i-том запуске. Будем считать эти результаты независимыми одинаково распределенными случайными величинами с дисперсией (будет странно, если запуски будут связаны между собой, или если алгоритм от запуска к запуску возвращает случайные величины из разных распределений). Обозначим --- правильное решение задачи, . Вероятность ошибки по условию --- это вероятность отклонения ответа алгоритма от правильного больше чем на
- .
Будем считать, что математическое ожидание ответов совпадает с правильным решением , иначе добавим ответам поправку на смещение. Согласно неравенству Чебышева
- .
Дисперсия случайной величины, равной среднему арифметическому ответов алгоритма равна
- .
Неравенство Чебышева для этой величины
Поэтому, если хотим уменьшить вероятность ошибки с уровня 0.25 до уровня , нужно удовлетворить
- .
Имеем неравенство
- ,
откуда получаем оценку
- .