Просмотр исходного текста страницы Вероятность/Задачи/estimate-probability/Решение Дербышев

Не решено.

Странно. Если верный ответ 1, то 

алгоритм который с вероятностью 3/4 отвечает 1, а иначе отвечает 1+e

или

алгоритм который с вероятностью 3/4 отвечает 1+e, а иначе отвечает 1+100e

дают видимое противоречие с условием. 









Предположим, что мы провели <m>\kappa</m> экспериментов, описанных в условии. Оценим разницу между точным и верным ответом <m> a </m> и мат.ожиданием от среднего по экспериментам <m>e_i</m>

<m>P\{|1-{\sum_{i=0}^\kappa{e_i} \over a\kappa}|\} = {\sum_{i=0}^\kappa{E|a-e_i|} \over a\kappa}</m>

Подсчитаем <m>E|{e_i-a \over a}|</m>. С вероятностью <m>3/4</m> <m>|{e_i-a \over a}| = 0</m>. Также с вероятностью <m>1</m> <m>|{e_i-a \over a}| < \epsilon </m>. Из этого следует что <m>E|{e_i-a \over a}| = {\epsilon \over 4}</m>. Тогда:

<m>E|a-{\sum_{i=0}^\kappa{e_i} \over \kappa}| < {\sum_{i=0}^\kappa{E|a-e_i|} \over \kappa}</m>