Вероятность/Задачи/eupce-1-11-a — различия между версиями
Материал из DISCOPAL
| Строка 7: | Строка 7: | ||
Докажите, что вероятность получения корректного бита: | Докажите, что вероятность получения корректного бита: | ||
<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>. Ч.т.д. | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Версия 02:26, 25 декабря 2023
Задача зарезервирована: OMShitikov 00:20, 25 декабря 2023 (UTC)
Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо может инвертировать бит с вероятностью «p».
Докажите, что вероятность получения корректного бита:
- Корректный бит мы получим тогда и только тогда, когда количество инвертирований чётно.
- Для инвертирований количество вариантов инвертирований на узлах равно количеству сочетаний из по , т.е. , и вероятность каждого подобного варианта равна (в силу известных количеств инвертированных и неинвертированных узлов)
- Возможные неотрицательные целые значения , т.ч. - от до .
- Значит, суммарная вероятность всех таких случаев равна . Ч.т.д.