Мальчик собирает изображения покемонов, которые кладут в пакетики с печеньем. Всего разных покемонов - 100 штук. Сколько пакетиков в среднем придётся купить родителям мальчика, чтобы он собрал всю коллекцию? В каждый пакетик случайно и независимо от содержимого других пакетиков кладётся один покемон.

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

Но второе образование <экономика> позволило привести эту задачку к реальным условиям.

 

Усложним условия!

НИ один производитель не будет печатать 100 покемонов в равных пропорциях.

Бедные покемоны...

DJ Gotya:

Каждый новый пакетик прибавит в коллекцию новый (M+1-ый) покемон с вероятностью (N-M)/N. Таким образом, на добывание M+1-го покемона затратится в среднем N/(N-M) пакетиков с печеньем...

Пусть ты нажимаешь на кнопку, а лампочка загорается с вероятностью p. То есть, если ты нажмёшь очень много раз, то лампочка зажжётся где-то в p раз меньшее количество раз, и нажимаю кнопку, ты не знаешь, зажжётся лампочка или нет (то есть, она не каждый 1/p-ый раз зажигается). Допустим, ты прекращаешь нажимать кнопку после первого зажигания лампочки, сколько раз ты её нажал? Ответ: вообще-то неизвестно, но порядок величины величины - 1/p раз (а может получиться и с первого раза). Каждому количеству нажатий n на кнопку можно приписать число p_n (вероятность того, что ты нажал на кнопку именно столько раз), причём sum_n p_n = 1, все p_n положительные. Если бы мы с тобой играли в игру: ты говоришь: "Я нажал на кнопку 10 или 20 раз, если угадаешь - я даю тебе рубль, если нет - ты мне", то если p_10 > p_20, то мне выгоднее сказать 10, и в такой игре (если играть очень много раз) я, скорее всего выиграю, а если буду говорить 20, то проиграю. В задаче про кнопку и лампочку p_n = p (1-p)^{n-1}, n > 1.

 

Среднее количество нажатий есть sum_n n p_n. Можешь в качестве упражнения доказать, что в нашем случае <p> = sum_{n=1}^infty n p (1-p)^{n-1} = 1/p. А почему среднее так определено - подумай. Но если ты будешь играть в игру много раз, и общее количество нажатий поделишь на количество зажиганий лампочки, то получишь число, близкое к 1/p (причём чем больше раз сыграешь - тем ближе).

 

То, что (1 + 1/2 + ... 1/N) при больших N ведёт себя как ln N можно понять так: int_{N_0}^N dx/x = ln(N/N_0), а при больших N сумму (кроме её начала, конечно) можно приблизить интегралом.

 

itech: Пусть имеется две группы покемонов, обе - заметные доли общего числа N, и покемоны из первой группы попадаются в q раз чаще, чем из второй. Наплюём временно на первую группу, и будем собирать коллекцию "вторых" покемонов. Вероятность, что в пакетике "второй" покемон - P = (N_2/(qN_1 + N_2)). Коллекцию "вторых" соберём в среднем за (N_2 ln N_2)/P = (qN_1 + N_2) ln N_2 пакетиков. При этом, вполне вероятно, мы соберём и коллекцию "первых" покемонов (кстати, ln N_2 недалёк от ln N). IMHO, неравномерное подкладывание покемонов увеличивает общий коэффициент. Например, если N_1 = N_2 = N/2, то в среднем надо где-то ((q+1)/2) N ln N пакетиков. Я не утверждаю, что коэффициент (qN_1 + N_2)/N - правда жизни (хотя при больших q так и есть), но к ответу N ln N припишется множитель тем больший, чем больше неравномерность подкладывания покемонов.

Я не утверждаю, что коэффициент (qN_1 + N_2)/N - правда жизни (хотя при больших q так и есть), но к ответу N ln N припишется множитель тем больший, чем больше неравномерность подкладывания покемонов.

Как насчёт гипотезы, что множитель определяется минимумом по 1<=k<=N вероятностей p[k] нахождения в очередном пакетике k-го покемона? Или для точного решения нужно знать и использовать все p[k]?

Пусть p_min = min(p[k], k = 1, 2, ..., N). Если 1/p_min >> количества, необходимого для сбора коллекции без этого "минимального", то, действительно, всё определяется именно p_min (и надо в среднем 1/p_min пакетиков). Если же нет, то надо знать, как быстро набирается вся коллекция и, соответственно, все p[k]. Поэтому: "при больших q".

А задача-то комбинаторная…

 

Вернёмся опять к двум покемонам, но на этот раз с вероятностями p_1, p_2, где sum{p_k| 1<=k<=2}=1.

 

Исходно (после 0 пакетов) у нас будет ровно 0 покемонов, с вероятностью 1*p_1^0*p_2^0 из них 0 первых и 0 вторых.

 

После 1 пакета у нас будет 1 покемон. С вероятностью 1*p_1^1*p_2^0 — 1 первый и 0 вторых, с вероятностью 1*p_1^0*p_2^1 — 0 первых и 1 второй.

 

После 2 пакетов у нас будет 2 покемона. С вероятностью 1*p_1^2*p_2^0 — 2 первых и 0 вторых, с вероятностью 2*p_1^1*p_2^1 — 1 первый и 1 второй, с вероятностью 1*p_1^0*p_2^2 — 0 первых и 2 вторых.

 

Ничего не напоминает?

 

Правильно, треугольник Паскаля aka биномиальные коэффициенты.

 

После n пакетов у нас будет n покемонов. С вероятностью P(n, <k_1, k_2>) = (n!/(k_1!*k_2!))*p_1^k_1*p_2^k_2 — k_1 первых и k_2 вторых, где sum{k_i| 1<=i<=2} = n.

 

Вероятность того, что после n пакетов у нас будет t различных покемонов равна P(n, t) = sum{P(n, <k_1, k_2>)| t = count{i| 0 != k_i, 1<=i<=2}}. То есть P(n, 0) = 0, P(n, 1) = p_1^n + p_2^n, P(n, 2) = 1 - (p_1^n + p_2^n).

 

Расширяем задачу обратно на N покемонов. При этом:

n = sum{k_i| 1<=i<=N},

P(n, <k_1, …, k_N>) = (n!/product{k_i!| 1<=i<=N})*product{p_i^k_i| 1<=i<=N},

P(n, t) = sum{P(n, <k_1, …, k_N>)| t = count{i| 0 != k_i, 1<=i<=N}},

 

Здесь не учтено то, что мы перестаём покупать пакеты, собрав коллекцию. Простое перемножение P(n, N)*P(n-1, N-1) не подходит.

 

Это так, идеи… расчёты оставляю читателям в качестве упражнения :)