Вероятность/Задачи/random-cloning-n-times — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | В аквариуме плавают существа типа A и B. | + | В аквариуме плавают существа типа A и B. Изначально их двое — A и B. Каждым ходом мы случайно выбираем одно существо, светим на него лучем жизни, после чего оно клонируется (превращается в двух существ такого же типа). |
| − | Изначально их двое — A и B. | + | |
| − | Каждым ходом мы случайно выбираем одно существо, светим на него лучем жизни, после чего оно клонируется (превращается в двух существ такого же типа). | + | |
| − | + | ||
Покажите, что после <tt>n</tt>-ходов, число существ типа A будет равновероятно распределено между <tt>1</tt> и <tt>n-1</tt>. | Покажите, что после <tt>n</tt>-ходов, число существ типа A будет равновероятно распределено между <tt>1</tt> и <tt>n-1</tt>. | ||
| − | [[ | + | ==Стенина Мария, группа 974== |
| + | |||
| + | [[Категория:На проверку]] | ||
| + | |||
| + | Вероятно, в условии опечатка, потому что число существ типа А будет равномерно распределено между <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>. | ||
| + | |||
| + | Что и требовалось доказать. | ||
Версия 10:03, 10 октября 2014
В аквариуме плавают существа типа A и B. Изначально их двое — A и B. Каждым ходом мы случайно выбираем одно существо, светим на него лучем жизни, после чего оно клонируется (превращается в двух существ такого же типа).
Покажите, что после n-ходов, число существ типа A будет равновероятно распределено между 1 и n-1.
Содержание
Стенина Мария, группа 974
Вероятно, в условии опечатка, потому что число существ типа А будет равномерно распределено между 1 и n+1.
Решение
Введем величину --- вероятность того, что после i ходов у нас имеется k существ типа А. Нужно показать, что
- , то есть эта величина не зависит от k.
Сделаем это по индукции.
База индукции .
Мы сделали только один шаг, с вероятностью 0.5 выбрали А. Поэтому имеем
- .
Индукционный переход.
Пусть мы доказали, что не зависит от k. Покажем, что .
После i+1 шагов ситуация возможна в двух случаях
1) после i шагов было , и мы выбрали А;
2) после i шагов было , и мы выбрали В.
Соответственно вероятность запишется
- ,
где --- вероятность на шаге i выбрать А.
.
Что и требовалось доказать.