броуновское дерево
Понятие в теории вероятностей

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

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

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

Определения

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

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

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

Рассмотрим пространство всех бинарных деревьев с листьями, пронумерованными от до . Эти деревья имеют ребра с длинами . Дерево затем определяется своей формой (то есть порядком узлов) и длинами ребер. Мы определяем вероятностный закон случайной величины на этом пространстве следующим образом: [ требуется пояснение ] к {\displaystyle к} 1 {\displaystyle 1} к {\displaystyle к} 2 к − 1 {\displaystyle 2k-1} ( ℓ 1 , … , ℓ 2 к − 1 ) ∈ Р + 2 к − 1 {\displaystyle (\ell _{1},\dots ,\ell _{2k-1})\in \mathbb {R} _{+}^{2k-1}} τ {\displaystyle \тау} П {\displaystyle \mathbb {P} } ( Т , ( Л я ) 1 ≤ я ≤ 2 к − 1 ) {\displaystyle (T,(L_{i})_{1\leq i\leq 2k-1})}

П ( Т = τ , Л я ∈ [ ℓ я , ℓ я + г ℓ я ] , ∀ 1 ≤ я ≤ 2 к − 1 ) = с эксп ⁡ ( − с 2 / 2 ) г ℓ 1 … г ℓ 2 к − 1 {\displaystyle \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}}

где . с = ∑ ℓ я {\displaystyle \textstyle s =\sum \ell _{i}}

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

Определение  —  Пусть будет случайным метрическим пространством со свойством дерева, то есть существует единственный путь между двумя точками . Снабдим вероятностной мерой . Предположим, что поддерево из сгенерировано точками, выбранными случайным образом при , имеет закон . Тогда называется броуновским деревом . Х {\displaystyle X} Х {\displaystyle X} Х {\displaystyle X} μ {\displaystyle \мю} Х {\displaystyle X} к {\displaystyle к} μ {\displaystyle \мю} П {\displaystyle \mathbb {P} } Х {\displaystyle X}

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

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

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

Пусть будет броуновская экскурсия. Определим псевдометрику на с помощью е = ( е ( х ) , 0 ≤ х ≤ 1 ) {\displaystyle e=(e(x),0\leq x\leq 1)} г {\displaystyle д} [ 0 , 1 ] {\displaystyle [0,1]}

г ( х , у ) := е ( х ) + е ( у ) − 2 мин { е ( з ) ; з ∈ [ х , у ] } , {\displaystyle d(x,y):=e(x)+e(y)-2\min {\big \{}e(z)\,;z\in [x,y]{\big \}},} для любого х , у ∈ [ 0 , 1 ] {\displaystyle x,y\in [0,1]}

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

х ∼ е у ⇔ г ( х , у ) = 0. {\displaystyle x\sim _{e}y\Leftrightarrow d(x,y)=0.}

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

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

Принято считать экскурсию, а не . е / 2 {\displaystyle e/2} е {\displaystyle e}

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

Это также называется строительством с ломкой палок .

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

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

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

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

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

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

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

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

Ссылки

  1. ^ Ле Галль, Жан-Франсуа (1999). Пространственные ветвящиеся процессы, случайные змеи и уравнения в частных производных . Springer Science \& Business Media.
  2. ^ Дэвид Олдос. "Континуальное случайное дерево" . Получено 2012-02-10 .
  3. ^ Грегори Мьермон . «Имитация леса продолжается, коричневая». Архивировано из оригинала 3 марта 2016 г. Проверено 10 февраля 2012 г.
  4. ^ Олдос, Дэвид (1991). «Континуумное случайное дерево I». Анналы вероятности . 19 (1): 1– 28. doi : 10.1214/aop/1176990534 .
  5. ^ Олдос, Дэвид (1991-10-25). "Континуальное случайное дерево. II. Обзор". Стохастический анализ . 167 : 23– 70. doi :10.1017/CBO9780511662980.003. ISBN 9780521425339.
  6. ^ Олдос, Дэвид (1993). «Случайное дерево континуума III». Анналы вероятности . 21 (1): 248– 289. doi : 10.1214/aop/1176989404 . ISSN  0091-1798. JSTOR  2244761. S2CID  122616896.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Brownian_tree&oldid=1187807840"