Карточки футболистов (вероятность)

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


1) Сколько в среднем разных карточек у него будет если он купит 100 упаковок

2)сколько в среднем надо купить упаковок чтобы собрать все карточки.

(имеется ввиду мат. ожидание)

Сообщение отредактировано: esperanto - 23.08.03, 18:32

Одно из необходимых требований - это как минимум знание общего "тиража" карточек.. и количество карточек в упаковке..

Цитата GrAnd, 25.08.03, 13:04:06

Одно из необходимых требований - это как минимум знание общего "тиража" карточек.. и количество карточек в упаковке..

тираж очень большой
т.е кажая карточка равновероятна

100*ln(100)

Не силен в вероятности, но вроде так: надо считать вероятность купить дубликат.

На первом шаге такая вероятность отсутствует, т.е. покупается 1 карточка со 100% успехом.
На следующей итерации вероятность купить дубликат 0.01, так что 1/0.99 = 100/99 карточек.
На следующей итерации 100/98
...
На последней итерации 100/1 = 100
Просуммировав 100/N, где N от 1 до 100, получим кол-во карточек, в среднем необходимое для заполнения альбома.

Единственно что не знаю - верен ли вывод о вероятности 100/(100-N) на шаге N. Дело давнее, в универе я в теорвер как-то глубоко не погружался. То ли преподы не те, то ли я не такой...

7 лет прошло, разобрался наверное уже

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

q(k,m) = Sum{i=1,k-1}(-1)^(i -1) C(i,k)(k - i)^m

(здесь C(i,k) – биномиальный коэффициент, ^ - степень, Sum{i=1,k-1} – сумма по i от 1 до k).

Тогда p(k,m) = C(k,n)(k^m - q(k,m))/n^m .

Рассмотрим теперь случайную величину: число непустых ячеек. Её математическое ожидание

М = Sum{k=1,n}k p(k,m) .

Пусть теперь m – число купленных конвертов, n – число всех футболистов, k – число различных футболистов в конвертах. Как упростить формулу, в частности, при m = n , не знаю.

ЗЫ. Решала не я.

Сообщение отредактировано: Swetlana - 03.04.10, 07:02

Цитата Swetlana @ 03.04.10, 06:55

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

q(k,m) = Sum{i=1,k-1}(-1)^(i -1) C(i,k)(k - i)^m

(здесь C(i,k) – биномиальный коэффициент, ^ - степень, Sum{i=1,k-1} – сумма по i от 1 до k).

Тогда p(k,m) = C(k,n)(k^m - q(k,m))/n^m .

Рассмотрим теперь случайную величину: число непустых ячеек. Её математическое ожидание

М = Sum{k=1,n}k p(k,m) .

Пусть теперь m – число купленных конвертов, n – число всех футболистов, k – число различных футболистов в конвертах. Как упростить формулу, в частности, при m = n , не знаю.

ЗЫ. Решала не я.

Так давно это было .

Задача известная под именем coupon collector.(Мостеллер 50 занимательных задач по теории вероятностей).


Достаточно просто решается используя свойство линейности мат.ожидания.

Сколько в среднем разных карточек у него будет если он купит 100 упаковок
100*Вероятность(первая карточка будет среди купленных карточек)


2)сколько в среднем надо купить упаковок чтобы собрать все карточки.
1+100\99+100\98+...=100лог100+конст

Хе-хе, я что, даже правильно решил? Ибо теорвер у меня после универа промелькнул лишь один раз - когда гуглы позвали собеседоваться. Вот там на очном интервью два перца подряд предлагали "let's talk about ...errr... ummmm... probability theory?". Я вышел оттуда весьма удивленным, потом уж понял, зачем им оно.

Сообщение отредактировано: Mr.Delphist - 03.04.10, 15:41

esperanto, у тебя 2 вопроса.
Ты цитируешь мой пост, который отвечает на 1 вопрос, а потом приводишь ответ на 2 вопрос.
Тогда уж приведи простое решение 1 вопроса.

Цитата Swetlana @ 03.04.10, 17:52

esperanto, у тебя 2 вопроса.
Ты цитируешь мой пост, который отвечает на 1 вопрос, а потом приводишь ответ на 2 вопрос.
Тогда уж приведи простое решение 1 вопроса.

Видимо лишнего нацитировал. Я там на оба вопроса ответил