स्वतंत्रता কী?

उदाहरण 21.21 (किसी गुणनफल संरचना से पढ़ी गई स्वतंत्रता)

दो निष्पक्ष पासे फेंकिए: एकसमान भारों के साथ $\Omega = \intint16^2$। मान लीजिए $A = {}$ “पहला पासा सम” और $B = {}$ “दूसरा पासा कम से कम $5$” है। गिनने पर: $\abs A = 3\cdot6 = 18$, $\abs B = 6\cdot2 = 12$, $\abs{A\cap B} = 3\cdot2 = 6$, अतः

अर्थात् स्वतंत्र, और तंत्र दिख भी रहा है — $A$ केवल पहले निर्देशांक को बाँधता है, $B$ केवल दूसरे को, और किसी गुणनफल समुच्चय पर एकसमान माप निर्देशांक-गणनाओं को गुणित कर देता है। “असंयुक्त उछाल-समूहों पर निर्भर घटनाएँ स्वतंत्र हैं” प्रकार का हर दावा (जिसका सप्ताहांत समस्या में भारी उपयोग होता है) यही परिकलन है, बस अधिक सूचकांक पहने हुए।

उदाहरण 21.8 (संघ परिबंध: कच्चा, पर अटूट)

परिमित रूप से कई घटनाओं के साथ उप-योज्यता — अर्थात् संघ परिबंध — परिशुद्धता देकर सार्वभौमिकता ख़रीद लेती है। $23$ व्यक्तियों वाली जन्मदिन समस्या में टकराव की प्रायिकता को युग्मों पर योग से परिबद्ध करने पर सच्चे $0.507$ के सामने

मिलता है: काफ़ी दूर, क्योंकि टकराव आपस में अतिव्यापी होते हैं। फिर भी इस परिबंध को कोई स्वतंत्रता नहीं चाहिए, न कोई संयुक्त नियम, केवल युग्म-प्रायिकताएँ — और इसीलिए सप्ताहांत समस्या में तथा अध्याय 22 भर संघ परिबंध सबसे पहले निकाला जाने वाला औज़ार है: जब वह संयोग से छोटा निकल आए, तब बात बिना किसी और प्रतिरूपण के तय हो जाती है।

उदाहरण 21.15 (जन्मदिन का टकराव, शृंखला नियम से)

$n$ व्यक्तियों के जन्मदिन, जो स्वतंत्र हैं और $365$ दिनों पर एकसमान, लेकर मान लीजिए $D_n = {}$ “$n$ जन्मदिन सब अलग-अलग हैं” है। व्यक्ति दर व्यक्ति प्रतिबंधन (शृंखला नियम):

जहाँ हर नए व्यक्ति को पहले से लिए गए $k$ दिनों से बचना पड़ता है। $n = 23$ के लिए: $\P(D_{23}) \approx 0.493$ — अर्थात् साझा जन्मदिन पहले ही न होने से अधिक संभावित है। $23$ के छोटेपन को समझाने वाला अंतर्ज्ञान: लघुगणक लेने पर $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$, और $\binom{23}2 = 253$ $253/365 \approx 0.693 \approx \ln 2$ दे देता है। जो मायने रखता है वह युग्मों की संख्या है, जो वर्गिक रूप से बढ़ती है: टकराव की समस्याएँ मापक्रम $n \sim \sqrt{365}$ पर जीती हैं, $n \sim 365$ पर नहीं — जन्मदिन का विरोधाभास भेस बदला हुआ वर्गमूल है।

उदाहरण 22.7 (जन्मदिन समस्या, ईमानदारी से)

$N = 365$ दिनों पर स्वतंत्र, एकसमान जन्मदिनों वाले $n$ व्यक्तियों में सभी जन्मदिनों के भिन्न होने की प्रायिकता पुनरावृत्त सप्रतिबंधन से

है (अथवा सीधे: कुल $N^n$ में से अनुकूल $N(N-1)\cdots(N - n + 1)$, और स्वातंत्र्य का गुणनफल सूत्र इस गणना-तर्क को कठोर बना देता है)। लघुगणक लेकर और $-\ln(1 - x) = x + O(x^2)$ का उपयोग करके:

पलटाव बिंदु $p_n = \frac12$ $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$ पर बैठता है: $N = 365$ के लिए $n = 23$ ($p_{23} = 0.4927$)। दो शिक्षाएँ। पहली, $N$ पेटियों में $n$ वस्तुओं के बीच टकराव $n \sim \sqrt N$ के मापक्रम पर प्रकट होते हैं, न कि $n \sim N$ पर — यही वह जन्मदिन मापन है जो हैश टकरावों को और कूटलेखन में जन्मदिन आक्रमणों की $\sqrt N$ लागत को नियंत्रित करता है। दूसरी, यह परिकलन एक प्रतिमान है: $\binom n2$ युग्म-टकराव घटनाएँ स्वतंत्र नहीं हैं, फिर भी उत्तर ऐसे व्यवहार करता है मानो वे स्वतंत्र हों ($\eu^{-\binom n2/N}$ ठीक-ठीक स्वतंत्र-युग्मों वाली अनुमान-विधि है) — यह प्वासों आसन्नन का पहला उदाहरण है, जिसे अध्याय 23 की सप्ताहांत समस्या में कठोर बनाया गया है (ले काम असमिका)।

उदाहरण 22.14 (प्रबल नियम से क्या मिलता है)

(क) आवृत्तियाँ: स्वतंत्र सम-बंटित सिक्का-उछालों के लिए चित की प्रेक्षित आवृत्ति लगभग निश्चित रूप से $p$ की ओर अभिसरित होती है — अर्थात् स्वयं प्रायिकता का आनुभविक औचित्य। (ख) मोंते कार्लो: $g \in L^1(\intcc01)$ और स्वतंत्र सम-बंटित एकसमान $(U_n)$ (प्रमेय 22.6) के लिए लगभग निश्चित रूप से $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$: अर्थात् प्रतिचयन से समाकल, किसी भी विमा में, अध्याय 23 में परिशुद्ध की गई विमा-निरपेक्ष दर $\sim n^{-1/2}$ पर। (ग) सामान्य संख्याएँ: लगभग प्रत्येक वास्तविक संख्या के द्विआधारी प्रसार में एकों की अनंतस्पर्शी आवृत्ति $\frac12$ होती है (प्रमेय 22.6 के अंक चरों पर प्रबल नियम लगाइए) — यह बोरेल की प्रमेय है, जो रोज़मर्रा की संख्याओं के बारे में एक कथन है और माप से सिद्ध होता है: समस्या 22.1 उसे सभी आधारों में पूरा कर देता है।