ВЕРОЯ́ТНОСТНАЯ КОМБИНАТО́РИКА
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
ВЕРОЯ́ТНОСТНАЯ КОМБИНАТО́РИКА, раздел дискретной математики, в котором методы теории вероятностей применяются для изучения комбинаторных объектов. В В. к. рассматриваются также перечислительные задачи комбинаторики и вопросы существования комбинаторных объектов с заданными характеристиками.
При использовании вероятностных методов для решения перечислительных задач комбинаторики на конечном множестве комбинаторных объектов задаётся вероятностное распределение и исследуются распределения характеристик случайного комбинаторного объекта из этого множества. Если заданное распределение является равномерным, то вероятность того, что некоторая характеристика случайного объекта приняла какое-то значение, есть отношение числа объектов, обладающих этим значением характеристики, к общему числу объектов в множестве, так что, если общее число объектов известно, задача нахождения вероятности и перечислительная задача нахождения числа объектов с заданным значением характеристики эквивалентны.
Первые шаги В. к. связаны с развитием в сер. 17 в. элементарной теории вероятностей, когда комбинаторные методы использовались для подсчёта разл. вероятностей в азартных играх. Первые результаты исследований в В. к. с использованием совр. методов теории вероятностей появились в работах В. Л. Гончарова 1942–44, в которых получены осн. результаты о предельном поведении случайных величин, связанных с цикловой структурой случайных подстановок при возрастании их степеней. Случайная подстановка степени $n$ – это подстановка, выбираемая с равными вероятностями из множества всех подстановок степени $n$. С использованием хорошо развитых в теории вероятностей методов доказательства предельных теорем (метода производящих функций, метода характеристических функций, а также метода моментов) Гончаровым было доказано, что число циклов длины $r$ в случайной подстановке степени $n$ имеет в пределе при $n→∞$ распределение Пуассона с параметром $1/r$, распределение общего числа циклов сближается с нормальным распределением с параметрами ($\ln n, \ln n $), найдено предельное распределение макс. длины цикла случайной подстановки. Впоследствии эти результаты во многом служили образцом для изучения разл. классов случайных комбинаторных объектов, в т. ч. случайных размещений, случайных разбиений целых чисел на целочисленные слагаемые, разл. классов случайных графов (случайных отображений, лесов, деревьев), случайных матриц, систем случайных уравнений, случайных автоматов, случайных алгоритмов.
При изучении случайных графов венг. математиками П. Эрдёшем и А. Реньи был обнаружен (1960) неожиданный эффект, который по аналогии с подобным эффектом в поведении систем частиц в статистич. физике трактуется как фазовый переход. Пусть $𝒢_{n,T}$ – случайный граф с $n$ вершинами, который получается в результате размещения $T$ рёбер, каждое из которых независимо от размещения остальных рёбер занимает любое из $n(n-1)/2$ возможных мест с равными вероятностями. Пусть $2T/n→λ$ при $n, T→∞$. Если $λ < 1$, точнее, если $(1–2T/n)^3n→∞$, то граф $𝒢_{n,T}$ с вероятностью, стремящейся к единице, состоит из связных компонент, которые являются либо деревьями, либо компонентами, содержащими ровно один цикл. При переходе параметром $2T/n$ значения 1, точнее, в области, где при $n, T→∞$ параметр $(1–2T/n)^3$ стремится к к.-л. постоянной $c$, появляется т. н. гигантская компонента, число вершин в которой асимптотически нормально с математич. ожиданием $α (c)n$, при этом с убыванием параметра $c$ параметр $α(c)$ возрастает. При $(1–2T/n)^3n→–∞$ граф $𝒢_{n,T} $ с вероятностью, стремящейся к единице, состоит из гигантской компоненты, деревьев и компонент с одним циклом. Такое поведение случайного графа при переходе параметром $2T/n$ значения 1 можно интерпретировать как фазовый переход или, другими словами, как наличие порогового эффекта в поведении случайного графа. Позднее пороговый эффект был обнаружен в поведении ещё более простых случайных комбинаторных объектов таких, как случайные леса из корневых и некорневых деревьев.
Вероятностный подход используется и для доказательства существования комбинаторных объектов без привлечения конструктивных построений. Простейший вариант этого подхода основан на том, что если математич. ожидание целочисленной неотрицательной случайной величины положительно, то эта случайная величина не равна тождественно нулю. Один из примеров применения вероятностного подхода состоит в следующем.
Пусть $𝒢_n(p)$ – случайный граф с $n$ вершинами, в котором каждая пара вершин независимо от остальных соединена ребром с вероятностью $p$ (с вероятностью $q$ такого ребра нет, $p+q=1$). В графе
$\overline{𝒢_{n}}(p)$, дополнительном к графу ${𝒢_{n}(p)}$, пара вершин соединена ребром тогда и только тогда, когда такого ребра нет в ${𝒢_{n}(p)}$. Пусть $v_n(p, k)$ и $\overline{v_{n}}(p, k)$ – числа полных подграфов с $k$ вершинами в $𝒢_n(p)$ и $\overline{𝒢_{n}}(p)$ соответственно. Для математич. ожиданий справедливы равенства
$\mathsf{M}v_n(p,k)=C_{n}^{k}p^{k(k-1)/2},$
$\mathsf{M}\overline{v}_n(p,k)=\mathsf{M}v_n(q,k)=C_{n}^{k}q^{k(k-1)/2}.$
Если число $k > max$ $\{$ $[2$ $\ln n /$ $\ln (1/p)]$$,[ 2 \ln n /$ $ \ln$ $(1/q)$ $]\}$, где $C_{n}^{k}$ – биномиальные коэффициенты, $[a]$ – целая часть числа $a$, то и при $n→∞$. Следствием этих соотношений является то, что для каждого фиксированного $p, 0 < p < 1$, и каждого достаточно большого $n$ существует граф $G_n(p)$ c $n$ вершинами, не содержащий полного подграфа с более чем $2\ln n/\ln(1/p)$ вершинами, дополнительный граф $\overline{G}_n(p)$ которого не содержит полного подграфа с более чем $\ln n/ \ln(1/q)$ вершинами.
Значительное внимание в В. к. уделяется генерации последовательностей случайных чисел, генерации случайных комбинаторных объектов таких, как случайные подстановки, а также вероятностному анализу алгоритмов и построению вероятностных алгоритмов, включающих в себя датчики случайных чисел.