|
|
| Строка 3: |
Строка 3: |
| | Покажите, что после <tt>n</tt>-ходов, число существ типа A будет равновероятно распределено между <tt>1</tt> и <tt>n-1</tt>. | | Покажите, что после <tt>n</tt>-ходов, число существ типа A будет равновероятно распределено между <tt>1</tt> и <tt>n-1</tt>. |
| | | | |
| − | ==Стенина Мария, группа 974==
| + | [[Category:Решенные задачи]] |
| − | | + | |
| − | [[Категория:На проверку]] | + | |
| − | | + | |
| − | Вероятно, в условии опечатка, потому что число существ типа А будет равномерно распределено между <tt>1</tt> и <tt>n+1</tt>.
| + | |
| − | | + | |
| − | ====Решение====
| + | |
| − | | + | |
| − | Введем величину <m>P_i(N_A=k)</m> --- вероятность того, что после i ходов у нас имеется k существ типа А. Нужно показать, что
| + | |
| − | ;<m>P_i(N_A=k) = \frac{1}{i+1}</m>, то есть эта величина не зависит от k.
| + | |
| − | | + | |
| − | Сделаем это по индукции.
| + | |
| − | | + | |
| − | =====База индукции <m>n=1</m>.=====
| + | |
| − | Мы сделали только один шаг, с вероятностью 0.5 выбрали А. Поэтому имеем
| + | |
| − | ;<m>P_1(N_A=1) = P_1(N_A = 2) = \frac{1}{2} = \frac{1}{n+1}</m>.
| + | |
| − | | + | |
| − | =====Индукционный переход.=====
| + | |
| − | Пусть мы доказали, что <m>P_i(N_A=k) = \frac{1}{i+1}</m> не зависит от k. Покажем, что <m>P_{i+1}(N_A = k) = \frac{1}{i+2}</m>.
| + | |
| − | | + | |
| − | После i+1 шагов ситуация <m>N_A = k</m> возможна в двух случаях
| + | |
| − | | + | |
| − | 1) после i шагов было <m>N_A = k-1</m>, и мы выбрали А;
| + | |
| − | | + | |
| − | 2) после i шагов было <m>N_A = k</m>, и мы выбрали В.
| + | |
| − | | + | |
| − | Соответственно вероятность запишется
| + | |
| − | ;<m>P_{i+1}(N_A=k) = P_i(N_A=k-1)P_i(A) + P_i(N_A=k)P_i(B)</m>,
| + | |
| − | | + | |
| − | где <m>P_i(A)</m> --- вероятность на шаге i выбрать А.
| + | |
| − | | + | |
| − | <m>P_{i+1}(N_A=k) = \frac{1}{i+1} \frac{k-1}{i+2} + \frac{1}{i+1} \frac{i+2-k}{i+2} = \frac{i+1}{(i+1)(i+2)} = \frac{1}{i+2}</m>.
| + | |
| − | | + | |
| − | Что и требовалось доказать.
| + | |
Версия 12:08, 24 декабря 2014
В аквариуме плавают существа типа A и B. Изначально их двое — A и B. Каждым ходом мы случайно выбираем одно существо, светим на него лучем жизни, после чего оно клонируется (превращается в двух существ такого же типа).
Покажите, что после n-ходов, число существ типа A будет равновероятно распределено между 1 и n-1.