На внутренней стороне конфетных фантиков напечатаны добрые пожелания. Сколько в среднем конфет понадобится, чтобы собрать все s разных пожеланий?

задан 12 Мар '20 21:27

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

Это известная задача, она в каком-то виде на форуме уже была.

Для начала лемма: если событие происходит с вероятностью p > 0, то для его наступления в среднем требуется 1/p испытаний. Это легко доказывается, например, с помощью рядов.

Рассмотрим теперь число испытаний, которое нужно для получения s конфет. Представим эту случайную величину в виде суммы X(1)+X(2)+...+X(s), где X(1)=1, и X(i+1) есть число испытаний до получения (i+1)-го нового пожелания после получения i-го (при i < s). Матожидание X(i) равно s/(s-i), так как вероятность успеха составляет (s-i)/s: на рассматриваемом шаге i пожеланий уже были, и s-i являются новыми.

Итого матожидание суммы как суммы матожиданий равно s/s+s/(s-1)+...+s/2+s/1=sH(s), где H(s)=1+1/2+...+1/s есть s-е гармоническое число. Оно растёт примерно как ln s.

Скажем, при s=36 (колода карт) требуется примерно 150 испытаний.

ссылка

отвечен 12 Мар '20 22:01

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

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

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

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

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

отмечен:

×4,045
×382
×120

задан
12 Мар '20 21:27

показан
1297 раз

обновлен
12 Мар '20 22:01

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

по почте:

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

по RSS:

Ответы

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

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