Задача про обувь

fore · Сообщение **fore** » 23 окт 2010, 19:10

Прошу помощи. Задача такая:
B доме 2 двери. Сейчас по 2 пары туфлей у каждой.Перед каждой прогулкой хозяин выбирает наугад одну из дверей для выхода из дома и надевает пару ботинок, стоящуюю у выбранной двери. Возвращаясь c прогулки, хозяин случайным образом выбирает дверь и снимает ботинки возле двери. Сколько хозяин прогулок в среднем совершит, прежде чем обнаружит, что у выбранной им для выхода из дома двери не осталось ботинок?

Вроде как можно решить через реккурентное соотношение, через условное матожидание, либо выписывать все случаи, но там дальше также не очень понятно что делать.

vicvolf · Сообщение **vicvolf** » 23 окт 2010, 21:56

fore писал(а):Source of the post
Прошу помощи. Задача такая:
B доме 2 двери. Сейчас по 2 пары туфлей у каждой.Перед каждой прогулкой хозяин выбирает наугад одну из дверей для выхода из дома и надевает пару ботинок, стоящуюю у выбранной двери. Возвращаясь c прогулки, хозяин случайным образом выбирает дверь и снимает ботинки возле двери. Сколько хозяин прогулок в среднем совершит, прежде чем обнаружит, что у выбранной им для выхода из дома двери не осталось ботинок?

Математическое ожидание числа прогулок:
$M(x)=2*0,5+3*0,5^2+..+n*0,5^{n-1}+...=$
Сумма указанного ряда считается, как производная от суммы бесконечной геометрической прогрессии в точке 0,5

Dm13 · Сообщение **Dm13** » 23 окт 2010, 23:49

Виктор B , думаю, что вероятность того, что прогулок будет две, все же не одна вторая. И задача намного хитрее.

Обозначим $p_{ij}(n)$ вероятность того, что у первой двери будет $$i$$

пар туфель, у второй $$j$$

туфель после $$n$$

прогулок. И обозначим $$P(n)$$

вероятность того, что $$n$$

-я прогулка последняя. Вероятность того, что хозяин выйдет через дверь $$i$$

, a войдет через дверь $$j$$

равна $\frac{1}{4}$ . Тогда получаем:
$p_{22}(1) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$
$p_{31}(1) = \frac{1}{4}$
$p_{13}(1)=\frac{1}{4}$
$$ P(1)=0 $$

вероятности остальных комбинаций очевидно 0.
Далее,
$p_{22}(2) = \frac{1}{2}p_{22}(1) + \frac{1}{4}p_{13}(1) + \frac{1}{4}p_{31}(1) = \frac{3}{8}$
$p_{04}(2) = \frac{1}{4}p_{13}(1) = \frac{1}{16}$
$p_{13}(2)= \frac{1}{2}p_{13}(1) + \frac{1}{4}p_{22}(1) = \frac{1}{4}$
$p_{31}(2)= \frac{1}{2}p_{31}(1) + \frac{1}{4}p_{22}(1) = \frac{1}{4}$
$p_{40}(2) = \frac{1}{4}p_{31}(1) = \frac{1}{16}$
$P(2)=\frac{1}{2}p_{04}(2) + \frac{1}{2}p_{40}(2)=\frac{1}{16}$ .
Далее несложно заметить рекурретную зависимость:
$p_{22}(n) = \frac{1}{2}p_{22}(n-1) + \frac{1}{4}p_{13}(n-1) + \frac{1}{4}p_{31}(n-1)$
$p_{04}(n) = \frac{1}{4}p_{13}(n-1) + \frac{1}{4}p_{04}(n-1)$
$p_{13}(n)= \frac{1}{2}p_{13}(n-1) + \frac{1}{4}p_{22}(n-1)$
$p_{31}(n)= \frac{1}{2}p_{31}(n-1) + \frac{1}{4}p_{22}(n-1)$
$p_{40}(n) = \frac{1}{4}p_{31}(n-1)+\frac{1}{4}p_{40}(n-1)$
$P(n)=\frac{1}{2}p_{04}(n) + \frac{1}{2}p_{40}(n)$ .

Искомое мат. ожидание равно
$\sum_{n=2}^{\infty} nP(n)$ .

Поскольку уже почти 3 часа ночи (или утра), то раскрытие рекурретных соотношений отношу на следующий день. Если понадобится.

fore · Сообщение **fore** » 24 окт 2010, 07:46

Спасибо.

Надо найти я так понимаю только $f_{04}(k)$ и $f_{40}(k)$ . Формально для f_04 получается такое

$f_{04} = [ C + \sum_{j=0}^{k-1} {2^{j-1} f_{13}(j) } ] ( \frac {1} {2} )^k$ (решал как линейное разностное) но что дальше делать c $f_{13} (j)$ не знаю. пробовал выражать но толку не особо

PS там, где Вы уже выписали реккурентную зависимость, во 2 и в 5 строчках во вторых слагаемых не 1/2 должна быть ? ведь прогулка, которая возвращает то же количество обуви, возможна c вероятностью 1/2, как выяснили выше

mihailm · Сообщение **mihailm** » 24 окт 2010, 08:42

Эксперимент в maple говорит, что примерно 12 прогулок

vicvolf · Сообщение **vicvolf** » 24 окт 2010, 09:10

mihailm писал(а):Source of the post
Эксперимент в maple говорит, что примерно 12 прогулок

Это не реально большое число!
Давайте лучше пойдем от противоположного события - что он каждый раз будет возращаться в ту дверь из какой вышел. B этом случае он никогда не обнаружит отсутствие обуви.
Вероятность этого события равна $$0,5^n$$

, где n число прогулок.

fore · Сообщение **fore** » 24 окт 2010, 09:19

Ответ действительно 12, только $$ P(n) $$

выразить бы )

vicvolf · Сообщение **vicvolf** » 24 окт 2010, 09:33

Dm13 писал(а):Source of the post
Обозначим $p_{ij}(n)$ вероятность того, что у первой двери будет пар туфель, у второй туфель после прогулок.

Извините по условию задачи в начале у каждой двери стоят по одной паре обуви и больше нет! Значит, если хозяин выщел из одной двери и вошел в другую, то у первой двери обуви уже не осталось! И если при втором выходе хозяин выйдет снова из первой двери, то он это обнаружит. Вероятность этого события 0,25 (что за 2 прогулки хозяин это обнаружит). He надо усложнять

Dm13 · Сообщение **Dm13** » 24 окт 2010, 09:35

vicvolf писал(а):Source of the post
Извините по условию задачи в начале у каждой двери стоят по одной паре

По условию по две. "B доме 2 двери. Сейчас по 2 пары туфлей у каждой." He две туфли, a две пары туфлей.

vicvolf · Сообщение **vicvolf** » 24 окт 2010, 09:47

fore писал(а):Source of the post
Ответ действительно 12, только выразить бы )

Ответ при данной модели может и такой - да модель не верна!

Dm13 писал(а):Source of the post
По условию по две. "B доме 2 двери. Сейчас по 2 пары туфлей у каждой." He две туфли, a две пары туфлей.

Да перепутал,по две пары, но это значит, что минимально на третью прогулку хозяин туфлей это обнаружит и среднее число прогулок значительно меньше! Да и модель для двух пар туфлей по-моему сложновата!

yourdomain.com