Вероятностная комбинаторика

ВЕРОЯТНОСТНАЯ КОМБИНАТОРИКА, раздел дискретной математики, в котором методы теории вероятностей применяются для изучения комбинаторных объектов. В вероятностной комбинаторике рассматриваются также перечислительные задачи комбинаторики и вопросы существования комбинаторных объектов с заданными характеристиками.

При использовании вероятностных методов для решения перечислительных задач комбинаторики на конечном множестве комбинаторных объектов задаётся вероятностное распределение, и исследуются распределения характеристик случайного комбинаторного объекта из этого множества. Если заданное распределение является равномерным, то вероятность того, что некоторая характеристика случайного объекта приняла какое-то значение, есть отношение числа объектов, обладающих этим значением характеристики, к общему числу объектов в множестве, так что, если общее число объектов известно, задача нахождения вероятности и перечислительная задача нахождения числа объектов с заданным значением характеристики эквивалентны.

Первые шаги вероятностной комбинаторики связаны с развитием в середине 17 века элементарной теории вероятностей, когда комбинаторные методы использовались для подсчёта различных вероятностей в азартных играх. Первые результаты исследований в вероятностной комбинаторике с использованием современных методов теории вероятностей появились в работах В. Л. Гончарова 1942-44 года, в которых получены основные результаты о предельном поведении случайных величин, связанных с цикловой структурой случайных подстановок при возрастании их степеней. Случайная подстановка степени n - это подстановка, выбираемая с равными вероятностями из множества всех подстановок степени n. С использованием хорошо развитых в теории вероятностей методов доказательства предельных теорем (метода производящих функций, метода характеристических функций, а также метода моментов) Гончаровым было доказано, что число циклов длины r в случайной подстановке степени n имеет в пределе при n → ∞ распределение Пуассона с параметром 1/r, распределение общего числа циклов сближается с нормальным распределением с параметрами (ln n, ln n), найдено предельное распределение максимальной длины цикла случайной подстановки. Впоследствии эти результаты во многом служили образцом для изучения различных классов случайных комбинаторных объектов, в том числе случайных размещений, случайных разбиений целых чисел на целочисленные слагаемые, различных классов случайных графов (случайных отображений, лесов, деревьев), случайных матриц, систем случайных уравнений, случайных автоматов, случайных алгоритмов.

При изучении случайных графов венгерскими математиками П. Эрдёшем и А. Реньи был обнаружен (1960) неожиданный эффект, который по аналогии с подобным эффектом в поведении систем частиц в статистической физике трактуется как фазовый переход. Пусть g_n,T - случайный граф с n вершинами, который получает­ся в результате размещения Т рёбер, каждое из которых независимо от раз­мещения остальных рёбер занимает лю­бое из n(n - 1)/2 возможных мест с равными вероятностями. Пусть 2T/n→λ при n, →∞ Если λ < 1, точнее, если (1-2T/n)³n → ∞, то граф g_n,T  с вероятностью, стремящейся к единице, состоит из связных компонент, которые являются либо деревьями, либо компонентами, содержащими ровно один цикл. При переходе параметром 2 Т/n значения 1, точнее, в области, где при n, Т→∞ па­раметр (1-2Т/n)³ стремится к какой-либо постоянной с, появляется так называемая гигантская компонента, число вершин в которой асимптотически нормально с математическим ожиданием α(с)n, при этом с убыванием параметра с параметр α(с) возрастает. При (1-2Т/n)³n →∞ граф g_n,T с вероятностью, стремящейся к единице, состоит из гигантской компоненты, деревьев и компонент с одним циклом. Такое поведение случайного графа при переходе параметром 2 Т/n значения 1 можно интерпретировать как фазовый переход или, другими словами, как наличие порогового эффекта в поведении случайного графа. Позднее пороговый эффект был обнаружен в поведении ещё более простых случайных комбинаторных объектов таких, как случайные леса из корневых и некорневых деревьев.

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

Пусть g_n(p) - случайный граф с n вершинами, в котором каждая пара вер­шин независимо от остальных соединена ребром с вероятностью р (с вероятностью q такого ребра нет, p + q= 1). В графе ?g_n(р), дополнительном к графу g_n(р), пара вершин соединена ребром тогда и только тогда, когда такого ребра нет в g_n(р). Пусть v_n(p, k) и ?v_n(p, k) - чис­ла полных подграфов с k вершинами в g_n(p) и  g?_n(р) соответственно. Для математических ожиданий справедливы равенства

Если число k>max{[2lnn/ln(1/р)], [2lnn/ln(1/q)]}, где С^k_n - биномиаль­ные коэффициенты, [а] - целая часть числа а, то Mv_n(p,k) → 0 и M?v_n(p,k)→0 при n→∞. Следствием этих соотно­шений является то, что для каждого фиксированного р, 0<р<1, и каждо­го достаточно большого n существует граф G_n(p) с n вершинами, не содер­жащий полного подграфа с более чем 2lnn/ln(1/р) вершинами, дополнитель­ный граф которого ?G_n(p) не содер­жит полного подграфа с более чем 2lnn/ln(l/q) вершинами.

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

Лит.: Гончаров В. Л. О распределении циклов в перестановках // Доклады Академии Наук СССР. 1942. Т. 35. № 9; он же. Из области комбинаторики // Известия Академии Наук СССР. Сер. математическая. 1944. Т. 8. № 1; Степанов В.Е. Фазовые переходы в случайных графах // Теория вероятностей и ее применения. 1970. Т. 15. Вып. 2; Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М., 1976; Сачков В. Н. Вероятностные методы в комбинаторном анализе. М., 1978; Павлов Ю.Л. Случайные леса. Петрозаводск, 1996; Колчин В. Ф. Случайные графы. 2-е изд. М., 2004.