Введение
Концепция в теории вероятности. Континуумное случайное дерево, полученное из брауновской экскурсии.
the Continuum Random Tree obtained from a Brownian excursion
В теории вероятностей брауновское дерево, или дерево Алдоса, или континуумное случайное дерево (CRT) — это случайное реальное дерево, которое может быть определено из брауновской экскурсии. Брауновское дерево было определено и изучено Дэвидом Алдосом в трех статьях, опубликованных в 1991 и 1993 годах. С тех пор это дерево было обобщено. Это случайное дерево имеет несколько эквивалентных определений и построений: с использованием поддеревьев, генерируемых конечным числом листьев, с использованием брауновской экскурсии, разделения Пуассона прямой линии или как предел деревьев Гальтона-Уотсона. Интуитивно, брауновское дерево — это бинарное дерево, узлы (или точки ветвления) которого плотно расположены в дереве; то есть для любых двух различных точек дерева всегда найдется узел между ними. Это фрактальный объект, который можно аппроксимировать с помощью компьютеров или физических процессов с дендритной структурой.
Определения
Следующие определения представляют собой различные характеристики брауновского дерева, взятые из трех статей Олдоса. Понятия листа, узла, ветви и корня соответствуют интуитивному пониманию дерева (подробности – в описании реальных деревьев).
Закон конечных измерений
Это определение описывает конечномерные законы поддеревьев, порожденных конечным числом листьев. Рассмотрим пространство всех бинарных деревьев с листьями, пронумерованными от 1 до n. Эти деревья имеют n-1 ребер с длинами A. Дерево определяется своей формой (то есть порядком узлов) и длинами ребер. Мы определяем вероятностный закон случайной величины на этом пространстве следующим образом:
where
In other words, depends not on the shape of the tree but rather on the total sum of all the edge lengths. In other words, the Brownian tree is defined from the laws of all the finite sub trees one can generate from it.
где
where
In other words, depends not on the shape of the tree but rather on the total sum of all the edge lengths. In other words, the Brownian tree is defined from the laws of all the finite sub trees one can generate from it.
Другими словами, P зависит не от формы дерева, а от общей суммы длин всех ребер. Иными словами, брауновское дерево определяется законами всех конечных поддеревьев, которые можно из него получить.
where
In other words, depends not on the shape of the tree but rather on the total sum of all the edge lengths. In other words, the Brownian tree is defined from the laws of all the finite sub trees one can generate from it.
Строительство разрыва линии Poisson
Это также называется построением с разрывом палочки. Рассмотрим неоднородный пуассоновский процесс точек N с интенсивностью. Иными словами, для любого t, является пуассоновской случайной величиной с параметром t. Пусть – точки этого процесса. Тогда длины интервалов между точками являются экспоненциальными случайными величинами с убывающими математическими ожиданиями. Далее мы выполняем следующее построение:
(initialisation) The first step is to pick a random point uniformly on the interval Then we glue the segment to (mathematically speaking, we define a new distance). We obtain a tree with a root (the point 0), two leaves ( and ), as well as one binary branching point (the point ). (iteration) At step k, the segment is similarly glued to the tree , on a uniformly random point of
This algorithm may be used to simulate numerically Brownian trees.
(инициализация) Первый шаг – выбрать случайную точку равномерно на интервале [0, 1]. Затем мы приклеиваем отрезок [0, ] к точке (математически говоря, мы определяем новое расстояние). В результате получается дерево с корнем (точка 0), двумя листьями ( и ), а также одной точкой бинарного ветвления (точка ).
(initialisation) The first step is to pick a random point uniformly on the interval Then we glue the segment to (mathematically speaking, we define a new distance). We obtain a tree with a root (the point 0), two leaves ( and ), as well as one binary branching point (the point ). (iteration) At step k, the segment is similarly glued to the tree , on a uniformly random point of
This algorithm may be used to simulate numerically Brownian trees.
(итерация) На шаге k отрезок аналогично приклеивается к дереву , в случайно выбранной точке на этом дереве.
(initialisation) The first step is to pick a random point uniformly on the interval Then we glue the segment to (mathematically speaking, we define a new distance). We obtain a tree with a root (the point 0), two leaves ( and ), as well as one binary branching point (the point ). (iteration) At step k, the segment is similarly glued to the tree , on a uniformly random point of
This algorithm may be used to simulate numerically Brownian trees.
Этот алгоритм может быть использован для численного моделирования брауновских деревьев.
(initialisation) The first step is to pick a random point uniformly on the interval Then we glue the segment to (mathematically speaking, we define a new distance). We obtain a tree with a root (the point 0), two leaves ( and ), as well as one binary branching point (the point ). (iteration) At step k, the segment is similarly glued to the tree , on a uniformly random point of
This algorithm may be used to simulate numerically Brownian trees.
Граница деревьев Гальтона-Уотсона
Рассмотрим дерево Гальтона-Уотсона, закон воспроизводства которого имеет конечную ненулевую дисперсию, при условии, что в дереве задано количество узлов. Пусть это дерево обозначено , а длины его ребер разделены на . Иными словами, каждое ребро имеет длину . Данную конструкцию можно формализовать, рассматривая дерево Гальтона-Уотсона как метрическое пространство или используя ренормированные контурные процессы. В данном случае, в качестве предела используется сходимость по распределению стохастических процессов в пространстве Скорохода (если рассматриваются контурные процессы) или сходимость по распределению, определяемая через расстояние Хаусдорфа (если рассматриваются метрические пространства).