ब्राउनियन ट्री

प्रायिकता सिद्धांत में, ब्राउनियन ट्री, एल्डोस ट्री, या कॉन्टिनम रैंडम ट्री (सीआरटी) यादृच्छिक वास्तविक ट्रीस से एक विशेष मामला है जिसे ब्राउनियन भ्रमण से परिभाषित किया जा सकता है। ब्राउनियन ट्री को डेविड एल्डस द्वारा 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}$ ट्री के आकार पर निर्भर नहीं करता बल्कि सभी किनारों की लंबाई के कुल योग पर निर्भर करता है।

Definition — Let $X$ be a metric space with the tree property, meaning there exists a unique path between two points of $X$. Equip $X$ with a probability measure $\mu$. Suppose the sub-tree of $X$ generated by $k$ points, chosen randomly under $\mu$, has law $\mathbb {P}$. Then $X$ is called a Brownian tree.

मान लीजिए $X$ ट्री संपत्ति के साथ एक मीट्रिक स्थान है, जिसका अर्थ है कि $X$ के दो बिंदुओं के बीच एक अद्वितीय पथ उपस्थित है। $X$ को प्रायिकता माप $\mu$ से लैस करें। $k$ के तहत यादृच्छिक रूप से चुने गए $\mu$ बिंदुओं द्वारा उत्पन्न $X$ के सबट्री को नियम $\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}$.

Definition — The metric space ${\big (}[0,1]\,/\!\sim _{e},\,d{\big )}$ is called a Brownian tree.

मीट्रिक स्थान ${\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}$.

Definition — The closure ${\overline {\bigcup _{k\geq 1}T_{k}}}$, equipped with the distance previously built, is called Brownian tree.

क्लोजर ${\overline {\bigcup _{k\geq 1}T_{k}}}$, जो पहले से निर्मित दूरी से सुसज्जित है, को ब्राउनियन ट्री' कहा जाता है।

इस एल्गोरिथ्म का उपयोग संख्यात्मक रूप से ब्राउनियन ट्रीस का अनुकरण करने के लिए किया जा सकता है।

गैल्टन-वाटसन ट्री की सीमा

गैल्टन-वाटसन ट्री पर विचार करें, जिसके प्रजनन नियम में परिमित गैर-शून्य प्रसरण है, जिसके लिए वातानुकूलित है $n$ नोड्स होने देना ${\tfrac {1}{\sqrt {n}}}G_{n}$ यह ट्री हो, जिसके किनारों की लंबाई को विभाजित किया गया हो ${\sqrt {n}}$. दूसरे शब्दों में, प्रत्येक किनारे की लंबाई होती है ${\tfrac {1}{\sqrt {n}}}$. गैल्टन-वाटसन के ट्री को मीट्रिक स्थान के रूप में या पुनर्निर्मित गैल्टन-वाटसन के ट्री का उपयोग करके निर्माण को औपचारिक रूप दिया जा सकता है।

Theorem — ${\frac {1}{\sqrt {n}}}G_{n}$ वितरण में एक यादृच्छिक वास्तविक वृक्ष में परिवर्तित हो जाता है, जिसे हम ब्राउनियन वृक्ष कहते हैं।

यहां, उपयोग की जाने वाली सीमा स्कोरोखोड अंतरिक्ष में स्टोकेस्टिक प्रक्रियाओं के वितरण में अभिसरण है (यदि हम समोच्च प्रक्रियाओं पर विचार करें) या हौसडॉर्फ दूरी से परिभाषित वितरण में अभिसरण (यदि हम मीट्रिक रिक्त स्थान पर विचार करें)।