Вероятность/Задачи/estimate-probability

Ссылки сюда (2) →

Подстраницы (8) →

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

Стенина Мария, группа 974

Обозначим --- результат, который вернул алгоритм на i-том запуске. Будем считать эти результаты независимыми одинаково распределенными случайными величинами с дисперсией (будет странно, если запуски будут связаны между собой, или если алгоритм от запуска к запуску возвращает случайные величины из разных распределений). Обозначим --- правильное решение задачи, . Вероятность ошибки по условию --- это вероятность отклонения ответа алгоритма от правильного больше чем на

.

Будем считать, что математическое ожидание ответов совпадает с правильным решением , иначе добавим ответам поправку на смещение. Согласно неравенству Чебышева

.

Дисперсия случайной величины, равной среднему арифметическому ответов алгоритма равна

.

Неравенство Чебышева для этой величины

Поэтому, если хотим уменьшить вероятность ошибки с уровня 0.25 до уровня , нужно удовлетворить

.

Имеем неравенство

,

откуда получаем оценку

.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.