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

Версия 02:28, 25 декабря 2023

Задача зарезервирована: OMShitikov 00:20, 25 декабря 2023 (UTC)

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

Докажите, что вероятность получения корректного бита:

@@ Строка 7: / Строка 7: @@
 Докажите, что вероятность получения корректного бита:
      <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>. Ч.т.д.
 [[Категория:Теоретические задачи]]