Вероятность/Задачи/estimate-probability/Решение Дербышев — различия между версиями
Материал из DISCOPAL
Kirikus (обсуждение | вклад) (На проверку;) |
Kirikus (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | + | Не решено. | |
| + | |||
| + | Странно. Если верный ответ 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> | ||
Текущая версия на 12:59, 6 декабря 2016
Не решено.
Странно. Если верный ответ 1, то
алгоритм который с вероятностью 3/4 отвечает 1, а иначе отвечает 1+e
или
алгоритм который с вероятностью 3/4 отвечает 1+e, а иначе отвечает 1+100e
дают видимое противоречие с условием.
Предположим, что мы провели экспериментов, описанных в условии. Оценим разницу между точным и верным ответом и мат.ожиданием от среднего по экспериментам
Подсчитаем . С вероятностью . Также с вероятностью . Из этого следует что . Тогда: