संभाव्य विधि

गणित में, संभाव्यता पद्धति एक गैर-रचनात्मक प्रमाण पद्धति है, जो मुख्य रूप से संयोजक में प्रयोग की जाती है और पॉल एर्डोस द्वारा अग्रणी है, गणितीय प्रमाण के लिए एक निर्धारित प्रकार की गणितीय वस्तु का अस्तित्व है। यह दिखा कर काम करता है कि यदि कोई निर्दिष्ट वर्ग से वस्तुओं को यादृच्छिक रूप से चुनता है, तो संभावना है कि निर्धारित प्रकार का परिणाम शून्य से अधिक है। हालांकि सबूत संभाव्यता का उपयोग करता है, अंतिम निष्कर्ष बिना किसी संभावित त्रुटि के 'निश्चित' के लिए निर्धारित होता है।

यह पद्धति अब गणित के अन्य क्षेत्रों जैसे संख्या सिद्धांत, रेखीय बीजगणित और वास्तविक विश्लेषण के साथ-साथ कंप्यूटर विज्ञान (जैसे यादृच्छिक गोलाई) और सूचना सिद्धांत में लागू की गई है।

परिचय

यदि वस्तुओं के संग्रह में प्रत्येक वस्तु में एक निश्चित गुण होने में विफल रहता है, तो संभावना है कि संग्रह से चुनी गई एक यादृच्छिक वस्तु में वह संपत्ति शून्य है।

इसी तरह, यह दिखाते हुए कि संभावना (सख्ती से) 1 से कम है, किसी वस्तु के अस्तित्व को साबित करने के लिए इस्तेमाल किया जा सकता है जो निर्धारित गुणों को पूरा नहीं करता है।

संभाव्यता पद्धति का उपयोग करने का दूसरा तरीका कुछ यादृच्छिक चर के अपेक्षित मूल्य की गणना करना है। यदि यह दिखाया जा सकता है कि यादृच्छिक चर अपेक्षित मान से कम मान ले सकता है, तो यह साबित करता है कि यादृच्छिक चर भी अपेक्षित मान से अधिक मान ले सकता है।

वैकल्पिक रूप से, संभाव्य विधि का उपयोग नमूना स्थान में एक वांछित तत्व के अस्तित्व की गारंटी देने के लिए भी किया जा सकता है, जो गणना किए गए अपेक्षित मूल्य से अधिक या उसके बराबर है, क्योंकि ऐसे तत्व की गैर-मौजूदगी में प्रत्येक तत्व का अर्थ होगा। नमूना स्थान अपेक्षित मान से कम है, यह एक विरोधाभास है।

संभाव्यता पद्धति में उपयोग किए जाने वाले सामान्य उपकरणों में मार्कोव की असमानता, Chernoff बाध्य और लोवाज़ स्थानीय लेम्मा शामिल हैं।

== Erdős == के कारण दो उदाहरण हालांकि उनके पहले के अन्य लोगों ने संभाव्य पद्धति के माध्यम से प्रमेयों को सिद्ध किया (उदाहरण के लिए, स्ज़ेल के 1943 के परिणाम में बड़ी संख्या में हैमिल्टनियन चक्रों वाले टूर्नामेंट (ग्राफ सिद्धांत) मौजूद हैं), इस पद्धति का उपयोग करने वाले कई सबसे प्रसिद्ध प्रमाण एर्डोस के कारण हैं। नीचे दिया गया पहला उदाहरण 1947 के एक ऐसे परिणाम का वर्णन करता है जो रैमसे के प्रमेय के लिए निचली सीमा का प्रमाण देता है $R (r, r)$ .

पहला उदाहरण

मान लीजिए हमारे पास एक पूरा ग्राफ है $n$ शिखर (ग्राफ सिद्धांत) । हम दिखाना चाहते हैं (छोटे पर्याप्त मूल्यों के लिए $n$ ) कि ग्राफ के किनारे (ग्राफ सिद्धांत) को दो रंगों (लाल और नीला कहते हैं) में रंगना संभव है ताकि कोई पूर्ण सबग्राफ (ग्राफ सिद्धांत) न हो $r$ कोने जो मोनोक्रोमैटिक (हर किनारे को एक ही रंग का रंग) है।

ऐसा करने के लिए, हम ग्राफ़ को बेतरतीब ढंग से रंगते हैं। प्रायिकता के साथ प्रत्येक किनारे को स्वतंत्र रूप से रंगें $1/2$ लाल होना और $1/2$ नीला होना। हम मोनोक्रोमैटिक सबग्राफ की अपेक्षित संख्या की गणना करते हैं $r$ कोने इस प्रकार हैं:

किसी भी सेट के लिए $S_{r}$ का $r$ हमारे ग्राफ से शिखर, चर को परिभाषित करें $X(S_{r})$ होना $1$ अगर हर किनारे के बीच $r$ शिखर एक ही रंग है, और $0$ अन्यथा। ध्यान दें कि मोनोक्रोमैटिक की संख्या $r$ -सबग्राफ का योग है $X(S_{r})$ सभी संभावित उपसमुच्चय पर $S_{r}$ . किसी भी व्यक्तिगत सेट के लिए $S_{r}^{i}$ , का अपेक्षित मूल्य $X(S_{r}^{i})$ केवल संभावना है कि सभी $C(r,2)$ किनारों में $S_{r}^{i}$ एक ही रंग हैं:

E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}

(का कारक $2$ आता है क्योंकि दो संभावित रंग हैं)।

यह किसी के लिए भी सही है $C(n,r)$ संभावित उपसमुच्चय जिन्हें हम चुन सकते थे, अर्थात $i$ से लेकर $1$ को $C(n,r)$ . तो हमारे पास इसका योग है $E[X(S_{r}^{i})]$ कुल मिलाकर $S_{r}^{i}$ है

\sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.

अपेक्षाओं का योग योग की अपेक्षा है (भले ही चर सांख्यिकीय स्वतंत्रता हैं), इसलिए योग की अपेक्षा (सभी मोनोक्रोमैटिक की अपेक्षित संख्या $r$ -सबग्राफ) है

E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.

विचार करें कि क्या होता है यदि यह मान इससे कम है $1$ . मोनोक्रोमैटिक की अपेक्षित संख्या के बाद से $r$ -सबग्राफ सख्ती से कम है $1$ , एक रंग मौजूद है जो स्थिति को संतुष्ट करता है कि मोनोक्रोमैटिक की संख्या $r$ -सबग्राफ सख्ती से कम है $1$ . मोनोक्रोमैटिक की संख्या $r$ -इस यादृच्छिक रंग में सबग्राफ एक गैर-ऋणात्मक पूर्णांक है, इसलिए यह होना चाहिए $0$ ( $0$ से कम एकमात्र गैर-ऋणात्मक पूर्णांक है $1$ ). इससे पता चलता है कि अगर

E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1

(जो रखता है, उदाहरण के लिए, के लिए $n = 5$ और $r = 4$ ), एक रंग मौजूद होना चाहिए जिसमें कोई मोनोक्रोमैटिक न हो $r$ -सबग्राफ।^{[lower-alpha 1]}

रैमसे संख्या की परिभाषा के अनुसार, इसका तात्पर्य है कि $R (r, r)$ से बड़ा होना चाहिए $n$ . विशेष रूप से, $R (r, r)$ के साथ कम से कम घातीय वृद्धि होनी चाहिए $r$ .

इस तर्क की एक कमजोरी यह है कि यह पूरी तरह से अरचनात्मक प्रमाण है। भले ही यह (उदाहरण के लिए) साबित होता है कि पूरे ग्राफ के लगभग हर रंग पर $(1.1) r$ शीर्षों में कोई एकवर्णी नहीं होता है $r$ -सबग्राफ, यह इस तरह के रंग का कोई स्पष्ट उदाहरण नहीं देता है। इस तरह के रंग को खोजने की समस्या 50 से अधिक वर्षों से खुली समस्या रही है।

↑
The same fact can be proved without probability, using a simple counting argument:
- The total number of r-subgraphs is ${n \choose r}$ .
- Each r-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.
- Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).
- Hence, the total number of colorings that are bad for some (at least one) subgraph is at most $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .
- Hence, if $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1$ , there must be at least one coloring which is not 'bad' for any subgraph.

दूसरा उदाहरण

Erdős के 1959 के पेपर (नीचे उद्धृत संदर्भ देखें) ने ग्राफ सिद्धांत में निम्नलिखित समस्या को संबोधित किया: दिए गए सकारात्मक पूर्णांक $g$ और $k$ , क्या कोई ग्राफ मौजूद है $G$ कम से कम लंबाई का केवल चक्र (ग्राफ सिद्धांत) युक्त $g$ , जैसे कि रंगीन संख्या $G$ कम से कम है $k$ ?

यह दिखाया जा सकता है कि ऐसा ग्राफ किसी के लिए भी मौजूद है $g$ और $k$ , और सबूत यथोचित सरल है। होने देना $n$ बहुत बड़ा हो और एक यादृच्छिक ग्राफ पर विचार करें $G$ पर $n$ कोने, जहां हर किनारा अंदर है $G$ संभाव्यता के साथ मौजूद है $p = n 1/ g -1$ . हम दिखाते हैं कि सकारात्मक संभावना के साथ, $G$ निम्नलिखित दो गुणों को संतुष्ट करता है:

संपत्ति 1।

G

अधिक से अधिक शामिल हैं

n /2

से कम लंबाई के चक्र

g

.

सबूत। होने देना $X$ से कम लंबाई के संख्या चक्र हो $g$ . लंबाई के चक्रों की संख्या $i$ पूरे ग्राफ में $n$ शिखर है

{\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}

और उनमें से प्रत्येक में मौजूद है $G$ संभाव्यता के साथ $p i$ . इसलिए मार्कोव की असमानता से हमारे पास है

\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).

इस प्रकार पर्याप्त रूप से बड़े के लिए

n

, संपत्ति 1 से अधिक की संभावना के साथ रखती है

1/2

.

संपत्ति 2।

G

में आकार का कोई स्वतंत्र सेट (ग्राफ़ सिद्धांत) नहीं है

\lceil {\tfrac {n}{2k}}\rceil

.

सबूत। होने देना $Y$ में सबसे बड़े स्वतंत्र सेट का आकार हो $G$ . स्पष्ट रूप से, हमारे पास है

\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),

कब

y=\left\lceil {\frac {n}{2k}}\right\rceil \!.

इस प्रकार, पर्याप्त बड़े के लिए

n

, संपत्ति 2 से अधिक की संभावना के साथ रखती है

1/2

.

काफी बड़े के लिए $n$ , संभावना है कि वितरण से एक ग्राफ में दोनों गुण हैं, सकारात्मक है, क्योंकि इन गुणों की घटनाओं को अलग नहीं किया जा सकता है (यदि वे थे, तो उनकी संभावनाएं 1 से अधिक हो जाएंगी)।

यहाँ चाल आती है: चूंकि $G$ में ये दो गुण हैं, हम अधिक से अधिक निकाल सकते हैं $n /2$ शिखर से $G$ एक नया ग्राफ प्राप्त करने के लिए $G'$ पर $n'\geq n/2$ वे शीर्ष जिनमें कम से कम केवल लंबाई के चक्र हों $g$ . हम देख सकते हैं कि इस नए ग्राफ में आकार का कोई स्वतंत्र सेट नहीं है $\left\lceil {\frac {n'}{k}}\right\rceil$ . $G'$ को केवल कम से कम में विभाजित किया जा सकता है $k$ स्वतंत्र सेट, और, इसलिए, कम से कम रंगीन संख्या होती है $k$ .

यह परिणाम इस बात का संकेत देता है कि किसी ग्राफ की रंगीन संख्या की गणना इतनी कठिन क्यों है: यहां तक कि जब ग्राफ के लिए कई रंगों की आवश्यकता के लिए कोई स्थानीय कारण (जैसे छोटे चक्र) नहीं होते हैं, तब भी रंगीन संख्या मनमाने ढंग से बड़ी हो सकती है।

यह भी देखें

अतिरिक्त संसाधन

कॉम्बिनेटरिक्स में संभाव्य तरीके, MIT OpenCourseWare

संदर्भ

Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
Erdős, P. (1959). "Graph theory and probability". Can. J. Math. 11: 34–38. doi:10.4153/CJM-1959-003-9. MR 0102081. S2CID 122784453.
Erdős, P. (1961). "Graph theory and probability, II". Can. J. Math. 13: 346–352. CiteSeerX 10.1.1.210.6669. doi:10.4153/CJM-1961-029-9. MR 0120168. S2CID 15134755.
J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics
Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, ISBN 978-981-3149-84-7, 2017
Elishakoff I., Lin Y.K. and Zhu L.P. , Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0

फुटनोट्स

श्रेणी: संयोजन विज्ञान श्रेणी:गणितीय प्रमाण श्रेणी:संभाव्य तर्क

[1] The same fact can be proved without probability, using a simple counting argument:
The total number of r-subgraphs is ${n \choose r}$ .

Each r-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.

Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).

Hence, the total number of colorings that are bad for some (at least one) subgraph is at most $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .

Hence, if $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1$ , there must be at least one coloring which is not 'bad' for any subgraph.

[2] The total number of r-subgraphs is ${n \choose r}$ .

[3] Each r-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.

[4] Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).

[5] Hence, the total number of colorings that are bad for some (at least one) subgraph is at most $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$ .

[6] Hence, if $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1$ , there must be at least one coloring which is not 'bad' for any subgraph.

[lower-alpha 1]

Anonymous

Search

संभाव्य विधि

Namespaces

More

Page actions

Contents

परिचय

पहला उदाहरण

दूसरा उदाहरण

यह भी देखें

अतिरिक्त संसाधन

संदर्भ

फुटनोट्स

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संभाव्य विधि

परिचय

पहला उदाहरण

दूसरा उदाहरण

यह भी देखें

अतिरिक्त संसाधन

संदर्भ

फुटनोट्स

Navigation

Wiki tools

Page tools

Other projects

Hidden categories