2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Берем k элементов с возвратом, а потом выбрасываем дубликаты
Сообщение13.07.2013, 20:27 


07/01/11
55
Задача
Из множества $U$ $k$ раз выбрали случайный элемент с возвратом и получили множество $S_k$. $|U| = n$. Чему в среднем равно $x_k = |S_k|$?

Мои мысли
Если рассмотреть $x_k$ как состояние процесса Маркова на $k$-м шаге и обозначить $x_i = |S_i|, \, i = 0, 1, ... $ то можно записать матрицу переходов $A = \left ( \mathbb P \left ( x_n = j - 1 | x_{n - 1} = i - 1 \right )\right )_{(n + 1) \times (n + 1)}$:
$$ A = \begin{pmatrix}
0 & 1 & 0 & \hdotsfor 2 & 0 & 0 \\
0 & \frac 1 n & \frac{n - 1}{n} & \hdotsfor 2 & 0 & 0 \\
0 & 0 & \frac 2 n & \frac{n - 2}{n} & \ldots & 0 & 0 \\
\hdotsfor 7 \\
0 & 0 & 0 & \hdotsfor 2 & \frac{n - 1}{n} & \frac 1 n \\
0 & 0 & 0 & \hdotsfor 2 & 0 & 1 

\end{pmatrix}$$
Теперь можно получить распределение $p_k$ величины $x_k$:
$$p_k = p_0 A^k, \quad p_0 = \left (1, \, 0, \, 0, \, \dots, \, 0 \right )$$
И по расределению найти $\mathbb E x_k$.

Вопрос
Как найти $A^k$?
Или может быть есть более простой путь?

Спасибо :-)

 Профиль  
                  
 
 Re: Берем k элементов с возвратом, а потом выбрасываем дубликаты
Сообщение14.07.2013, 04:17 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Есть более простой путь. :wink:
Зафиксируем $k$ и пусть$$\xi_i=\begin{cases}
 0,&\text{если $i$-й элемент не выбран ни разу;}\\
 1,&\text{если $i$-й элемент выбран хотя бы один раз .}
\end{cases}$$Если $\xi=\sum\limits_{i=1}^n {\xi_i}$, то $\xi=|S_k|$. Нам нужно найти $M \xi=\sum\limits_{i=1}^n {M \xi_i}=\sum\limits_{i=1}^n {\mathbb P\lbrace\xi_i=1\rbrace}=\sum\limits_{i=1}^n {\mathbb P\lbrace\xi_1=1\rbrace}=nP\lbrace\xi_1=1\rbrace.$ Ну а дальше, я думаю, и сами справитесь. :D

 Профиль  
                  
 
 Re: Берем k элементов с возвратом, а потом выбрасываем дубликаты
Сообщение28.07.2013, 09:51 


07/01/11
55
Действительно просто! Спасибо :-)

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

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



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

Сейчас этот форум просматривают: Shadow


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

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