Вероятность/Задачи/eupce-1-11-a — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
−
{{проверено|}}
+
{{проверено|[[Участник:StasFomin|StasFomin]] 12:29, 26 декабря 2023 (UTC)}}
 
<!-- Probability and Computing -->
 
<!-- Probability and Computing -->
−
{{reserve-task|[[Участник:OMShitikov|OMShitikov]] 00:20, 25 декабря 2023 (UTC)}}
 
 
Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо  
 
Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо  
 
может инвертировать бит с вероятностью «p».
 
может инвертировать бит с вероятностью «p».
Строка 7: Строка 6:
 
Докажите, что вероятность получения корректного бита:
 
Докажите, что вероятность получения корректного бита:
 
     <m>\sum_{k=0}^{n/2} \binom{n}{2k} p^{2k}(1-p)^{n-2k}</m>
 
     <m>\sum_{k=0}^{n/2} \binom{n}{2k} p^{2k}(1-p)^{n-2k}</m>
−
----
 
−
* Корректный бит мы получим тогда и только тогда, когда количество инвертирований чётно.
 
−
* Для <m>2k</m> инвертирований количество вариантов инвертирований на узлах равно количеству сочетаний из <m>n</m> по <m>2k</m>, т.е. <m>\binom{n}{2k}</m>, и вероятность каждого подобного варианта равна <math>p^{2k}(1-p)^{n-2k}</math> (в силу известных количеств инвертированных <m>(2k)</m> и неинвертированных <m>(n-2k)</m> узлов)
 
−
* Возможные неотрицательные целые значения <m>k</m>, т.ч. <m>2k \leqslant n</m> - от <m>0</m> до <m>\lfloor n/2 \rfloor</m>.
 
−
* Значит, суммарная вероятность всех таких случаев равна <m>\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} p^{2k}(1-p)^{n-2k}</m>. Ч.т.д.
 
  
 
[[Категория:Теоретические задачи]]
 
[[Категория:Теоретические задачи]]

Текущая версия на 12:29, 26 декабря 2023

Проверено: StasFomin 12:29, 26 декабря 2023 (UTC)

Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо может инвертировать бит с вероятностью «p».

Докажите, что вероятность получения корректного бита:
Источник — «https://discopal.ispras.ru/index.php?title=Вероятность/Задачи/eupce-1-11-a&oldid=28063»