Задача по тер.веру

[David Sunrise]

Прошу помощи, очень мучает задача с виду простая, но что-то не решается.

В комнате K шляп принадлежат K людям. За одну попытку каждый присутствующий выбирает случайным образом одну шляпу. После этого все выбравшие свою шляпу уходят, для остальных все повторяется. Нужно найти среднее число попыток затраченное на разбор всех шляп.

Есть следующее соображение:
Пусть $\xi_i= \begin{cases} 1 - \text{правильный выбор} \\ 0 - \text{неправильный} \end{cases} $, теперь пусть $\mu_k$ число выбравших свои шляпы в попытке с $k$ людьми и $k$ шляпами, т.е $\mu_k=\xi_1+\dots+\xi_k$, тогда $\mathbb{E}(\mu_k)=k\mathbb{E}(\xi_i) =1$ т.к $\xi_i$ независимы и одинаково распределены. Значит независимо от $k$ в среднем за одну попытку "уходит" одна шляпа.
Ну и еще одно:
вероятность того, что хоть кто-то возьмет свою шляпу равна $1-(\text{вероятность того что никто не взял свою шляпу})=1-(1-k^{-1})^k$, т.е хоть кто-то берет шляпу с вероятностью $1-(1-k^{-1})^k$, и в среднем берут только одну шляпу каждый раз при каждом $k$, дальше не знаю что делать.

[provincialka]

Не очень поняла, за один раз все берут шляпы? Тогда величины $\xi_i$ зависимы. Например, не может быть так, что все, кроме одного, взяли свои шляпы.

-- 05.04.2014, 19:11 --

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

[Brukvalub]

Интересно, "откуда дровишки"? По первым прикидкам, задача кажется "гробовой".

[nikvic]

provincialka в сообщении #845831 писал(а):

Не очень поняла, за один раз все берут шляпы?

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

[Brukvalub]

nikvic в сообщении #845841 писал(а):

provincialka в сообщении #845831 писал(а):

Не очень поняла, за один раз все берут шляпы?

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

Нет. Представим ситуацию: в прихожей погас свет, все побежали в темную прихожую и похватали по одной шляпе. При первом разборе шляп один схватил свою шляпу, а остальные - чужие. Тогда этот один пошел домой, а остальные снова повесили шляпы на гвоздики, вышли из прихожей, снова зашли в темную прихожую, снова похватали шляпы. Теперь двое схватили свои шляпы, а остальные - чужие. Двое пошли домой, а остальные повесили шляпы на гвоздики, вышли из прихожей, снова зашли в темную прихожую и т.д.

[David Sunrise]

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

[nikvic]

Ок, теперь ясно.

[David Sunrise]

Откуда сказать не могу, и сам не знаю.
Пример:
Допустим 3 человека
1 попытка:
1 $\to$ 3 (первый человек выбрал третью шляпу)
2 $\to$ 2
3 $\to$ 2

Итог: 2й ушел 1й и 3й остались.

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

[provincialka]

Рассуждение с индикаторами верное, и то, что соответствующие величины зависимы, нисколько не мешает. Проверка на небольших числах подтверждает вывод. Например, при одном "шляпозаборе" возможны следующие варианты (номера шляп указаны в порядке номеров людей). $n$ - числе совпадений

$k=2$
$(1, 2)$ $n=2$
$(2, 1)$ $n = 0$
среднее значение 1

$k=3$
$(1, 2, 3)$ $n=3$
$(2;3З;1)$ $n = 0$
$(3З;1;2)$ $n=0$
$(3, 2, 1)$ $n = 1$
$(2,1,3З )$ $n=1$
$(1,3З, 2)$ $n = 1$
среднее значение 1

И вообще за один раз в среднем берется по 1 шляпе. Можно ли из этого сделат вывод, что в среднем понадобится $k$ "заходов"? Интуитивно кажется, что да, но как это доказать?

[nikvic]

provincialka в сообщении #845921 писал(а):

но как это доказать?

Процесс можно представить по-другому. Очередной неудачник не уходит домой, а становится в конец очереди.
Получаем "линейную" цепь Маркова.
====
Но это, похоже, не совсем то...

[--mS--]

nikvic в сообщении #845934 писал(а):

Процесс можно представить по-другому. Очередной неудачник не уходит домой, а становится в конец очереди.

Кажется, Вы всё-таки не поняли условия. Цепь Маркова неоднородная тут, конечно, есть изначально - количество оставшихся шляп после каждого разбора образует ЦМ, толку-то от неё. В исходном сообщении всё, что верно - это только $\mathsf E\mu_k=1$, а последний абзац вообще никак. Всем хорошо известно, что вероятность никому не выбрать свои шляпы есть $!K/K!$, где $!K$ - субфакториал, а никакие не степени из-за зависимости $\xi_i$.

Доказывать проще всего по индукции. Пусть $\tau_n$ - число шагов, которые потребовалось для полного разбора всех $n$ шляп. Пусть для $k=1,\ldots,n-1$ известно, что $\mathsf E\tau_k=k$. Докажем, что $\mathsf E\tau_n=n$.

Пусть $\zeta_n$ - число шляп, которые ушли за первый шаг, если их изначально было $n$. Пусть распределение $\zeta_n$ описывается набором вероятностей $\mathsf P(\zeta_n=i)=p_i$, $i=0,\ldots,n$. Они выписываются, конечно, через те же субфакториалы, но мы без них обойдёмся. Достаточно того, что $\mathsf E\zeta_n=1$.

Тогда имеет место следующая рекуррентная формула. Один раз разобрали $n$ шляп. Тогда $\tau_n - 1$ (уже осталось на 1 шаг меньше) совпадает по распределению с величиной

$$\tau_n\cdot \textrm I(\zeta_n=0)+\tau_{n-1}\cdot \textrm I(\zeta_n=1)+\ldots+\tau_1\cdot \textrm I(\zeta_n=n-1)+0\cdot \textrm I(\zeta_n=n).$$

Последние два слагаемых нулевые, но это неважно. В этой сумме $\tau_k$ - это количества шагов после того, как осталось $k$ шляп. Они независимы с результатом предыдущего извлечения шляп $\zeta_n$. Их надо было бы, конечно, новыми буковками обозначить, потому как $\tau_n$ "старая" от $\zeta_n$ зависит, а "новая" уже нет, но мне стало лениво ещё индексы заводить.

$$\mathsf E\tau_n - 1=\mathsf E\tau_n p_0 + \mathsf E\tau_{n-1}p_1+\ldots+\mathsf E\tau_1 p_{n-1}+0p_n = $$

(используем индукционное предположение)

$$= \mathsf E\tau_n p_0 + (n-1)p_1+(n-2)p_2+\ldots +(n-(n-1))p_{n-1}+(n-n)p_n = $$

(перегруппируем слагаемые)

$$=\mathsf E\tau_n p_0 + n(p_1+\ldots+p_n) - \sum_{k=1}^n kp_k = \mathsf E\tau_n p_0 +n(1-p_0) -\mathsf E\zeta_n =\mathsf E\tau_n p_0+ n(1-p_0) - 1. $$

Отсюда $\mathsf E\tau_n (1-p_0)=n(1-p_0)$, $\mathsf E\tau_n =n$.

[nikvic]

Прекрасно