...

понедельник, 11 января 2016 г.

Использование МатАнализа в компьютерных играх (часть 2)

Ключевые слова:Задача о коллекции; Wolfram Alpha; Wolfram Mathematica; числа Стирлинга второго рода; матанализ; теория вероятностей; мат ожидание; медиана; квантиль; компьютерные игры; коллекция вкладышей; функция распределения случайной величины; плотность вероятности, ArcheAge.

Введение


Когда остается заполучить только три из ста предметов для того чтобы собрать всю коллекцию (вкладышей жвачек БомБимБома или Турбо, или набора тяжелых доспехов для персонажа компьютерной игры), то огонь в глазах и ожидание чуда вытесняют и логику и разум и попытки математического анализа из головы напрочь. Есть только одна мысль «Ещё чуть-чуть и я заполучу оставшееся! Я соберу всю!». В это время, родные и друзья, этого одержимого коллекционера озадачены лишь только одним вопросом – «А, чуть-чуть, это сколько?!». Сколько маме нужно купить ещё ненавистных жвачек, или сколько нужно ещё девушке сидеть одной, пока её парень не выбьет с монстров в игре «редчайшие трусы Баала»?!
Ответить на вопрос «сколько нужно купить жевательных резинок, чтобы собрать полную коллекцию из N-штук вкладышей» сходу довольно сложно, даже если пользоваться Яндексом, потому, что сложно сформулировать сам запрос для «обычного» поисковика. Попытка решения задачи самостоятельно обычно ставит людей в тупик – не понятно, с какой стороны к ней подступиться.
В данной статье будут рассмотрены три вопроса: Как подходить к задачам, которые не понятно на первый взгляд как решать? Каким поисковиком пользоваться для того чтобы получать научные ответы на научные вопросы (а не получать предложения купить формулу квадратного уравнения на eBay)? И конечно, сколько же нужно купить жвачек, чтобы собрать коллекцию вкладышей?

Навигация по статье


Статья получилась довольно большой. Поэтому в тех местах, где можно что-то пропустить, я буду об этом сообщать. В таких главах будет рассматриваться не решение задачи, а те понятия и принципы которое используются при её решении. Если же станут интересны подробности, то можете перечитать пропущенные места позже. С формулировкой задачи стоит ознакомиться, а вот далее, те, кто хочет поскорее ознакомиться с ответом, могут сразу перейти к результатам. Советую, однако, отдельно ознакомиться с главой посвященной Alpha Wolfram.
Так же для удобства, привожу полный список глав.
  1. Постановка задачи
  2. Парни, девушки и шары
  3. Математическое моделирование одержимого коллекционера
  4. Любопытная таблица
  5. Азъ есмь Alpha Wolfram
  6. Математический детектив
  7. Триста лет тому назад
  8. Три строчки
  9. Две сущности
  10. Средняя температура пациентов и средняя зарплата врачей
  11. Там, где прямо не пролезем, мы пройдём бочком
  12. Wiki-больство какое-то
  13. Результаты
  14. День рождения и банка плесени
  15. Выводы

Постановка задачи


Чтобы было понятно и тем, кто любит математическую строгость, и тем, кто с ней не знаком, сформулирую задачу о коллекции двумя способами.
  1. (Через язык знакомый с детства) Пусть каждая жвачка содержит с равной вероятностью один из K вкладышей. Какова вероятность того что купив N жвачек, мы соберём всю коллекцию вкладышей(у нас будет K уникальных вкладышей)?
  2. (Более научным языком) Пусть дано множество из K элементарных исходов (все исходы равновероятны). Какова вероятность того, что после N проведенных экспериментов каждое событие произойдет хотя бы один раз?

Сразу проясним ряд моментов, которые в дальнейшем нам помогут в решении. Во-первых, для простоты все элементы коллекции будем нумеровать от 1 до K, и таким образом иметь дело просто с числами. Во-вторых, нашими элементарными исходами будут последовательности чисел длинной N, состоящие из K различных чисел. Например, если K=3 и N=5, то последовательности {3,3,1,2,3},{1,2,3,3,3},{3,3,1,1,1} одни из возможных исходов, при этом порядок элементов имеет значение. Если в такой последовательности все K чисел встречаются, хотя бы один раз – значит это «удачная» для нас последовательность, если не встречается, хотя бы одно число ни разу, значит последовательность для нас не удачная. При этом любая возможная последовательность равновероятна. В-третьих, мы всегда можем посчитать количество всех возможных последовательностей из K чисел, длиной N элементов, при условии, что порядок имеет значение. Это количество равно K^N. В-четвертых, вероятность сбора коллекции за N шагов, равна отношению «удачных» последовательностей к общему количеству, то есть к K^N. Таким образом, можно искать либо вероятность, либо само количество «удачных» последовательностей – как будет удобнее, одно всегда можно получить из другого.

Парни, девушки и шары


Те, у кого не возникло вопросов касательно «порядок имеет значение» и «количество равно K^N», а так же кто помнит что такое «факториал» и «C из n по k», эту главу можете пропустить и перейти к следующей. Для тех же, кто основательно подзабыл комбинаторику, или ещё не был с ней знаком, рассмотрим основные моменты, которые нам пригодятся.
История комбинаторики хоть и уходит корнями в глубокую древность, всё же активно развивалась благодаря гамерам. Ну, может Кардано, Галилей, Ферма Паскаль и остальные великие умы мира сего сами и не были заядлыми гамерами (хотя не факт не, факт), но как минимум гамеры их конкретно донимали вопросами об играх, про стратегии победы, просили гайды писать. Конечно, тогда больше как-то в кости да карты играли, любителей азартных игр с танками или магией было как-то не очень много. С одним был дефицит, а за другое сжигали. Но активно применявшись к анализу головоломок и азартных игр, комбинаторика оказалась исключительно полезной для решения практических задач почти во всех разделах математики. Кроме того, комбинаторные методы оказались полезными в статистике, программировании, генетике, лингвистике и многих других науках уже много времени спустя. Википедия ЗЛО (я об этом ещё не раз вспомню), но обзорные вещи не связанные с формулами там читать физически возможно, а вот доверять не стоит. Тем не менее, можете ознакомиться со статьёй «История комбинаторики»
Я пока искал различные материалы по комбинаторике, наткнулся на сайт, а точнее на один из документов с этого сайта. Понравился язык, которым написано, можете ознакомиться с комбинаторикой там. Я бы, в общем-то, и не вспомнил про этот сайт, если бы не одно «но». Там есть задача про траекторию. Мне она очень понравилась, показалась интересной, и вот глядя на неё, у меня родилась идея, как решить задачу про коллекцию, но об этом позже.
Вот основные факты из комбинаторики, которые нам пригодятся.
1.) Сколько всего существует N -значных чисел в системе счисления с основанием K? Сколькими способами можно разместить на N креслах представителей K наций? Сколькими способами можно раскрасить N квадратов, если есть фломастеры K различных цветов? Сколькими способами можно заполнить N ящиков разноцветными шарами, если количество различных цветов K и в каждый ящик влезет только один шар?
Ответ на все эти вопросы один – «Размещение с повторениями». В случае с шарами, в первый ящик мы можем положить шар любого из K цветов. То есть у нас K вариантов засунуть один шар в первый ящик. Во второй ящик мы тоже можем засунуть шар K способами. Вариантов же заполнения первого и второго ящика шарами уже будет K* K= K^2. Так получается потому, что для каждого варианта заполнения первого ящика может быть любой из K вариантов заполнения второго ящика. Если же ящиков у нас N то значит, вариантов будет K^N.
2.) Сколько всего существует N -значных чисел в системе счисления с основанием N, таких, что каждая цифра в числе встречается ровно один раз? Сколькими способами можно разместить на N креслах представителей N наций, так чтобы сидел представитель каждой нации? Сколькими способами можно раскрасить N квадратов, если есть фломастеры N различных цветов, так чтобы каждый фломастер был использован (без перекрашиваний конечно)? Сколькими способами можно заполнить N ящиков N пронумерованными шарами?
Ответ на все эти вопросы один – «Перестановка». Случаи с шарами и с цифрами, в общем-то, идентичны даже в своей формулировке. На первое место мы можем поместить любой из N шаров. На второе место любой из оставшихся N-1 шаров, на третье любой из оставшихся после заполнения первых двух мест N-2 шаров. И так далее до последнего. Получается, мы имеем произведение N*(N-1)*(N-2)*(N-3)*… *(N-(N-2)) *(N-(N-1)). Вот такое произведение всех натуральных чисел от 1 до N и называется факториалом. А обозначается оно как «N!». Да, восклицательный знак, это и есть обозначение факториала или произведения всех натуральных чисел от 1 до N. Встречается крайне часто везде и всюду, а учитывая, что писать его в виде произведения довольно долго, решили упростить и сократить запись до значка восклицательного знака. Про факториал есть старый анекдот, который любят рассказывать преподаватели.
На экзамене по матану лектор просит студента разложить экспоненту в ряд Тейлора.
Студент: Один плюс икс разделить на ОДИН(произносит громко и торжественно) плюс икс в квадрате разделить на ДВА(также громко) плюс икс в кубе разделить на ТРИ
Лектор: Хорошо, хорошо, всё правильно, только, зачем вы так кричите?!
Студент: Ну, так восклицательный знак же!!!
Стоит отметить, что факториал от нуля будет 1. 0!=1
3.) Сколькими способами можно заполнить K ящиков N пронумерованными шарами? (шаров больше чем ящиков) У вас есть N билетов в кино и K подруг. Сколькими способами вы можете раздать билеты вашим подругам? (билетов больше чем подруг)
Ответ на эти вопросы – «Размещение БЕЗ повторений». Однако решение аналогично не первому пункту, а второму. На первое место мы можем поместить любой из N шаров. На второе место любой из оставшихся N-1 шаров, на третье любой из оставшихся после заполнения первых двух мест N-2 шаров. И так далее до тех пор, пока не кончатся ящики. А значит, произведение будет N*(N-1)*(N-2)*(N-3)*… *(N-(K-1)). То есть произведение всех натуральных чисел от K+1до N. Но такое произведение можно расписать в виде N*(N-1)*(N-2)*(N-3)*… *(N-(K-1)) * (N-K)! / (N-K)! =N!/ (N-K)! Что, в общем-то, значительно короче.
4.) Последний пункт про то, почему порядок может иметь или не иметь значение. И что такое «C из n по k».
Предположим у вас есть УАЗик, и вы собрались поехать с друзьями (только парни, без девушек) на рыбалку. В УАЗик может влезть K человек. А всего у вас друзей N. Все, кто в ваш УАЗик не влезут, поедут на других машинах. Сколько есть вариантов заполнения УАЗика вашими друзьями? Сколько существует способов из 20(N) ваших знакомых который сейчас онлайн собрать команду 5 человек(K) чтобы часок поиграть в доту? (Тут конечно есть нюанс – считать вас или нет, но не будем на этом заморачиваться)
В чём различие этого примера от всех предыдущих? В том, что порядок не имеет значения. Кто, как и где будет сидеть в УАЗике, или кого вы первого, а кого второго позовете в команду, роли не играет ни какой. Главное это состав, а кто там на каком месте уже не важно. Если бы порядок имел значение, то это был бы в точности предыдущий вариант, то есть ответ был бы N!/ (N-K)!. Но нам порядок не важен. А про порядок у нас был пример 2) с факториалом. То есть N!/ (N-K)! нужно разделить на K!, и тогда случаи, которые отличались лишь последовательностью, но были одинаковы по составу, «схлопнутся в один вариант». Например, пусть есть 3 человека и 2 места. Тогда все возможные варианты. Для примера 3 будут {1,2},{1,3},{2,1},{2,3},{3,1},{3,2}. То есть 6 вариантов. 3!/(3-2)!=3!/1!=3!=6. Но в нашем примере с УАЗиком (двухместный правда сейчас уже УАЗик) не важна последовательность и поэтому варианты типа {1,2} и {2,1} одинаковы. Ну, действительно, Петя и Вася в УАЗике или Вася и Петя — разницы нету. Главное что они двое едут в нём. Получаем, что ответом для пункта 4, в котором порядок не имеет значения, будет формула N!/ (N-K)!/ K! И называются такие случаи, когда порядок не важен, а важен лишь состав «Сочетанием из N по K». Есть ещё одно название у этой чудо-формулы – «Биномиальный коэффициент». Но чаще всего называется это «C из n по k». («Цэ из эн по ка»). Обозначается соответственно буквой C с нижним и верхним индексом n и k соответственно. Биномиальный коэффициент имеет самое непосредственное отношение к широко известному «биному Ньютона». Сложного в нём ничего нет, можете прочитать про него, где захотите (Только википедию главное не читайте). Бином Ньютона и биномиальные коэффициенты по сути своей довольно просты, но вот тот факт, что они вдруг внезапно оказываются применимы в неимоверно большом количестве разнообразных ситуаций, создаёт этакий мистический ореол и подозрение что это всё неспроста. Хотя сложного там ничего нет, зато много чего интересного
Этих знаний из комбинаторики на данном этапе будет достаточно, остальное будет пояснено по ходу дела.

Математическое моделирование одержимого коллекционера


Когда я первый раз попробовал решить задачу аналитически, пытаясь честно посчитать (не перебором конечно, а формулами) все возможные удовлетворяющие условиям последовательности, у меня признаюсь ничего не вышло. Точнее сказать путь рассуждений был довольно логичным, но в итоге я приходил к необходимости записи гигантской суммы сумм, свернуть которую во что-то компактное не представлялось возможным.
В случаях, когда понятны основные принципы некоторого процесса, но при этом не можем получить вразумительный и удобоваримый закон, описывающий этот процесс (когда понимаем что и как происходит, а вот формулу для всего этого дела выписать не получается), то можно пойти от обратного – смоделировать этот процесс, получить численное решение и попытаться проанализировать ответ. Например, используя величайший из методов анализа – «Метод Пристального Взгляда». После чего вполне возможно новые полученные данные, идеи, мысли подскажут нам пути решения.
Это как подсмотреть ответ в задачнике, и потом под него подогнать решение. Мы в своё время пользовались этим, но при этом сами себя не одобряли за такое. Однако, семинарист по физике (он же и лектор был) объяснил нам, что это абсолютно нормально, и более того, физика в какой-то мере это «искусство подгонки». Очень часто сначала открывается некоторое новое явление, а затем его пытаются объяснить – то есть как бы решение, теоретическое обоснование явления пытаются подогнать под экспериментальные данные. Тогда нам это было не совсем понятно – мы привыкли что нужно «решать задачи честно». Только вот теоретическое построение гипотез с последующей экспериментальной проверкой, это одно, но вот обратные задачи встречаются порой даже чаще. И одно без другого, вообще говоря, не существовало бы. О чём теорию то строить, если изначальных данных из практики мы не получали?
Главное запомните – подгонка решения под ответ это не просто нормально, а хорошо и естественно. За такое Нобеля дают. Эйнштейн не предсказал фотоэффект, он его объяснил. А вот за своё предсказание различных эффектов связанных с ограниченностью скорости света Нобеля он не получал, хотя да – тут было именно что предсказание. Да и если посмотреть списки премий по научным дисциплинам, то очень многие идут с формулировкой «За объяснение…» «За вклад в понимание…».
Итак, раз идей о том, как вывести формулу, нет – будем моделировать.
Моделировать будем в среде Wolfram Mathematica. Mathematica очень проста в использовании, быстра, приятный и интуитивно понятный интерфейс (ну разве что Ctrl+Enter нужно знать – это комбинация для запуска выполнения куска кода на котором мы стоим; главная и основная) и главное там шикарный хелп который на 90% процентов состоит из примеров + куча ссылок по теме. Действительно полезные ссылки в самом хелпе, так что я порой начинаю там залипвнув сёрфить как в инете. Очень легко и просто отображать данные – строить графики, таблицы какие угодно и как угодно, наверно, на все случаи жизни, что для презентаций порой просто неоценимо. Устанавливайте и пробуйте – залипните и не пожалеете.
Кстати все картинки этой статьи были сделаны в Wolfram Mathematica.
Вот код для моделирования сбора коллекции из 40 элементов. В коде достаточно много комментариев. Сам алгоритм написан так, чтобы быть максимально понятным при прочтении, но при этом, правда, потерял в скорости. У меня при 100 тыс. итераций работает минут 10. 
(*Медленный но понятный алгоритм*)
SeedRandom[1234];(*"фиксирует"рандом. Когда мы хотим полуить случайную последовательность, то можем каждый раз получать новую, а можем каждый раз получать ту же самую.Если СидРандом задан, то последовательность будет всегда генериться одна и таже.*)
NPosibleElems=40;(*Количество уникальных элементов в коллекции*)
WhatWeHave=Table[0,{i,1,NPosibleElems}];(*То что мы имеем. Массив всегда должен быть длинной равной "Количество уникальных элементов".  то что имеем обозначем 1, то что не имеем обозначаем 0. Если захотим смоделировать ситуацию когда уже часть предметов есть, то нужно будет просто сделать этот массив не нулевым*)
WhatWeWantToHave=Table[1,{i,1,NPosibleElems}];(*То что мы хотим получить. Массив всегда должен быть длинной равной "Количество уникальных элементов". а то что нужно обозначем 1, то что не обязательно обозначаем 0. Если захотим смоделировать ситуацию когда целью будет собрать не все предметы, а только какую-то часть, то нужно будет сделать этот массив не весь из единиц*)
TargetArray=BitOr[WhatWeHave,WhatWeWantToHave];(*Если мы в желаемом забыли указать то что уже есть, то в силу того что невозможно потерять то что уже было, мы бинарно сложим желаемое с тем что есть. В результате мы получим непротиворечивую цель. Тут ничего править не нужно, это просто для корректной работы программы*)
NumItearations=100000;(*Сколько раз будем проводить испытания. Если вычисления проходят медленно - сделайте кол-во интераций меньше.*)
FinishedSteps=Table[0,{i,1,NumItearations}];(*Массив с результатами, в нём будут содержаться количество полученных элементов к моменту достижения цели. "сколько купили жвачек" прежде чем собрали коллекцию.*)
ProgressIndicator[Dynamic[indic],{1,NumItearations}](*В этом примере мы будем использовать индикатор прогресса. Не проверял её особо на скорость, но вроде не сильно тормозит. Переменная indic в данном случае динамическая. Тоесть изменяя её гдето в одном месте, её изменения отразятся СРАЗУ ЖЕ и в других частях документа. К НАШЕМУ АЛГОРИТМУ ЭТО НЕ ИМЕЕТ ОТНОШЕНИЯ - просто для красоты визуализации. Если не понятно, просто пропустите.*)
For[j=1,j<=NumItearations,j++, (*Начинаем в цикле собирать коллекции.*)
indic=j;(*Обновляем полоску индикатора... точнее переменную которая отвечает за положение полоски, а так как она динамическая, то индикатор сам перерисуется. При желании можно в конец цикла воткнуть, а не тут в начале*)
FindedElems=WhatWeHave;(*FindedElems - временный массив. Нашат "текущая" коллекция. При каждой новой итерации мы её будем снова сбрасывать в дфолт*)
While[ Total[TargetArray-FindedElems]!=0,(*Цикл сбора коллекции. Будем открывать новые жвачки до тех пор пока коллекцию не соберём. По идее его не плохо было бы всё же ограничить разумным числом, а то есть какаято мизерная вероятность что и за сто тысяч милионов жвачек мы коллекцию не соберём - в итоге комп может конкретно тут подвиснуть.*)
NewItem=RandomInteger[{1,NPosibleElems}];(*Эмулятор новой жвачки, собственно получение рандомного номера вкладыша*)
If[FindedElems[[NewItem]]!=1,FindedElems[[NewItem]]=1];(*Если не было такого вкладыша - добавляем его в коллекцию*)
FinishedSteps[[j]]+=1;(*Подсчитываем сколько вкладышей мы получили*)
];
];
(*Рисуем гистограмму (с настройками построения гистограммы по умолчанию). Также вытаскиваем данные из полученной гистограммы*) 
{bins,count}=HistogramList[FinishedSteps];
HistoList=Transpose[{binsN[[2;;]],count}];
TickL=20;
Show[{Histogram[FinishedSteps],ListPlot[HistoList,PlotStyle->{Darker[Red],PointSize[Large]}]},Ticks->{Table[i,{i,0,Last[bins],TickL}],Automatic}]

(*Рисуем граффик вероятностей*)
ProbList=Transpose[{bins[[2 ;;]],count/NumItearations}];
ListLinePlot[ProbList]


В результате получаем вот такую картинку. Это гистограмма. В ней каждый столбец имеет свою координату на горизонтальной оси, свою высоту и ширину. Высота столбца обозначает, сколько раз из 100000 тысяч итераций коллекция была закончена за n шагов, причём n в данном случае это и есть координата на горизонтальной оси. Грубо, но в целом верно. А если точнее, то нужно вспомнить про ширину столбца, он тут не просто так. Дело в том, что при построении гистограммы, выбор «адекватной» ширины столбцов является вопросом архиважным и архисложным. Когда же его выбрали, и показали вам готовый результат, то вы должны помнить, что на самом деле, высота столбца обозначает, сколько раз произошли события, которые имеют координату больше левой границы и меньше правой границы столбца. Предположим, что у нас в принципе возможны только целые числа, а ширину столбцов мы по глупости сделаем 0.25. В итоге мы вместо «гладкой» картинки получим «расчёску» из столбцов, как забор с дырками – то есть столбец, то нет, то есть, то нет. Если же мы ширину возьмём очень большой, то можем получить просто один очень широкий столбец – толку от него не будет никакого. Все изгибы и нюансы будут просто отсутствовать.
Сейчас высота столбцов обозначает, сколько раз из всех испытаний коллекция была собрана за определённое количество шагов (открытий жвачек). Чтобы узнать вероятность получения коллекции на определённом шаге, мы должны высоту столбцов поделить на общее количество испытаний, и таким образом, получим численно смоделированный ответ к поставленной задаче о коллекции.
Как уже было упомянуто, после случайно встреченной задачки про траекторию (ссылку смотрите выше), возникла идея, которая помогла не только оптимизировать алгоритм, но в конечном итоге вывести формулу.

Любопытная таблица


Каждый момент процесса собирания коллекции можно описать двумя числами: сколько уникальных элементов и сколько повторов. Вероятность получить уникальный элемент коллекции при следующем получении нового элемента (в новой жвачке получить вкладыш которого ещё не было) не зависит от того, какие именно элементы у вас уже есть, а зависит лишь от того, сколько у вас уникальных элементов и сколько всего элементов в коллекции.

Пусть в какой-то момент есть K уникальных элементов, M повторов, а всего в коллекции N элементов. Стоит уточнить, что под количеством повторов подразумеваются все те элементы, которые останутся у нас, если из всего нашего текущего набора мы уберём ровно по одному уникальному элементу что были. Например, есть 4 яблока, и 3 груши, всего уникальных элементов 2 – это яблоко и груша, а повторов 7 – это 3 яблока и 2 груши. При получении нового элемента, мы можем перейти из текущего состояния (K, M) в одно из двух других состояний. Либо у нас увеличится количество уникальных элементов (K+1, M), либо у нас увеличится количество повторов (K, M+1). Таким образом, мы можем построить таблицу переходов, для любого случая (K, M).

На основе такого подхода, мы можем построить алгоритм для моделирования процесса сбора коллекции. Теперь нам нужно будет на каждом шаге с вероятностью (N –K)/ N переходить либо в клетку (K+1, M) либо c вероятностью K/ N в клетку (K, M+1), до тех пор, пока K
Вот собственно код этого алгоритма. Работает он всё же побыстрее, чем первый вариант. 
SeedRandom[1234];(*"фиксирует"рандом. Когда мы хотим полуить случайную последовательность, то можем каждый раз получать новую, а можем каждый раз получать ту же самую.Если СидРандом задан, то последовательность будет всегда генериться одна и таже.*)
NPosibleElems=40;(*Количество уникальных элементов в коллекции*)
NumItearations=100000;(*Сколько раз будем проводить испытания. Если вычисления проходят медленно - сделайте кол-во интераций меньше.*)
Results=Table[0,{i,1,NumItearations}];(*Массив с результатами, в нём будут содержаться количество полученных элементов к моменту достижения цели. "сколько купили жвачек" прежде чем собрали коллекцию.*)
ProgressIndicator[Dynamic[indic],{1,NumItearations}](*В этом примере мы будем использовать индикатор прогресса. Не проверял её особо на скорость, но вроде не сильно тормозит. Переменная indic в данном случае динамическая. Тоесть изменяя её гдето в одном месте, её изменения отразятся СРАЗУ ЖЕ и в других частях документа. К НАШЕМУ АЛГОРИТМУ ЭТО НЕ ИМЕЕТ ОТНОШЕНИЯ - просто для красоты визуализации. Если не понятно, просто пропустите.*)
For[i=1,i<=NumItearations,i++,(*Начинаем в цикле собирать коллекции.*)
indic=i;(*Обновляем полоску индикатора... точнее переменную которая отвечает за положение полоски, а так как она динамическая, то индикатор сам перерисуется*)
n=0;(*Скольо УНИКАЛЬНЫХ элементов коллекции у нас уже есть*)
m=0;(*Сколько ПОВТОРОВ в коллекции у нас есть. Если у нас есть 2 яблока и 3 груши, то уникальных предметов у нас 2 -это {Яблоко, Груша}. А повторов у нас 3 - это одно ЛИШНЕЕ яблоко и две ЛИШНИХ груши.*)
While[n<NPosibleElems,(*Цикл сбора коллекции. Будем открывать новые жвачки до тех пор пока коллекцию не соберём. По идее его не плохо было бы всё же ограничить разумным числом, а то есть какаято мизерная вероятность что и за сто тысяч милионов жвачек мы коллекцию не соберём - в итоге комп может конкретно тут подвиснуть.*)
r=RandomInteger[{1,NPosibleElems}];(*В отличии от прошлого примера данный рандом это не эмуляция нового элмемента коллекции, а эмуляция вероятности того, что новый полученный элмент уже был у нас или ещё не было.*) 
If[r> n,n+=1,m+=1];(*С вероятность n/NPosibleElems мы увеличиваеи количество повторов, а с вероятностью 1-n/NPosibleElems увеличиваем кол-во уникальных элементов.*)
];
Results[[i]]=n+m;(*Сумма уникальных и повторых элементов, это общее количество элементов которое у нас есть, или же то кол-во шагов (открытий жвачки) которое было сделано прежде чем колекция была собрана*)
];
(*Дальше также рисуем как в прошлом примере.*)
{bins,count}=HistogramList[Results];
HistoList=Transpose[{binsN[[2;;]],count}];
TickL=20;
Show[{Histogram[Results],ListPlot[HistoList,PlotStyle->{Darker[Red],PointSize[Large]}]},Ticks->{Table[i,{i,0,Last[bins],TickL}],Automatic}]
(*Рисуем граффик вероятностей*)
ProbList=Transpose[{bins[[2 ;;]],count/NumItearations}];
ListLinePlot[ProbList]

Теперь разовьём идею дальше. Можно попробовать посчитать, сколько существует вариантов попасть в клетку с фиксированными (K, M). В клетку (K, M) можно попасть либо из клетки (K, M-1) либо из клетки (K-1, M). Кроме случаев, когда у нас либо только один уникальный элемент, либо нет повторов, то есть K=1, M=0, в них можно попасть только единственным из двух способов. Обозначим количество способов попасть в клетку (K, M) как V[K, M]. Из клетки (K, M-1) в клетку (K, M) можно попасть К различными вариантами, потому что получить ещё один повтор можно таким количеством вариантов, сколько уже есть уникальных элементов. Из другой же соседней клетки (K-1, M) в клетку (K, M) можно попасть (N-(K-1)) количеством вариантов, потому что в клетке (K-1, M) уникальных элементов (K-1), и соответственно недостаёт (N-(K-1)) элементов. Вообще же вариантов попасть в клетку (K, M) через клетку (K, M-1) можно V[K, M-1]*K вариантами, то есть произведение количества вариантов попасть в саму (K, M-1) умноженное на количество вариантов попасть из (K, M-1) в (K, M). Аналогично и с вариантами попасть в клетку (K, M) через клетку (K-1, M) получаем V[K-1, M]* (N-(K-1)). Суммарно же попасть в клетку (K, M) можно попасть V[K, M-1]*K+ V[K-1, M]* (N-(K-1)) количеством вариантов. Таким образом, мы получаем саму полезную для нас формулу о количестве способов попадания в клетку (K, M).
V[K, M]=V[K, M-1]*K+ V[K-1, M]* (N-(K-1))

Используя это правило, можно последовательно посчитать количество способов попадания для любой клетки (K, M). То есть это не будет формула которая сразу выдаст значение вариантов для конкретных (K, M), но у нас будет таблица с символьными ответами, а не с численным моделированием. Вот собственно алгоритм. 
KKT=10;
MMT=10;
V=Table[0,{k,1,KKT},{m,1,MMT}];
V[[1,1]]=NN;
For[k=2,k<=KKT,k++,V[[k,1]]=FullSimplify[V[[k-1,1]]*(NN-(k-1))]];
For[m=2,m<=MMT,m++,V[[1,m]]=NN];
For[k=2,k<=KKT,k++,
For[m=2,m<=MMT,m++,
V[[k,m]]=V[[k-1,m]]*(NN-(k-1))+V[[k,m-1]]*k;
];
];
MatrixForm[V]

И вот полученная таблица, не смотря на весь свой огромный размер, обладает замечательной особенностью. Все столбцы таблицы пропорциональны с некоторым числовым коэффициентом первому столбцу. И данные числовые коэффициенты не зависят от количества элементов в коллекции. Если разделить все столбцы этой таблицы на первый столбец, то получим вот такой результат.

Честно говоря, я был крайне озадачен, когда первый раз это получил. Это казалось настолько красивым и невероятным, что у меня просто в голове не укладывалось. Числа эти не зависят от количества элементов в коллекции и зависят только от количества повторов и уникальных элементов, то есть от (K, M). Если понять, как эти числа получаются, то задача будет полностью решена и сводится к весьма простой формуле. Но что это за числа, я не имел, ни малейшего понятия.

Азъ есмь Alpha Wolfram


Представьте, что во время каких-то вычислений, вы сталкиваетесь с некоторым коэффициентом, например 5.01326. Вы знаете, что получили его не с абсолютной точностью, но подумали, а вдруг это число какое-то «красивое» и выражается через известные математические константы, или является корнем какого-то натурального числа, логорифмом, синусом. Ну, или если и не является, то очень близко к нему. Например, с такой потребностью можно столкнуться при анализе чужого кода, со списком констант, но без комментариев. В таком случае меня выручал сайт Wolfram Alpha.
Вот пример ответа на запрос о числе 5.01326. (я загадал корень из 8*Pi)
Я затрудняюсь назвать Wolfram Alpha поисковиком, он нечто большее. Он не просто ищет на просторах инета страницы, которые как-то относятся к тому, что вы ищите. Он часто вычисляет ответ на ваш вопрос сам. Причём вместо «бонуса» рекламы, как делают обычные поисковики, он выдаёт действительно интересные факты, относящиеся к данному вопросу. Не ссылки, а именно сразу факты на странице. Ссылки, правда, тоже конечно выдаёт в конце страницы, но обычно всё, что он выдаст сам, бывает более чем достаточно.
Так же при желании можно получить доступ к базам данным о погоде, каких-то финансовых данных, географии, биологии, химии и прочем. Например вот. Ссылки уже с готовыми запросами
Графики температуры, давления и прочего в Кабуле с 97ого по 99ый годы.
Информация об акциях компании Apple за последние 16 лет
Карта и информация о территории СССР
Основные свойства оксида азота
Помимо ответов на вопросы типа «что такое….?» он может выдавать решения дифференциальных уравнений введенных ему в строку ввода. Или нарисовать график, который вы попросили. То есть не нужно никаких сторонних программ, плагинов и прочего – можно просто решить дифференциальное уравнение и отрисовать график введя его в строку ввода Wolfram Alpha. Но всё же, отмечу, что всё в пределах разумного – если что-то довольно трудоёмкое, то он откажется считать «на халяву», и для сложных задач и быстродействия всё же потребуется Wolfram Mathematica.
В частности можно делать запрос в виде последовательностей чисел, и помимо основных характеристик, данного массива, он может (не всегда правда) выдать предположительный вариант продолжения последовательности. Именно эта его возможность и была использована для выяснения, что же за числа были получены в клетках выше описанной таблицы.

Математический детектив


Те, кто не любят детективы, эту главу могут пропустить и перейти к следующей.
Я начал с того, что брал строки полученного массива W и просто вводил вручную в Wolfram Alpha. Но можно и не копипастить, а прямо из Wolfram Mathematica напрямую обращаться к Wolfram Alpha без браузеров. Причём сразу запрашивать ту часть информации, которая интересует. Вот код, который в цикле запрашивает предположительную формулу введённой последовательности. 
For[i=1,i<=Length[W],i++, 
Print[i,"  ",W[[i]]];
Print[WolframAlpha[ToString[W[[i]]],{{"PossibleSequenceIdentification",1},{"Output"}}]];
Print[""];
];

К сожалению не все запросы были успешно обработаны, причины бывают разными, иногда помогает уменьшить или увеличить размер вводимой последовательности. Но из полученных ответов, после пристального взгляда, можно обнаружить, что последовательности, которые мы вводили, имеют вид a0*0^n+a1*1^n +a2*2^n + a3*3^n +…. Количество слагаемых равно порядковому номеру введённой последовательности. Но коэффициенты an линейно входят в формулу, а значит, их можно легко найти из системы линейных уравнений. Более того если приглядеться, то все слагаемые имеют общий множитель, обратно пропорциональный факториалу номера последовательности, а также, что слагаемые знакопеременные. Поэтому искать слагаемые будем с учётом этих фактов. Систему решаем, разумеется, не вручную, а в Wolfram Mathematica. Вот код для решения. 
TempAr = W;
CoefRes = Table[{}, {i, 1, Length[TempAr]}];
For[k = 1, k <= Length[TempAr], k++,
  An = Table[a[i], {i, 2, k}];
  (*Conds=Table[An[[i]]>0,{i,1,Length[An]}]*)
  F[z_] := (Total[
       Table[(((-1)^(k + 1))*(-1)^(i + 1))*i^z*An[[i - 1]], {i, 2, 
         k}]] + (-1)^(k + 1))/((k - 1)!);
  Eqs = Table[F[i] == TempAr[[k]][[i]], {i, 1, Length[An]}];
  Res = Solve[Eqs, An];
  CoefRes[[k]] = Prepend[(An /. Res)[[1]], 1];
  ue = Table[(-1)^k*(-1)^i, {i, 1, Length[CoefRes[[k]]]}];
  CoefRes[[k]] = CoefRes[[k]]*ue;
  ];
CoefRes // Column

Коэффициенты нашли, но они тоже, не то что бы простые. Повторяем с ними ту же самую процедуру попытки поиска формулы для них. И тут нас ждёт разочарование — Wolfram Alpha в режиме халявы не может распознать эти последовательности. Ну что же — пробуем сами.
Попробуем разложить все эти числа на простые множители и немного помедитируем, созерцая полученное. Такой подход часто бывает полезен, для того чтобы распознать формулу последовательности. 
For[i=1,i<=Length[W],i++, 
Print[FactorInteger[Abs[CoefRes[[i]]]]//Column];
]

Присмотревшись к полученным разложениям, видно, что каждое из чисел в последовательностях делится на свой порядковый номер в определённой степени, причём эта степень растёт с ростом номера последовательности. Присмотревшись ещё внимательнее видно, эта степень равна номеру последовательности минус 2. Ну, хорошо, разделим тогда все числа в наших последовательностях на их порядковые номера в степени номера последовательности минус 2. 
CoefRes2=CoefRes;
For[i=1,i<=Length[CoefRes],i++, 
For[j=1,j<=Length[CoefRes[[i]]],j++, 
CoefRes2[[i]][[j]]=Abs[CoefRes[[i]][[j]]]/j^(i-2);
];
]
CoefRes2

Я не приводил раньше результаты обсчёта алгоритмов, там массивы чисел, и слишком много пришлось бы таблиц вставлять. Да и числа, как я уже говорил не то что бы понятные. Если кто-то хочет на них взглянуть – то, пожалуйста, я для этого код и выложил. Просто прогоните его разок и всё увидите. Он быстро сработает. В этот же раз я приведу результат работы алгоритма, в силу того что числа очень известные.
{{1},{1,1},{1,2,1},{1,3,3,1},{1,4,6,4,1},{1,5,10,10,5,1},{1,6,15,20,15,6,1},{1,7,21,35,35,21,7,1},{1,8,28,56,70,56,28,8,1},{1,9,36,84,126,126,84,36,9,1}}
То, что получилось после деления, если вы помните бином Ньютона и треугольник Паскаля, в Wolfram Alpha засовывать уже не будете. Это как раз получились «Цэ из эн по ка».
Теперь осталось собрать все наши запчасти от разобранной формулы обратно в единое целое. 
FV[KK_,LL_,NN_]:=Sum[((-1)^(n+KK) n^(KK+LL))/(n! (KK-n)!),{n,1,KK}]*NN!/(NN-KK)!/(NN^(KK+LL));


Результат в аналитическом виде получен, и в принципе, все что нужно, можно из него вытащить. Однако, формула довольно громоздкая, а хотелось бы сделать её более компактной. Да и наверняка она должна быть известной, в силу распространенности задачи о коллекции.
Я довольно долго пытался упростить её, либо найти в литературе. В итоге получилось сделать и то и другое после того, когда вместо строк нашей исходной таблицы я отправил на распознавание последовательности в Wolfram Alpha столбцы.

Триста лет тому назад


Если ввести столбцы полученного массива W в Wolfram Alpha, то последовательность будет распознана как числа Стирлинга второго рода (Stirling numbers of second kind). Это довольно известный (как оказалось, хотя я их не помнил/не знал) массив чисел, который подробно описан в различных учебниках по комбинаторике и теории вероятностей. Те кто знаком с числами Стирлинга данную главу могут пропустить и перейти к следующей.
Прочитать про числа Стирлинга можно, например, тут.
А тут вот намного подробнее, но, правда, на английском. Это вообще, пожалуй, один из лучших сайтов, если нужна полная справочная информация о чём-то из математики.
Числа Стирлинга второго рода означают количество способов разбиения множества из N элементов на K частей. Например, множество {1,2,3,4} из четёрёх элементов можно разбить на:
на 4 множества по одному элементу, {{{a}, {b}, {c}, {d}} (способ всего один)
на 3 множества, где в одном будет 2 элемента в оставшихся по одному {{a, b}, {c}, d}}, {{a, c}, {b}, {d}}, {{a, d}, {b}, {c}},{{b, c}, {a}, {d}}, {{b, d}, {a}, {c}}, {{c, d}, {a}, {b}} (способов всего 6)
на 2 множества по 1 и 3 элемента {{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}}, или по 2 элемента каждый {{a, b}, {c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}} (способов всего 7)
на 1 множество из 4 элементов, то есть ничего не разбивая. (способ всего один)
Собственно количество способов разбиений множества на определённое количество частей (но при этом произвольный состав этих частей) и обозначают числа Стирлинга.
Джеймс Стирлинг, шотландский математик, жил примерно 300 лет назад, современник Исаака Ньютона, с которым собственно регулярно переписывался, общался, работал. В честь него и названы числа обозначающие количество способов разбиения множества на n частей.
Формула для получения чисел Стирлинга второго рода выглядит следующим образом.

Но в Wolfram Mathematica они доступны через функцию StirlingS2[SS, NN].

Три строчки


Задача о коллекции из N элементов может быть решена в три строчки. Правда, чтобы это понять, мне понадобилось довольно много времени.
  1. Все элементы коллекции, которые мы последовательно собирали, можно пронумеровать согласно очереди их получения. Эти номера, можно объединить в группы, по повторяемости самих элементов. Число таких групп это числа Стирлинга второго рода.
  2. Эти группы можно представить как места для размещения уникальных элементов коллекции на данный момент. Число вариантов такого размещения равно числу «Размещение без повторений» N элементов по K мест. Следовательно, общее количество вариантов получения K уникальных элементов равно произведению соответствующего числа Стирлинга на количество размещений.
  3. Вероятность собрать коллекцию на S-ом шаге, равна отношению числа возможностей получения K уникальных элементов к числу всех возможных комбинаций, которое равно N^ S.
    Если нас интересует именно собранная коллекция, а не частично собранная коллекция (формула для которой уже приведена была выше), то нужно чтобы количество уникальных элементов в данный момент было равно общему количеству элементов в коллекции.

Таки образом вероятность собрать коллекцию из K элементов за N шагов равна StirlingS2[N,K]*K!/N^K

Две сущности


Те кто знаком с понятиями »: «Распределение дискретной случайной величины» и » и «Функция распределения дискретной случайной величины» данную главу могут пропустить и перейти к следующей.
Пусть мы бросаем игральный кубик. Вероятность того что выпадет заданное конкретное число например 3 или 5 равно 1/6. График вероятности этих событий просто горизонтальная линия, ну или пусть будем звать её «полочка» (похожа ведь). Но очень часто встречается другой вопрос. Какова вероятность, что выпадет число меньше либо равное конкретному заданному числу, например меньше либо равно 2. Тогда для каждого из возможных чисел можно тоже построить график вероятности, но он уже будет в виде «лесенки», а не горизонтальной линией как прошлый раз.
Причём как мы видим, на графике «полочки» нет значений для точек 3.5 или 2.8, просто потому, что кубиком вы их никогда не выкинем. Стоит ли в таком случае для не целых чисел, или для тех, что меньше одного или выше 6 считать вероятность равной нулю или считать неопределенной — вопрос довольно сложный, но пока что мы его будем просто обходить стороной. Что касается «лесенки», то там тоже есть важный момент, который не сложный в понимании, но при этом очень легко его пропустить и сделать в итоге ошибку. Горизонтальная часть каждой ступеньки «имеет на левой границе точку», а вот «справа не имеет». В смысле можно как угодно близко приближаться к впуклому углу ступеньки, но значение нашей функции лесенки в месте где происходят разрывы графика равно значению верхней(следующей) ступеньки. Например, вероятность получить число меньше либо равное 2 на кубике равно 1/3, вероятность получить число не больше 2.5 тоже равно 1/3, вероятность получить число не больше 2.999999999… тоже равно 1/3, а вот вероятность получить не больше 3 равно уже 1/2.


Кубик один и тот же. Вроде и там и там строим график вероятности. Но они разные. Очень часто при изучении тервера возникают проблемы именно из-за путаницы двух этих сущностей. Отчасти это связано с их названиям, которые очень уж похожи. А отчасти с тем, что не совсем понятно, зачем же их ввели две, можно ж было и одной обойтись. Особенно «лесенка» поначалу воспринимается слабо информативной и бессмысленной.
Называются эти две сущности так:
  1. та что мы обозвали «ПОЛОЧКА»: «Закон распределения дискретной случайной величины» или даже просто (без слова закон) «Распределение дискретной случайно величины» или ещё короче «Распределение вероятностей» или «Таблица распределения».
  2. та что мы обозвали «ЛЕСЕНКА»: «Функция распределения дискретной случайной величины».

Вот если кому-то на слух очевидно и понятно разительное различие между «функция» и «закон» — съешьте печеньку. Особенно нехорошо получается, когда при разговоре, «функцию распределения» сокращают просто до «распределения», и всё, привет, различия просто нету. Обидно, что бывает непонимание важных вещей, как оказывается, только из-за лингвистических косяков, а не из-за того что вы не способны понять смысл. Преподы по терверу тут вообще проблемы не видят, а студенты мучаются.
Понятно, что «полочка» и «лесенка» не всегда таковыми получаются. Например, если бы мы рисовали график не для значений кубика, а скажем для роста людей, то тогда график был бы уже не полочкой (люди не все же одинакового роста), а скорее каким-то «куполом». Максимум его был бы где-то наверно на 160см. а вот вероятность роста 200см так же как и 140см была бы значительно ниже. Лесенка, правда, в дискретном случае чаще всего именно «лесенка», (хитрые редкие случаи не рассматриваем сейчас, в силу их непрактичности) но всё же, это обычно лесенка довольно неравномерная.
Лучше всего эти сущности воспринимать в голове абстрактно, без названия. Но в разговоре же надо что-то конкретное, а не абстрактное применять – поэтому я обычно (хоть конечно терверщики меня за это закопают живьём) применяю следующие понятия. «Интеграл» для обозначения сущности «лесенки», и «плотность» для обозначения сущности «полочки». Такие определения довольно хорошо подходят по смыслу. Вероятность того, что на кубике выпадет число меньшее либо равное трём, означает сумму вероятностей того что выпадет 1 или выпадет 2 или выпадет 3. То есть сумма вероятностей всех возможных вариантов меньше 3 как раз и даст значения для графика «интеграла» — «лесенки» в точке 3. Интеграл это, по сути, и есть сумма, отсюда и используемое мной обозначение. Плотность же, если сказать просто и грубо это масса одного маленького кусочка от всего объёма. В случае, когда мы говорим о вероятности выпадения строго фиксированного одного значения, мы как вы вычленяем из всего множества возможных значений только его, одинокого, и говорим о нём. Отсюда и второе используемое обозначение.
Теперь остаётся вопрос – зачем нужно отдельно вводить такую сущность как график «интеграла»-вероятности. Для кубика это действительно не очень наглядно. Попробуем другой пример. Пусть у нас есть сто человек, каждый из них получает зарплату, которая зависит от стажа, различных заслуг в работе, квалификации и т д. В такой ситуации у всех зарплаты будут хоть немного да отличаться. Один получает 30т.р. другой 32, пять человек человек по 35, кто-то 36, а ровно 34 никто не получает, ну и так далее. А теперь представьте, что у вас есть график «плотности»-вероятности, то есть по нему вы можете сказать, что вероятность получать ровно 32т.р равна 1/100, а вероятность получать 34 т.р. вообще не пойми что (у нас же 100 человек, и только один получает 32т.р, а 34 никто и не получает). Ну и какие полезные выводы можно сделать из знания о вероятности 1/100 для 32т.р или из факта о том, что для 34т.р просто нет данных? По сути никаких. А теперь представьте, что у вас есть график «интеграла»-вероятности. По нему вы можете сказать какова вероятность получать меньше 30 рублей, и это будет какой-то ощутимый процент. А если например вероятность меньше 10т.р окажется ноль, то это значит что никто не получает меньше 10 т.р, что гораздо информативнее чем тот факт что зарплаты в 34 234р. 20к. нет ни у кого.
Конечно, можно ещё придумать графики типа «вероятность, что больше чем что-то и меньше чем что-то», тогда сумма будет идти не по всем значениям меньшим, чем заданное, а от одного значения до какого-то другого. Но это уже конкретные примеры, которые для каждого конкретного случая свои. А вот графики «вероятности-интеграла» и «вероятности-плотности» широко используются всеми, поэтому выделены в две отдельные важные сущности.
Понимание смысла этих двух сущностей, а также понимание уместности их применения нужны для того, чтобы осмыслить те формулы для задачи о коллекции, что мы получили, а также те данные, что мы получили в численном моделировании. Вот как выглядит график вероятности собрать коллекцию за определённое количество шагов в зависимости от самого количества шагов, а так же ещё раз напомню, как выглядят полученные моделированием данные. Графики сильно различаются.


Разница объясняется тем, что график полученный моделированием это «плотность-вероятности», а тот, что по формуле это «интеграл-вероятности». Формула даёт значение вероятности собрать коллекцию за N шагов. Не ровно за N! А просто – за N. То есть мы могли коллекцию собрать почти сразу, а потом бы получали уже только повторные элементы до тех пор, пока бы не сделали N шагов, и такой вот странный случай мы всё равно учитывали в нашей вероятности. Чтобы не было путаницы или недопонимания, то про нашу формулу правильнее говорить «Вероятность собрать коллекцию за N или меньше шагов» или «… за не более чем N шагов». А про график полученный моделированием нужно говорить, «вероятность получить коллекцию именно на N-ом шаге», то есть, когда на (N-1)-ом коллекция ещё не была собрана, а вот на N-ом шаге она собралась.
Чтобы получить формулу для «плотности-вероятности» из формулы для «интеграла-вероятности», нужно из вероятности собрать коллекцию за N или меньше шагов вычесть вероятность собрать коллекцию за (N-1) или меньше шагов. Полученная разность это и будет вероятность собрать коллекцию именно на N-ом шаге, а не раньше. Таки образом вероятность собрать коллекцию из K элементов именно на N-ом шаге равна StirlingS2[N,K]*K!/K^N- StirlingS2[N-1,K]*K!/K^(N-1)
Стоит заметить, что эту формулу можно и сократить. Дело в том, что когда осталось собрать только один элемент, сделать это можно только одним единственным способом. А значит, вероятность собрать коллекцию именно на N-ом шаге равна отношению количества возможностей собрать её за (N -1) шагов к общему количеству всевозможных набор элементов на N-ом шаге. В итоге формула сокращается до вида StirlingS2[N-1,K-1]*K!/K^N
На следующем графике, формула для сбора коллекции именно на N-ом шаге изображена сплошной линией, а красными точками обозначены результаты моделирования. Как можно видеть, они довольно хорошо совпадают.

Средняя температура пациентов и средняя зарплата врачей


То, что сейчас будет описано, крайне важно и полезно знать в повседневной жизни. Те же, кто знаком с понятием среднего, мат ожидания и медианы, могут пропустить эту главу и перейти к следующей.
Часто возникает такой вопрос, сколько «в среднем» нужно шагов, чтобы собрать коллекцию? Вроде бы вопрос простой, естественный, часто встречающийся, но есть одна проблема. Нужно уточнить, что же именно мы хотим узнать, когда говорим о «среднем».
Представим такую ситуацию, продавец, каждый день получает прибыль в размере одной, двух, трёх, и так далее до 6 тысяч рублей. Как будто его дневная прибыль зависит от того какое число выпало на брошенном кубике. И вот после месяца работы в таком режиме, он решил посчитать среднее. Вычислил сумму прибыли за все тридцать дней и разделил на количество дней. Полученное число есть среднее арифметическое значение прибыли за все 30 дней. Число это довольно информативно, но у него есть одно существенное неудобство-недостаток. Дело в том, что его можно посчитать, только если вы уже имеете данные о некоторых произошедших событиях. Если он захочет узнать среднее значение прибыли за будущий месяц, то узнать это, используя методику подсчёта среднего арифметического, сейчас, в данный момент не сможет – у него ещё нет данных за следующий месяц, которые можно было бы сложить и разделить. Но, работа его в следующем месяце, вроде, будет той же, катаклизмов не предвидится, перебоев с поставками товара и падения спроса он тоже не ожидает. Продавец ожидает, что в следующем месяце свойства случайной величины не изменятся. Ну а раз так, то можно предположить, что и среднее значение, которое он сможет посчитать через месяц, тоже будет не сильно отличаться от того среднего, что было получено в прошлом месяце. Вопрос о том, что значит «не сильно», мы пока пропустим, он довольно сложный и не слишком сейчас актуальный. Давайте лучше попробуем найти способ, как спрогнозировать примерное среднее значение прибыли в следующем месяце.
Когда мы считали среднее арифметическое, мы суммировали все полученные в ходе наблюдений значения случайно величины (зарплаты) и делили на общее количество. Давайте посмотрим ещё раз более внимательно на весь этот процесс. Давайте все полученные данные запишем в таблицу.

Единичка выпала k1 число раз, двойка k2 раза. (У нас там в тысячах шёл подсчёт, но для краткости нули не будем писать). После этого мы нашли сумму всего, что выпадало на кубике (ну или как там было – зарабатывали за день). Слагаемыми этой суммы были как раз числа 1 2 3 4 5 6, при ‘том каждое из них соответственно k1 k2 k3 k4 k5 k6 раз. А это значит, что сумма эта равна S=k1*1+k2*3+k3*3+k4*4+k5*5+k6*6. Общее же количество слагаемых в этой сумме равнялось N=k1+k2+k3+k4+k5+k6. Ведь k[x] обозначает, сколько раз выпадало каждое из значений, а всего их 6. После чего мы разделили S на N, что равно S/N=1*(k1/N) +2*(k2/N)+ 3*(k3/N)+ 4*(k4/N)+ 5*(k5/N)+ 6*(k6/N). Но если приглядеться, то k1/N это очень сильно напоминает вероятность выпадения единицы, соответственно k2/N вероятность что выпадет двойка и т д. Действительно, мы, же делим количество числа возникновения события к общему количеству событий. Но процесс выпадения случайных чисел, сам закон распределения случайно величины не менялся в прошлом месяце и вроде не планировался поменяться в следующем. А значит и отношения типа (k1/N) не зависят от времени, а зависят только от свойств случайной величины. И если однажды мы их можем получить из полученных опытным путём наблюдений, (ну и разумеется подсчитанных и поделенных), то сможем использовать и в дальнейшем. Более того получается что S/N теперь тоже зависит только от свойств случайно величины и не зависит от времени, в ней же теперь остались только слагаемые вида ЧТО_ВЫПАЛО * ВЕРОЯТНОСТЬ_ВЫПАДЕНИЯ_ТОГО_ЧТО_ВЫПАЛО.
Давайте чтобы много слов не писать, обозначим все возможные варианты ТОГО_ЧТО_ВЫПАЛО через X(i). («икс итое – всмысле как пятое, шестое, энтое, катое, итое»)Всего у нас X(i) шесть штук, так как наша случайная величина принимает только одно из шести значений. При этом Х(1)=1, Х(2)=2 ну и так далее. А ВЕРОЯТНОСТЬ_ВЫПАДЕНИЯ_ТОГО_ЧТО_ВЫПАЛО через P(i). И каждому значению случайно величины X(i) соответствует своя вероятность выпадения P(i). В таких обозначениях величину S/N записать можно проще S/N=СуммаВсех[P(i)*X(i)] (для всех i). У нас всего 6 штук получится слагаемвых, для наглядности выпишу их.
S/N= P(1)*X(1) + P(2)*X(2)+ P(3)*X(3)+ P(4)*X(4)+ P(5)*X(5)+ P(6)*X(6)
Так вот. Величину СуммаВсех[P(i)*X(i)](для всех i) называют математическим ожиданием. В том смысле, что это ещё не полученное, но ожидаемое после математического анализа, среднее значение случайной величины. Для кубика мат.ожидание равно 1*(1/6)+2*(1/6)+3*(1/6)+4*(1/6)+5*(1/6)+6*(1/6)=21/6=3.5. Для кубика, у которого грани только целые числа, понять, что такое 3.5 при первом знакомстве с этим фактом обычно бывает не просто – грани 3.5 ведь нету! А мат ожидание вовсе и не должно быть равно одному из значений случайной величины. Для нашего продавца, который получает в среднем за день 3500р прибыли, всё довольно понятно.
А теперь представьте, что вы кинули кубик 10 раз, и все 10 раз на нём выпала цифра 6. Если посчитать среднее арифметическое значение, то оно будет тоже равно 6(ну очевидно же). А мы говорим, что мат. ожидание 3.5, и что именно 3.5 должно быть средним значением, а ни как не 6. Вот тут то мы и видим, что среднее арифметическое значение, полученное из наблюдаемых данных может отличаться от мат.ожидания. И что вообще-то, мат.ожидание это ОЖИДАЕМОЕ среднее, а не то что порой может случиться в реальности. Ожидаемое, близкое к реальности, но не равное реальному значения прям уж точно-точно. Однако, существует теорема («Закон больших чисел»), которая говорит, что чем больше раз мы кинем кубик, и за все эти разы посчитаем среднее арифметическое, тем меньше будет различие между мат.ожиданием и средним значением. А учитывая, что в большинстве случаев у нас нет возможности проводить длинные эксперименты, да и вообще, хочется без всяких экспериментов предсказывать, что же там получится «в среднем», то нам остаётся довольствоваться только использованием мат.ожидания, как некоторой оценкой, предсказанием с какой-то погрешностью.
С одной стороны среднее значение довольно информативно при описании некоторых случайных процессов, но иногда, среднее значение просто бессмысленно, нелогично, а его использование противоречит здравому смыслу и реальности. И дело тут не в самом среднем значении, а в здравомыслии тех, кто его считает.
Главврач одной из больниц, любил в отчётах писать следующую формулировку: «Средняя температура тела пациентов составляет 36.6 градусов, что полностью соответствует норме». Он не врал, а честно считал температуру всех пациентов, и тех, у кого был жар 40 градусов, и тех, кто умер и остыл до комнатной температуры. В среднем получалось 36.6. Гораздо более информативно было бы нарисовать график распределения температуры больных, посмотрев на который, можно было бы оценить, сколько людей ещё живы, и у скольких из них температура выше нормы, а значит нужно бросить все силы на их спасение. Пример, конечно, анекдотический, но яркий, про то, что считать среднее значение иногда бессмысленно.
Ещё один пример использования среднего значения, уже даже не столько бессмысленный, сколько вредный, и вводящий людей в заблуждение. Часто в СМИ можно услышать упоминание про среднюю зарплату в такой-то отрасли. График распределения зарплат обычно никто не показывает, то ли лень печатать, то ли лень у статистов его попросить. А я вам покажу (выдуманное конечно, но очень близкое к реальности).

Вот такое распределение: 50 рабочих получает примерно по 20т.р. начальник 200, и его четыре зама по 150т.р. СМИ честно пишут, что среднее значение зарплаты на этом предприятии составляет 32 236р и 40 копеек. Рабочие, конечно, очень сильно удивляются, когда слышат, что именно такую зарплату они в среднем получают. Среднее значение именно такое. Только оно в полтора раза выше, чем зарплата большей части сотрудников. И вот никто же нигде никого не обманул. С другой стороны, показывать график, было бы правильнее, но гораздо дольше. А графики бывают и довольно сложные, так сразу и не всякий поймет, что же на нём такое изображено. Да даже в нашей задаче о коллекции я больше чем уверен, что далеко не все люди захотят разглядывать, или тем более строить графики сами. Скорее они захотят услышать то самое «среднее» количество элементов для сбора коллекции. Одно число как-то легче осознать, чем распределение.
Есть ещё одно «число», которое коротко, но порой более информативно описывает закон распределения, чем мат.ожидание. Называется оно медианой (нет, это не та самая медиана из треугольника, просто названия похожи).
В предыдущем примере про зарплаты можно задать такой вопрос – не больше какой суммы получают 50% работников предприятия. Вот та самая сумма, которая будет ответом на этот вопрос и называется медианой. Однако медиана существует не всегда, но есть какое-то ближайшее к ней значение. Этот нюанс не играет особой роли, ну нельзя получить значение строго для 50%, но ближайшее, то всегда можно. В данном примере можно сказать, что 61.8% сотрудников получают зарплату не больше 21т.р. Более того, можно сказать что, 89% процентов сотрудников получают зарплату не больше 25т.р. Данное число будет называться уже не медианой, а квантилем(89%). Вообще-то медиана это тоже квантиль, но из-за частого использования и потому что она именно 50% процентов, ей дали своё собственно имя. Согласитесь, фраза «89% сотрудников получает зарплату не больше 25 т.р.» звучит гораздо более информативно, чем «средняя зарплата 32 т.р». В идеале конечно лучше и то и то говорить, не слишком уж это долго или сложно сказать. Правда слушатели могут с непривычки и не понять, что ж им сказали то такое.
Особо вдумчивые наверно спросят, а какие именно 50% мы будем брать, а если в эти самые 50% войдёт начальник с замом, то опять ерунда получится. Да, получится, поэтому нужно, сначала всех отсортировать по возрастанию, и считать проценты от минимума к максимуму. Я этот момент пропустил в описании закона и функции распределения, но они всегда строятся именно что по возрастанию.
На практике же, квантили, или даже медиану посчитать бывает довольно сложно. Для медианы надо решать уравнение вида F(x)=0.5, а обратную функцию далеко не от каждого распределения легко посчитать, да и не всегда она существует, а значит надо искать ближайшее. В итоге мы получим уже не уравнение, а неравенство, а если нам потом квантили по разным случаям (по разным предприятиям или месяцам) нужно записать и сравнить, а они у нас будут от разных процентов, то это будет неудобно.
Для задачи о коллекции я, кстати, не знаю, как аналитически посчитать квантиль, но мы получим его численным решением.

Там, где прямо не пролезем, мы пройдём бочком


В задаче о коллекции, хотелось бы узнать, а сколько же в среднем коллекционеры делают шагов (открывают жвачек) прежде чем соберут коллекцию. Можно воспользоваться формулой для мат.ожидания и использовать закон распределения вероятности (тот что «плотность») который был получен нами ранее. Но надо сказать посчитать такую сумму мне не удалось – довольно сложная всё же формула, и как её свернуть не понятно.
Раз не получается решить «в лоб», будем пытаться хоть как-то. Поможет нам в этом одно из свойство мат.ожидания. Приведу его без доказательства, которое короткое и не сложное и может быть найдено в любом учебнике по терверу.
Мат ожидание от суммы двух независимых случайных величин равно сумме мат ожиданий от каждой из этих величин.
Например у кубика мат.ожидание 3.5. А каково мат.ожидание суммы чисел на двух одновременно брошенных кубиках. По выше описанному правилу, получаем ответ 7.
Пусть в какой-то момент мы имеем K уникальных элементов, а всего в коллекции N элементов. Вероятность получить ещё один уникальный элемент равна (N-K)/N, а вероятность получить очередной повтор равна. K/N. В такой ситуации вероятность получить уникальный элемент ровно за M шагов равна (N-K)/N*( K/N)^(M-1), то есть это вероятность получить уникальный элемент при условии что перед этим мы получали только повторы. Для подсчёта среднего значения шагов, которое нужно сделать, чтобы получить новый уникальный элемент воспользуемся формулой для мат.ожидания. Она кстати не сложно считается и вручную, но вот код для подсчёта в математике. 
Sum[i*(n-k)/n*(k/n)^(i-1),{i,1,Infinity},Assumptions->{k/n<1}]

В результате получаем, что если у нас уже было K уникальных элементов, то в среднем нужно сделать N/(N-K) шагов (открыть жвачек), чтобы получить новый элемент.
Среднее значение полученных элементов(всех открытых жвачек) для сбора всей коллекции равно сумме средних значений кол-ва шагов, которое было сделано между получениями уникальных элементов, которые равны N/(N-K). Например, для того чтобы получить первый уникальный элемент нужно N/(N-0)=1 шаг(открытие жвачки), для того чтобы получить последний уникальный элемент, нужно в среднем N/(N-(N-1))=N шагов, для предпоследнего N/(N-(N-2))= N/2 шагов, для пред-предпоследнего N/(N-(N-3))= N/3 шагов и т д. В итоге мы получим сумму вот такого вида N+ N/2+ N/3+ N/4+…+ N/(N-2)+ N/(N-1)+N/N. Которую можно записать в более простом виде: N*(1+1/2+1/3+1/4+…+1/N).
Это и есть ответ на вопрос, сколько в среднем нужно получить элементов, чтобы собрать коллекцию.

Wiki-больство какое-то


На русскую википедию даже не пытайтесь заходить. Всё, что касается формул, теорем и чего-то мало-мальски научного на русской википедии смотреть вредно! Статьи скудные, и написаны таким языком, что изучать что-то по ним просто не реально. Такое ощущение, что выдрав из середины довольно серьёзных книг куски определений, написанных с использованием самых неочевидных символов, авторы статей википедии просто копипастят их, без попыток объяснения сути вопроса или хотя бы смысла используемых обозначений. И не редко с существенными смысловыми ошибками!
У большинства пользователей уже сложилось мнение, что на википедии всё написано довольно просто, а раз так, то если уж на википедии непонятно, то значит вопрос чрезвычайно сложный и лучше про него забыть. Прям антиучебник какой-то – вместо того чтобы заинтересовать и просветить, отталкивает от изучения напрочь, либо вводит в заблуждение.
Кстати в процессе поиска вопросов связанных с темой данной статьи меня занесло на страницу википедии посвященную Джеймсу Стирлингу.
Он жил 300 лет назад, и то изображение, которое прикреплено к странице, вызвало у меня подозрение из-за качества картинки и внешнего вида изображенного мужчины. На страницах о Джеймсе Стирлинге на других языках это изображение было не везде. В большинстве случаев его не было, но оно присутствовало на страницах на словацком, армянском, венгерском, иврите и русском языках. Ссылка же на изображение давала весьма интересный результат.
Оказывается, это фото Густава Бергмана – философа 20-ого века. По крайней мере, на официальном сайте Университета Айовы так утверждается.
Когда-то википедия содержала действительно хорошие, надёжные статьи, но всё меняется. И русская википедия продолжает меняться в худшую сторону.
Но справедливости ради, отмечу, что английские страницы википедии довольно часто написаны хорошо.

Результаты


Формулы, которые могут быть записаны с использованием чисел Стирлинга второго рода, будут записаны в двух вариантах.
В силу того что буквы N и K зарезервированы в Wolfram Mathematica, используются обозначения вида NN. Это означает один символ, а не произведение двух символов.
Во всех формулах NN обозначает количество элементов в коллекции, KK – количество уникальных элементов, LL – повторы. Иногда будет встречаться ММ – оно означает все элементы, которые имеются в данный момент (то, что сейчас есть у коллекционера). Да, ММ=KK+LL, и введение этого обозначении кажется избыточным, но оно бывает удобным при описании формулы.
Некоторые формулы идут в двух вариантах с применением StirlingS2 и в общем виде. Но эти 2 варианта полностью одинаковы.
  1. Самая общая формула, из которой можно получить все остальные.
    Вероятность, что среди MM элементов будет KK уникальных и LL повторов. (ММ = KK+LL)
    Код для Wolfram Mathematica 
    FV[KK_,LL_,NN_]:=Sum[((-1)^(n+KK) n^(KK+LL))/(n! (KK-n)!),{n,1,KK}]*NN!/(NN-KK)!/(NN^(KK+LL));
FVs2[KK_,LL_,NN_]:=StirlingS2[KK+LL,KK]*NN!/(NN-KK)!/(NN^(KK+LL));


  2. Вероятность, что именно на MM-ом «шаге» будет получено KK уникальных и LL повторов. (ММ = KK+LL)
    Код для Wolfram Mathematica 
    TV[KK_,LL_,NN_]:=Sum[((-1)^(n+KK-1) n^(KK-1+LL))/(n! (KK-1-n)!),{n,1,KK-1}]*NN!/(NN-KK+1)!/(NN^(KK+LL));
TVs2[KK_,LL_,NN_]:=StirlingS2[KK+LL-1,KK-1]*NN!/(NN-KK+1)!/(NN^(KK+LL));

  3. Ответ на основной вопрос задачи о коллекции. Вероятность, собрать коллекцию, купив SS жвачек. (Не важно, в какой момент она будет собрана.)
    Код для Wolfram Mathematica 
    FCompleteNN[SS_,NN_]:=If[SS<NN,0,Sum[((-1)^(n+NN) n^SS)/(n! (NN-n)!),{n,1,NN}]*NN!/(NN^SS)];
FCompleteNNs2[SS_,NN_]:=If[SS<NN,0,StirlingS2[SS,NN]*NN!/(NN^SS)];


    Важно!Те, у кого нет возможности воспользоваться Wolfram Mathematia или иными способами посчитать эти довольно трудно считаемые формулы, могут воспользоваться сайтом Wolfram Alpha.Вот ссылка с введенной уже формулой, нужно только изменить параметр N под ваши нужды.
  4. Вероятность, собрать коллекцию, купив именно SS жвачек. (последний элемнт коллекции будет содержаться именно в последней, SS-ой жвачке).
    Код для Wolfram Mathematica 
    TCompleteNN[SS_,NN_]:=If[SS<NN,0,Sum[((-1)^(n+NN-1) n^(SS-1))/(n! (NN-1-n)!),{n,1,NN-1}]*NN!/(NN^SS)];
TCompleteNNs2[SS_,NN_]:=If[SS<NN,0,StirlingS2[SS-1,NN-1]*NN!/(NN^SS)];

  5. Формулы для вычисления:
    среднего количества жвачек необходимых для сбора полной коллекции, максимума распределения вероятности собрать коллекцию, и медианы.
    Код для Wolfram Mathematica 
    MeanFCompleteNN[NN_]:=Sum[NN*(1/k),{k,1,NN}];

MaxTCompleteNN[NN_]:=
Module[{SSm=IntegerPart[MeanFCompleteNN[NN]-(3+0.5777490650280465*NN)] ,NNm=NN,TVOld=0,TVNew=0},
If[SSm<NNm,SSm=NNm];
TVOld=TV[NNm,SSm-NNm,NNm];
TVNew=TV[NNm,SSm-NNm+1,NNm];
While[(TVNew-TVOld)>0,
SSm=SSm+1;
TVOld=TVNew;
TVNew=TV[NNm,SSm-NNm+1,NNm];
];
SSm
];

MedianaFCompleteNN[NN_]:=
Module[{SSm=IntegerPart[MeanFCompleteNN[NN]-(3+0.2116249898999874*NN)],NNm=NN},
If[SSm<NNm,SSm=NNm];
While[FV[NNm,SSm+1-NNm,NNm]<0.5,
SSm=SSm+1;
];
SSm
];

  6. Упрощенные формулы (погрешность ±2 элемента для коллекций с количеством элментов не более 1000) для вычисления
    среднего количества жвачек необходимых для сбора полной коллекции, максимума распределения вероятности и медианы

  7. Очень простая в использовании формула для вычисления числа элементов, имея которое, вероятность собрать коллекцию чуть больше 50%.

В игре ArcheAge в труднодоступных местах на западном материке можно найти «Сумку путешественника», в которой помимо прочего будут лежать страницы из дневника Эрика. Если собрать все 80 уникальных страниц, то можно восстановить из них полный дневник, и в награду получить титул, дающий обладателю способность при падении получать меньше повреждения. Используя полученные формулы, можно сказать, что в среднем игроку нужно найти 397 сумки, чтобы самостоятельно собрать весь дневник. Так же можно сказать, что подобрав 400 сумок, вероятность собрать все страницы составляет 58.7%.

День рождения и банка плесени


Иногда, а может даже и часто, люди довольно беспечно полагаются на свою интуицию, не уделяя должного времени на математический анализ вопросов. Предлагаю вам (а потом можете и вы предложить вашим знакомым) ответить на два вопроса. Попробуйте дать на них ответ, полагаясь лишь на ваши «внутренние ощущения» на вашу интуицию.
Первый вопрос такой. В классе 23 ученика. Какова вероятность того, что хоть у кого-нибудь из них дни рождения совпадут?
Второй вопрос про плесень. В банку с питательным раствором залетела одна клетка плесени, и через время t поделилась на две. После чего, каждые из этих двух клеток снова поделились через время t. Через 1 час, банка была заполнена клетками плесени ровно наполовину. Через какое время банка заполнится полностью?
Погодите, не читайте дальше, попробуйте всё же выдать хоть какой-то ответ, представите что если вы правильно ответите – получите 1000р, а если не правильно то 100р, а если за минуту не ответите, то ничего не получите. Это просто для стимула, а то сейчас подумаете, что задачка с подвохом, что тут «думать надо». А внимательно анализировать люди обычно начинают только тогда, когда начинают подозревать подвох. Что, конечно, хорошо. Но хорошо бы ещё на интуицию не полагаться и в остальных случаях. Однако сейчас именно что ваша проверка вашей интуиции. Ответили?
Ответ на вопрос про дни рождения в одну строчку получается из выведенной ранее формулы про коллекции. Все дни в году — это количество элементов в коллекции, 23 человека — это текущее количество элементов которое у вас есть, повторов — 0. Вероятность того, что хотя бы у двух людей дни рождения совпадают, равна единица минус вероятность того что дни рождения не совпадают ни у кого. А в терминах вкладышей и жвачек, это значит, 23 уникальных элемента, 0 повторов, и 365 элементов содержит вся коллекция. Получаем что вероятность совпадения дней рождения хотя бы у двух из 23 человек равна
1 — FV[23,0,365]= 0.507297 = примерно 50%
То есть, в вашем классе, у кого-то дни рождения совпадали с довольно большой вероятностью. У нас в классе, кстати, совпадал именно мой день рождения с одним из одноклассников. Как показывает практика, для большинства людей вне зависимости от рода деятельности такая большая вероятность довольно неожиданна. Я например был очень удивлён, узнав ответ. Но правда потом порадовался, что формула про коллекцию очень хорошо тут работает.
Ответ на вопрос про плесень, предлагаю найти вам самостоятельно.

Выводы


Интуиция, азарт, эмоции без всего этого жить было бы довольно скучно. Но, тем не менее, это самые слабые места человека. И именно по этим слабым местам активно бьют мошенники, рекламщики, пиарщики, маркетологи, много кто. Математический анализ получаемой информации и собственных планов может быть либо отличной защитой, либо мощным оружием. Как его применить – решать вам и вашей совести. Главное, вырабатывайте привычку математического анализа получаемой информации в любых ситуациях, от похода в магазин, чтения новостей до планирования тактики и стратегии во время компьютерных игр. Особенно, во время игр.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

на
Ярлыки: ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)