В этом видео мы рассмотрим более сложные задания вероятностных распределений. Давайте посмотрим на такую задачу. Пусть у нас есть случайная перестановка чисел 1, 2 и 3. И она выбирается следующим образом: сначала мы берем одно из трех чисел случайно и равновероятно и ставим на первую позицию. Затем у нас остается два числа, мы берем одно из них случайно и равновероятно и ставим на вторую позицию. Затем мы берем оставшееся число и ставим на третью позицию. Какова вероятность того, что на второй позиции стоит число два? Давайте разбираться. Прежде чем решать такую задачу, нам нужно понять, какое у нас, собственно, вероятностное распределение. И здесь распределение описано в виде процесса. С таким мы раньше не сталкивались, и вообще надо как-то понять, что с этим делать. Стандартный подход здесь такой: мы начинаем сверху и мы рисуем такую вершину. Дальше для первого шага мы проводим три стрелки из этой вершины, для каждого из трех вариантов действий на первом шаге. Мы можем написать либо число один, либо число два, либо число три, и мы проводим стрелки в вершины 1, 2 и 3. На стрелках мы подписываем вероятности, с которыми это происходит. Тут у нас мы выбираем число равновероятное: исходов три, поэтому везде вероятности по одной трети. Хорошо. Дальше мы рисуем из новых вершин стрелки для второго шага. И из каждой вершины здесь будет две стрелки, потому что в каждом случае мы должны выбрать одно из двух оставшихся чисел. Например, для числа один, для вершины один, мы рисуем две стрелки в новые вершины 12 и 13. Это то, что получается у нас, то, что у нас может получиться после второго шага. Опять же, мы подписываем тут вероятности, опять же, мы выбираем число здесь равновероятно из двух вариантов, и поэтому вероятности здесь будут одна вторая и там и там. И, наконец, у нас есть третий шаг в нашем процессе. На нем, просто, на самом деле, мы выбираем оставшееся число однозначно, пишем его в последовательность нашу, и, собственно, все заканчивается. Вот мы из каждой вершины на предыдущем уровне провели по одному ребру в вершину нижнего уровня, и там у нас уже получились последовательности длины три, вот те самые перестановки. Вероятности здесь нужно подписать на ребрах один, просто потому, что у нас всего одна возможность, но и она происходит с вероятностью один. Хорошо, теперь исходами в нашем распределении в таком виде называются вершины внизу, внизу вот этой вот картинки. Как же посчитать вероятность каждого исхода? Надо просто перемножить вероятности на ребрах, ведущих в этот исход. Для каждого исхода здесь это одно и то же, например, возьмем самый левый исход, и тогда на ребрах, ведущих сверху вниз, у нас написано одна треть, одна вторая и единица, надо эти вероятности перемножить — и получится одна шестая, вероятность каждого исхода здесь одна шестая. Такая картинка, такая диаграмма, называется деревом событий. Число-дерево здесь возникло не случайно, мы обсудим деревья чуть позже в курсе графов, но пока для нас вот эта картинка — это дерево событий. Давайте теперь вспомним нашу задачу, мы разобрались, что у нас за распределение, надо вспомнить, что от нас, собственно, просили. Нас спрашивали, какова вероятность того, что на второй позиции стоит число два? Давайте смотреть. У нас шесть исходов, вероятность каждого исхода — одна шестая, и давайте посмотрим, сколько есть исходов, в которых число два стоит на второй позиции. Их ровно два: 123 и 321. То есть если число два стоит на второй позиции, то осталось только, можно только переставлять числа один и три, есть два способа это сделать. Поэтому у нас вероятность каждого исхода — одна шестая. Исходов в событиях два, поэтому вероятность события будет две шестых, то есть одна треть. Хорошо, на самом деле таким же способом можно задавать и неравновероятное распределение. Например, мы могли бы нарисовать такую же картинку, но поменять вероятности на ребрах. Например, с самого верха, с самого начала мы могли сказать, что у нас число три пишется с вероятностью одна вторая, первым, а оставшиеся числа — с вероятностями одна четверть. А дальше тоже могли быть какие-то сложные распределения. Например, если мы написали число один, то второе число выбирается так: с вероятностью одна треть — это два, а с вероятностью две трети — это три. Или, например, если мы написали число три, то там из двух чисел одно выбирается равновероятно, каждое один и два выбирается с вероятностью одна вторая. А на последнем уровне у нас там неизбежно единицы будут, ничего другого мы там написать не можем. То есть таким образом можно задавать и неравновероятное распределение, и вероятности, исходы здесь те же самые, то есть исходы — это вершины, которые получились внизу, и вероятность исходов определяется аналогично, надо просто перемножить, для каждого исхода надо просто перемножить все ребра, ведущие в этот исход. Например, для исхода 123, который слева, вероятность будет одна четверть умножить на одну треть, то есть, одна двенадцатая. А, например, для исхода 231 у нас вероятности будут: одна четверть в начале, а потом три четверти. То есть, надо перемножить, получается три шестнадцатых. То есть здесь вероятности исходов могут быть уже разными, и так можно задавать разные неравновероятные распределения. Хорошо, но как подобные вот схемы вообще могут возникнуть на практике? Например, следующим образом. Например, так: у нас могут быть данные, и мы хотим с ними что-то делать, и мы делаем следующий процесс. Мы выбираем объект в наших данных, а дальше мы переходим к случайному соседнему объекту. То есть у нас в наших данных есть какое-то понятие соседнего объекта. Мы рассматриваем все соседние объекты, и по какому-то принципу, по какому-то распределению, выбираем случайного соседа у нашего выбранного объекта. Дальше мы попали в новый объект, и мы можем повторить процедуру — мы можем снова перейти к случайному соседу нового объекта. И так можем повторить несколько раз, то есть мы можем несколько раз перейти к случайному соседу у текущего объекта. И получается некоторое случайное распределение на объектах в наших данных, и такой процесс называется "случайным блужданием". И мы, на самом деле, увидим примеры таких блужданий чуть позже в курсе. Итак, мы разобрались, как вообще обсуждать вероятности, и оказалось, что комбинаторика полезна для подсчета вероятностей. При этом даже эти знания уже могут пригодиться на практике, уже это может быть полезным. А дальше мы обсудим численные характеристики случайных объектов.
