2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему
 
 Задача по тер.веру
Сообщение05.04.2014, 16:47 


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

В комнате 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$, дальше не знаю что делать.

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:00 
Заслуженный участник
Аватара пользователя


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

-- 05.04.2014, 19:11 --

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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:13 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:17 
Заслуженный участник
Аватара пользователя


06/04/10
3152
provincialka в сообщении #845831 писал(а):
Не очень поняла, за один раз все берут шляпы?

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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:23 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
nikvic в сообщении #845841 писал(а):
provincialka в сообщении #845831 писал(а):
Не очень поняла, за один раз все берут шляпы?

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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:29 


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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:40 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Ок, теперь ясно.

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 18:43 


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

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

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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 21:15 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Рассуждение с индикаторами верное, и то, что соответствующие величины зависимы, нисколько не мешает. Проверка на небольших числах подтверждает вывод. Например, при одном "шляпозаборе" возможны следующие варианты (номера шляп указаны в порядке номеров людей). $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$ "заходов"? Интуитивно кажется, что да, но как это доказать?

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение05.04.2014, 21:58 
Заслуженный участник
Аватара пользователя


06/04/10
3152
provincialka в сообщении #845921 писал(а):
но как это доказать?

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

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение06.04.2014, 10:09 
Заслуженный участник
Аватара пользователя


23/11/06
4171
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$.

 Профиль  
                  
 
 Re: Задача по тер.веру
Сообщение06.04.2014, 13:27 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Прекрасно :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group