Броуновское дерево

Эта статья о случайном дереве континуума, полученном в результате броуновского экскурса. О компьютерном искусстве, развитом в 90-е годы, см. Агрегация, ограниченная диффузией .

В теории вероятностей — броуновское дерево , или дерево Олдоса , или континуальное случайное дерево (CRT). — случайное реальное дерево , которое можно определить на основе броуновского отклонения . Броуновское дерево было определено и изучено Дэвидом Олдосом в трех статьях, опубликованных в 1991 и 1993 годах. С тех пор это дерево было обобщено.

Это случайное дерево имеет несколько эквивалентных определений и конструкций: использование поддеревьев, порожденных конечным числом листьев, использование броуновского экскурса, пуассоновского разделения прямой линии или предела деревьев Гальтона-Ватсона.

Интуитивно понятно, что броуновское дерево — это бинарное дерево, узлы (или точки ветвления) которого плотны в дереве; то есть для любых двух различных точек дерева всегда будет существовать узел между ними. Это фрактальный объект, который можно аппроксимировать с помощью компьютеров. или физическими процессами с дендритными структурами .

Определения

Следующие определения представляют собой различные характеристики броуновского дерева и взяты из трех статей Олдоса. Понятия листа, узла, ветви, корня — это интуитивные понятия дерева (подробнее см. Реальные деревья ).

Конечномерные законы

Это определение дает конечномерные законы поддеревьев, порожденных конечным числом листьев.

Рассмотрим пространство всех бинарных деревьев с $k$ листья пронумерованы от $1$ к $k$. У этих деревьев есть $2k-1$ края с длиной $(\ell _{1},\dots ,\ell _{2k-1})\in \mathbb {R} _{+}^{2k-1}$. Тогда дерево определяется его формой. $\tau$ (то есть порядок узлов) и длины ребер. Определим закон вероятности $\mathbb {P}$ случайной величины $(T,(L_{i})_{1\leq i\leq 2k-1})$ на этом пространстве:

$\mathbb {P} (T=\tau \,,\,L_{i}\in [\ell _{i},\ell _{i}+d\ell _{i}],\forall 1\leq i\leq 2k-1)=s\exp(-s^{2}/2)\,d\ell _{1}\ldots d\ell _{2k-1}$

где $\textstyle s=\sum \ell _{i}$.

Другими словами, $\mathbb {P}$ зависит не от формы дерева, а от общей суммы длин всех ребер.

Определение — Пусть $X$ быть случайным метрическим пространством со свойством дерева, что означает, что существует уникальный путь между двумя точками $X$. Оборудовать $X$ с вероятностной мерой $\mu$. Предположим, что поддерево $X$ созданный $k$ точки, выбранные случайным образом под $\mu$, имеет закон $\mathbb {P}$. Затем $X$ называется броуновским деревом .

Другими словами, броуновское дерево определяется на основе законов всех конечных поддеревьев, которые можно из него сгенерировать.

Непрерывное дерево

Броуновское дерево — это реальное дерево, определенное на основе броуновского отклонения (см. характеристику 4 в Реальном дереве ).

Позволять $e=(e(x),0\leq x\leq 1)$быть броуновским экскурсом. Определите псевдометрику $d$ на $[0,1]$ с

$d(x,y):=e(x)+e(y)-2\min {\big \{}e(z)\,;z\in [x,y]{\big \}},$ для любого $x,y\in [0,1]$

Затем мы определяем отношение эквивалентности , отмеченное $\sim _{e}$ на $[0,1]$ который касается всех пунктов $x,y$ такой, что $d(x,y)=0$ .

$x\sim _{e}y\Leftrightarrow d(x,y)=0.$

$d$ тогда это расстояние в факторпространстве $[0,1]\,/\!\sim _{e}$.

Определение . Случайное метрическое пространство. ${\big (}[0,1]\,/\!\sim _{e},\,d{\big )}$ называется броуновским деревом .

Экскурсию принято считать $e/2$ скорее, чем $e$.

Пуассоновая конструкция разрыва линии

Это также называется конструкцией, ломающей палки .

Рассмотрим неоднородный точечный пуассоновский процесс N с интенсивностью $r(t)=t$. Другими словами, для любого $t>0$, $N_{t}$ — переменная Пуассона с параметром $t^{2}$. Позволять $C_{1},C_{2},\ldots$ быть точками $N$. Тогда длины интервалов $[C_{i},C_{i+1}]$ являются экспоненциальными переменными с убывающими средними. Далее делаем следующую конструкцию:

• ( инициализация ) Первый шаг — выбрать случайную точку. $u$ равномерно на интервале $[0,C_{1}]$. Затем склеиваем отрезок $]C_{1},C_{2}]$ к $u$ (математически говоря, мы определяем новое расстояние). Получаем дерево $T_{1}$ с корнем (точка 0), двумя листьями ( $C_{1}$ и $C_{2}$), а также одну бинарную точку ветвления (точку $u$).
• ( итерация ) На шаге k сегмент $]C_{k},C_{k+1}]$ аналогично приклеивается к дереву $T_{k-1}$, в равномерно случайной точке $T_{k-1}$.

Определение . Замыкание . ${\overline {\bigcup _{k\geq 1}T_{k}}}$, снабженное ранее построенным расстоянием, называется броуновским деревом .

Этот алгоритм можно использовать для численного моделирования броуновских деревьев.

Предел деревьев Гальтона-Ватсона

Рассмотрим дерево Гальтона-Ватсона , закон воспроизводства которого имеет конечную ненулевую дисперсию, при условии, что $n$ узлы. Позволять ${\tfrac {1}{\sqrt {n}}}G_{n}$ быть этим деревом с длинами ребер, разделенными на ${\sqrt {n}}$. Другими словами, каждое ребро имеет длину ${\tfrac {1}{\sqrt {n}}}$. Построение можно формализовать, рассматривая дерево Гальтона-Ватсона как метрическое пространство или используя перенормированные контурные процессы .

Определение и теорема — ${\frac {1}{\sqrt {n}}}G_{n}$ сходится по распределению к случайному вещественному дереву, которое мы называем броуновским деревом .

Здесь используется предел сходимости по распределению случайных процессов в пространстве Скорохода (если рассматривать контурные процессы) или сходимости по распределению, определяемому расстоянием Хаусдорфа (если рассматривать метрические пространства).