प्रस्तावना: प्रायिकता सिद्धांत का सबसे अद्भुत चमत्कार
2003 में डेनिश कंप्यूटर वैज्ञानिक पीटर ब्रो मिल्टरसन (Peter Bro Miltersen) ने प्रसिद्ध 100 कैदियों की समस्या (100 Prisoners Problem) प्रस्तुत की:
- मृत्युदंड पाए $100$ कैदियों को $1$ से $100$ तक संख्या दी गई है। एक कमरे में $100$ बंद डिब्बे हैं जिनमें $1$ से $100$ तक की पर्चियां यादृच्छिक रूप से रखी हैं (एक क्रमचय $\sigma \in S_{100}$)।
- नियम: प्रत्येक कैदी बारी-बारी से अकेले कमरे में जाता है और अपनी संख्या खोजने के लिए अधिकतम $50$ डिब्बे खोल सकता है। बाहर आने पर कमरा पूर्ववत कर दिया जाता है और खेल शुरू होने के बाद किसी भी प्रकार का संवाद पूर्णतः वर्जित है (किंतु शुरू होने से पहले रणनीति तय की जा सकती है)।
- जीवन-मरण शर्त: यदि सभी $100$ कैदी अपनी संख्या खोज लेते हैं, तो सभी रिहा कर दिए जाते हैं; यदि एक भी विफल रहा, तो सभी $100$ को मृत्युदंड दिया जाता है।
यदि प्रत्येक कैदी यादृच्छिक रूप से $50$ डिब्बे खोलता है (स्वतंत्र रणनीति), तो प्रत्येक की सफलता प्रायिकता $1/2$ है, किंतु सभी के बचने की प्रायिकता नगण्य है:
$$\mathbb{P}(\text{सभी बचें})_{\text{स्वतंत्र}} = \left(\frac{1}{2}\right)^{100} \approx 7.89 \times 10^{-31}$$किंतु स्वेन स्कायुम (Sven Skyum) ने सूचक-अनुसरण रणनीति (Pointer-Following Strategy) खोजी, जो बिना एक भी बिट सूचना भेजे सामूहिक जीवन रक्षा प्रायिकता को $31.18\%$ तक पहुँचा देती है!
अध्याय 1: सूचक-अनुसरण रणनीति और असंयुक्त चक्र वियोजन
कैदी संख्या $k \in \{1, \dots, 100\}$ के लिए स्कायुम की रणनीति:
- चरण 1: सबसे पहले डिब्बा सं. $k$ खोलें।
- चरण 2: यदि अंदर की पर्ची $x_1 = k$ है, तो सफल; यदि $x_1 \neq k$, तो अगला डिब्बा सं. $x_1$ खोलें।
- चरण 3: नई संख्या $x_2$ पढ़ें और डिब्बा सं. $x_2$ खोलें, अर्थात् श्रृंखला $k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots$ का अनुसरण करें जब तक $k$ न मिल जाए या $50$ प्रयास समाप्त न हो जाएं।
flowchart TD
Start["कैदी k कमरे में प्रवेश करता है (अधिकतम 50 प्रयास)"]
Step1["चरण 1: डिब्बा k खोलें, पर्ची x = σ(k) पढ़ें"]
Check{"क्या पर्ची x == k ?"}
Win["अपनी संख्या k मिल गई!"]
Limit{"क्या खुले डिब्बे < 50 ?"}
Next["सूचक का अनुसरण: डिब्बा x खोलें (x ← σ(x))"]
Lose["50 चरणों में k नहीं मिला: सभी को मृत्युदंड"]
Start --> Step1 --> Check
Check -- "हाँ" --> Win
Check -- "नहीं" --> Limit
Limit -- "हाँ" --> Next --> Check
Limit -- "नहीं (चक्र की लंबाई ℓ > 50)" --> Lose
यह क्यों काम करता है? डिब्बा $\mapsto$ पर्ची प्रतिचित्रण सममित समूह $S_{2n}$ ($2n=100$) में एक एकैकी आच्छादक क्रमचय $\sigma$ है। प्रत्येक परिमित क्रमचय अद्वितीय रूप से असंयुक्त चक्रों (Disjoint Cycles) के गुणनफल में टूटता है:
$$\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100$$चूंकि $\sigma$ एकैकी आच्छादक है, डिब्बा $k$ से शुरू करने पर कैदी $k$ को समाहित करने वाले अद्वितीय बंद चक्र में घूमता हुआ अंततः $\sigma^{-1}(k)$ (जिस डिब्बे में पर्ची $k$ है) पर पहुँचता है। अतः:
- कैदी $k$ अधिकतम $50$ चरणों में तभी सफल होता है जब उसके चक्र की लंबाई $\ell \le 50$ हो।
- सभी $100$ कैदी तभी बचते हैं जब क्रमचय $\sigma \in S_{100}$ में लंबाई $\ell > 50$ का कोई भी चक्र न हो!
अध्याय 2: लंबे चक्रों की गणना और हरात्मक संख्याएं ($1 - \ln 2$)
$2n$ कैदियों ($n = 50$) के लिए, किसी क्रमचय $\sigma \in S_{2n}$ में लंबाई $\ell > n$ का अधिकतम एक ही चक्र हो सकता है, क्योंकि $> n$ लंबाई के दो असंयुक्त चक्रों के लिए कम से कम $2n+2 > 2n$ अवयव चाहिए। अतः घटनाएं $E_\ell := \{\sigma \text{ में लंबाई } \ell \text{ का चक्र है}\}$ ($\ell = n+1, \dots, 2n$) परस्पर अपवर्जी हैं! $E_\ell$ में क्रमचयों की संख्या:
- लंबे चक्र के लिए $\ell$ अवयव चुनना: $\binom{2n}{\ell}$;
- उन्हें एक वृत्तीय चक्र में सजाना: $(\ell - 1)!$;
- शेष $2n - \ell$ अवयवों का क्रमचय: $(2n - \ell)!$।
गुणा करने पर क्रमगुणित कट जाते हैं:
$$|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}$$$|S_{2n}| = (2n)!$ से भाग देने पर $\mathbb{P}(E_\ell) = \frac{1}{\ell}$ मिलता है। हरात्मक संख्याओं (Harmonic Numbers) $H_N = \sum_{k=1}^N \frac{1}{k}$ से बचने की सटीक प्रायिकता है:
$$\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30.685\%}$$$2n = 100$ के लिए $P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31.1828\%}$!
अध्याय 3: बिना सूचना प्रसारण के जोखिम युग्मन (Coupling)
flowchart TD
Pool["कुल जोखिम स्थिर: अपेक्षित विफलताएं E[विफल] = 50"]
Indep["स्वतंत्र रणनीति: लगभग सभी ब्रह्मांडों में विफलताएं बिखरी हैं"]
Cycle["चक्र रणनीति: σ की चक्र संरचना से भाग्य आपस में जुड़े हैं"]
ResI["99.99...92% ब्रह्मांडों में कम से कम 1 विफल → बचाव ≈ 7.89×10⁻³¹"]
ResC["68.82% (ℓ>50) में सभी विफलताएं केंद्रित → 31.18% ब्रह्मांडों में 100% सुरक्षित!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| विशेषता | 1. स्वतंत्र रणनीति | 2. चक्र-अनुसरण रणनीति |
|---|---|---|
| व्यक्तिगत सफलता $\mathbb{P}(A_k)$ | $50.00\%$ | $50.00\%$ (समान) |
| अपेक्षित सफल कैदी $\mathbb{E}[X]$ | $50$ कैदी | $50$ कैदी (समान) |
| सहसंबंध | शून्य (स्वतंत्र) | $\sigma$ के माध्यम से प्रबल धनात्मक युग्मन |
| सभी $100$ के बचने की प्रायिकता | $(1/2)^{100} \approx 7.89 \times 10^{-31}$ | $1 - (H_{100} - H_{50}) \approx 31.18\%$ |
| सीमा $n \to \infty$ | $0$ | $1 - \ln 2 \approx 30.685\%$ |
- युग्मन (Coupling): चूंकि 1 विफलता और 51 विफलताओं का दंड एक समान है, चक्र रणनीति सभी विफलताओं को $\ell > 50$ वाले $68.82\%$ क्रमचयों में समेट देती है, जिससे $31.18\%$ प्रतिदर्श समष्टि पूर्णतः विफलता-मुक्त हो जाती है!
- दुर्भावनापूर्ण जेलर से बचाव: पहले से एक गुप्त यादृच्छिक एकैकी आच्छादन $\tau \in S_{100}$ तय करने पर संयुग्मन $\tau \sigma \tau^{-1}$ पुनः $31.18\%$ सफलता सुनिश्चित करता है।