Drzewo Browna

W teorii prawdopodobieństwa drzewo Browna , drzewo Aldousa lub kontinuum Random Tree (CRT) jest szczególnym przypadkiem przypadkowych drzew rzeczywistych , które można zdefiniować na podstawie wycieczki Browna . Drzewo Browna zostało zdefiniowane i zbadane przez Davida Aldousa w trzech artykułach opublikowanych w 1991 i 1993 roku. Od tego czasu drzewo to zostało uogólnione.

To losowe drzewo ma kilka równoważnych definicji i konstrukcji: użycie poddrzew generowanych przez skończoną liczbę liści, użycie wycieczki Browna, Poissona oddzielającego linię prostą lub jako granicę drzew Galtona-Watsona.

Intuicyjnie drzewo Browna jest drzewem binarnym, którego węzły (lub punkty rozgałęzień) są gęste w drzewie; to znaczy, że dla dowolnych dwóch odrębnych punktów drzewa zawsze będzie istniał między nimi węzeł. Jest to fraktalny , który można aproksymować za pomocą komputerów lub procesów fizycznych ze strukturami dendrytycznymi .

Definicje

Poniższe definicje to różne charakterystyki drzewa Browna, zaczerpnięte z trzech artykułów Aldousa. Pojęcia liścia, węzła, gałęzi, korzenia są intuicyjnymi pojęciami na drzewie (szczegóły w prawdziwych drzewach ).

Prawa skończonych wymiarów

Ta definicja podaje prawa skończonych wymiarów poddrzew generowanych przez skończenie wiele liści.

Rozważmy przestrzeń wszystkich drzew binarnych z liśćmi ponumerowanymi od $k}$ $displaystyle$ do $\ displaystyle k}$ . Te drzewa mają $\ ell _ {1}, \ kropki, \ell _{2k-1})\w \mathbb {R} _{+}^{2k-1}}$ długościach $1$ . Drzewo jest następnie definiowane przez jego kształt $to$ znaczy kolejność węzłów) i długości krawędzi. Definiujemy prawo prawdopodobieństwa $zmiennej losowej$ $\leq i\leq 2k-1})}$ $\ Displaystyle (T, (L_ {i}) _ {$ 1 na tej przestrzeni przez:

{\ Displaystyle \ mathbb {P} (T = \ tau \,, \, L_ {i} \ w [\ 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}}

gdzie ${\ Displaystyle \ textstyle s = \ suma \ ell _ {i}}$ .

Innymi słowy, nie zależy od kształtu drzewa, ale raczej od całkowitej sumy wszystkich długości $krawędzi$

Definicja - Niech będzie przestrzenią metryczną z właściwością drzewa, co oznacza, że istnieje unikalna ścieżka między dwoma punktami $X$ $displaystyle X}$ . Wyposaż $_$ w $.$ prawdopodobieństwa $,$ $,$ $punkty$ poddrzewo wygenerowane przez wybrane losowo $ma$ prawo . Następnie nazywa $Browna$ drzewem .

Innymi słowy, drzewo Browna jest zdefiniowane na podstawie praw wszystkich skończonych poddrzew, które można z niego wygenerować.

Ciągłe drzewo

Drzewo Browna jest prawdziwym drzewem zdefiniowanym na podstawie wycieczki Browna (patrz charakterystyka 4 w Prawdziwym drzewie ).

Niech ${\ Displaystyle e = (e (x), 0 \ równoważnik x \ równoważnik 1)}$ będzie wycieczką Browna. Zdefiniuj pseudometryczny $]$ ${\ Displaystyle [0,1$ } z

{\ Displaystyle d (x, y): = e (x) + e (y) -2 \ min {\ duży \ {} e (z) \, z \ w [ x, y] {\ duży \}},}

dla dowolnego

{\ Displaystyle x, y \ w [0,1]}

Następnie definiujemy relację równoważności , zanotowaną $\ Displaystyle$ $0,1]} , która odnosi się do$ $displaystyle \ sim _ {e}}$ punktów tak, że ∼ \ ${\ Displaystyle d (x, y) = 0}$ .

{\ Displaystyle x \ sim _ {e} y \ strzałka w lewo d (x, y) = 0.}

${\ displaystyle d}$ jest wtedy odległością w przestrzeni ilorazu ${\ Displaystyle [0,1] \,/ \! \ sim _ {e}}$ .

Definicja - Przestrzeń metryczna ${\ Displaystyle {\ duży (} [0,1] \,/ \! \ sim _ {e}, \, d {\ duży)}}$ nazywa się drzewem Browna .

Zwyczajowo bierze się pod uwagę wycieczkę, $e/2}$ nie $displaystyle$ .

Konstrukcja przełamująca linię Poissona

Nazywa się to również budową łamiącą kije .

Rozważmy niejednorodny proces punktu Poissona $N$ z intensywnością ${\ displaystyle r (t) = t}$ . Innymi słowy, dla dowolnego $t$ zmienną $displaystyle$ z parametrem 2 ${2}}$ . Niech do $\ Displaystyle C_ {1}, C_ {2}, \ ldots}$ będą punktami ${\ displaystyle N}$ . $_$ długości _ _ _ Następnie wykonujemy następującą konstrukcję:

( inicjalizacja ) Pierwszym krokiem jest wybranie losowego punktu $równomiernie$ przedziale [ $\ Displaystyle [0, C_ {1}]}$ . $Następnie$ przyklejamy odcinek $do$ rzecz ) Otrzymujemy drzewo $i$ korzeniem (punkt 0), dwoma liśćmi ( $\ Displaystyle T_ {1}}$ 2 $\ Displaystyle C_ {2} }$ ), jak oraz jeden binarny punkt rozgałęzienia ( $)$ .
( iteracja ) W kroku $k$ segment jest podobnie przyklejony do drzewa $}]$ $} k-1}}$ , w równomiernie losowym punkcie ${\ Displaystyle T_ {k-1}}$ .

Definicja - Zamknięcie $_$ wcześniej drzewem Browna _

Algorytm ten może być wykorzystany do numerycznej symulacji drzew Browna.

Granica drzew Galtona-Watsona

$,$ którego prawo reprodukcji ma skończoną niezerową wariancję, uwarunkowaną posiadaniem . Niech $n}}$ drzewem, z długościami krawędzi podzielonymi przez $}$ . Innymi słowy, każda krawędź ma długość ${\ displaystyle {\ tfrac {1} {\ sqrt {n}}}}$ . Konstrukcję można sformalizować, uznając drzewo Galtona-Watsona za przestrzeń metryczną lub stosując renormalizowane procesy konturowe.

Definicja i Twierdzenie — ${\ Displaystyle {\ Frac {1} {\ sqrt {n}}} G_ {n}}$ zbiega się w rozkładzie do losowego drzewa rzeczywistego, które nazywamy drzewem Browna .

Granicą jest tutaj zbieżność rozkładu procesów stochastycznych w przestrzeni Skorochoda (jeśli uwzględniamy procesy konturowe) lub zbieżność rozkładu określona z odległości Hausdorffa (jeśli uwzględniamy przestrzenie metryczne).