Вероятность/Задачи/estimate-probability/Решение Дербышев — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 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>\kappa</m> экспериментов, описанных в условии. Оценим разницу между точным и верным ответом <m> a </m> и мат.ожиданием от среднего по экспериментам <m>e_i</m>
  
−
<m>E|a-{\sum_{i=0}^\kappa{e_i} \over \kappa}| = {\sum_{i=0}^\kappa{E|a-e_i|} \over \kappa}</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|a-e_i|</m>. С вероятностью <m>3/4</m> <m>|e_i-a| < \epsilon</m>. При условии ограниченности матожиднания также с вероятностью <m>1</m> <m>|e_i-a| < \epsilon </m>. Из этого следует что <m>E|e_i-a| = {\epsilon \over 4}</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>
 
<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

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





Предположим, что мы провели экспериментов, описанных в условии. Оценим разницу между точным и верным ответом и мат.ожиданием от среднего по экспериментам

Подсчитаем . С вероятностью . Также с вероятностью . Из этого следует что . Тогда:

Источник — «https://discopal.ispras.ru/index.php?title=Вероятность/Задачи/estimate-probability/Решение_Дербышев&oldid=4913»