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

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

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.

दूसरे शब्दों में, ब्राउनियन वृक्ष को उन सभी परिमित उप-वृक्षों के नियमों से परिभाषित किया जाता है जो इससे उत्पन्न हो सकते हैं।

सतत वृक्ष

ब्राउनियन वृक्ष एक वास्तविक वृक्ष है जिसे ब्राउनियन भ्रमण से परिभाषित किया गया है (वास्तविक वृक्ष में लक्षण वर्णन 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.

भ्रमण पर विचार करने की प्रथा है $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.

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

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

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

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

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