Сколько в среднем потребуется выборов(с возвращением), чтобы выбрать хотя бы по одному разу все элементы из множества $% \{1,2...k\}$%

задан 26 Июн '17 11:44

10|600 символов нужно символов осталось
2

Хорошо известен такой факт: если вероятность успеха равна $%p > 0$%, то среднее число независимых испытаний до наступления первого успеха, равно $%\frac1p$%. Это можно доказать разными способами, и на форуме это всё неоднократно рассматривалось.

Теперь рассмотрим случайные величины $%X_1$%, $%X_2$%, ... , $%X_k$%, где $%X_1$% -- число шагов до появления первого нового элемента множества (очевидно, $%X_1=1$%), $%X_2$% -- число шагов до появления второго нового элемента, ... , $%X_k$% -- число шагов до появления последнего, $%k$%-го элемента (после того, как предыдущие уже все появились).

После того, когда $%i-1$% номеров уже появились, вероятность извлечь новый номер, которого раньше не было, равна $%p=\frac{k-(i-1)}k$%. По предыдущему, $%MX_i=\frac1p=\frac{k}{k-i+1}$%. Ввиду аддитивности матожидания, общее среднее время до выпадения по разу каждого из номеров есть $%M(X_1+\cdots+X_k)=MX_1+MX_2+\cdots+MX_k=\frac{k}k+\frac{k}{k-1}+\cdots+\frac{k}1=kH_k$%, где $%H_k=1+\frac12+\cdots+\frac1k$% есть $%k$%-е гармоническое число.

Известно, что $%H_k$% приближённо равно $%\ln k+\gamma$%, где $%\gamma\approx0,577$%. Тогда, чтобы собрать полную колоду из 36 карт, при условии, что нам каждый раз случайно достаётся одна из карт (например, её вкладывают в пачку сигарет), в среднем потребуется около $%36(1+\frac12+\cdots+\frac1{36})\approx36(\ln36+\gamma)\approx149,77$% испытаний.

ссылка

отвечен 26 Июн '17 12:34

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,709

задан
26 Июн '17 11:44

показан
250 раз

обновлен
26 Июн '17 12:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru