Вероятность/Задачи/random-cloning-n-times

Ссылки сюда (11) →

В аквариуме плавают существа типа 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 выбрать А.

.

Что и требовалось доказать.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.