निष्पक्ष जुआरी की बर्बादी की संभावना
मैं निष्पक्ष जुआरी की बर्बादी समस्या के निम्नलिखित प्रकार को देख रहा हूं: जुआरी 1 डॉलर से शुरू होता है। वे बार-बार एक उचित सिक्का फ्लिप करते हैं। प्रमुख, +1 डॉलर; पूंछ -1 डॉलर। जुआरी 0 डॉलर तक पहुंचने पर खेल बंद हो जाता है।
यह सर्वविदित है कि खेल संभावना 1 के साथ समाप्त होता है, और खेल समाप्त होने का औसत समय अनंत है।
मैं निम्नलिखित प्रश्न में रुचि रखता हूं: (asymptotic) संभावना क्या है कि खेल अभी खत्म नहीं हुआ है $n$ flips?
एक तर्कवादी तर्क से, मैं काफी हद तक निश्चित हूं कि इसका उत्तर है $\theta(1/\sqrt{n})$। सिमुलेशन से, यह प्रतीत होता है कि उत्तर के बारे में है$0.8/\sqrt{n}$।
मैं सटीक उत्तर जानना चाहता हूं, और मैं जानना चाहता हूं कि इसे विश्लेषणात्मक रूप से कैसे प्राप्त किया जाए। कम से कम, मैं जानना चाहता हूं कि कैसे साबित किया जाए कि संभावना है$\theta(1/\sqrt{n})$। मैं अनुमान लगा रहा हूं कि प्रमाण में एक मार्टिंगेल शामिल है, लेकिन मैं इसे स्वयं नहीं ढूंढ सकता।
जवाब
खेल के बाद खेल खत्म नहीं हुआ है कि सटीक संभावना $\ n^\text{th}\ $ टॉस है $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$पहली अभिव्यक्ति का प्रमाण मुझे पहले की अपेक्षा अधिक सीधा लगता है। मध्य द्विपद गुणांक के लिए प्रसिद्ध असममित अभिव्यक्तियों से स्पर्शोन्मुख सन्निकटन इस प्रकार है:\begin{align} {2n\choose n}&\sim\frac{4^n}{\sqrt{\pi n}}=2^{2n}\sqrt{\frac{2}{2n\pi}}\\ {2n+1\choose n}&={2n+1\choose n+1}\sim\frac{2^{2n+1}}{\sqrt{\pi(n+1)}}\\ &=2^{2n+1}\sqrt{\frac{2}{\pi(2n+1)}}\sqrt{1-\frac{1}{2n+2}}\ . \end{align} के लिये $\ i\ge1\ $ लश्कर $\ p_{in}\ $ संभावना है कि खिलाड़ी है $\ i\ $ डॉलर के बाद $\ n^\text{th}\ $ टॉस, और चलो $\ p_{0n}\ $ संभावना है कि खेल पर या उससे पहले समाप्त होता है $\ n^\text{th}\ $टॉस। फिर\begin{align} p_{n+1\,n}&=\frac{1}{2^n}\ ,\\ p_{n\,n}&=0\ ,\\ p_{0\,n}&= p_{0\,n-1}+\frac{p_{1\,n-1}}{2}\ ,\\ p_{1\,n}&= \frac{p_{2\,n-1}}{2}\ , \text{ and}\\ p_{i\,n}&= \frac{p_{i+1\,n-1}+p_{i-1\,n-1}}{2}\ \text{ for }\ i\ge2\ . \end{align} गणना को सरल बनाने के लिए, आइए $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ के लिये $\ 0\le j<n\ $। फिर\begin{align} T_{n0}&=1\ ,\\ T_{11}&=1\ ,\text{ and}\\ T_{nj}&=T_{n\,j-1}+T_{n-1\,j}\ \text{ for }\ 1\le j\le n\ . \end{align} यह इन पहचानों में से अंतिम है $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ संख्याएँ $\ T_{nj}\ $कैटलन के त्रिकोण में प्रविष्टियां हैं । संख्याएँ$\ T_{nn}\ $विकर्ण के साथ कैटलन संख्याएं हैं ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ जिससे हम प्राप्त करते हैं \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} के लिए पुनरावृत्ति से $\ p_{in}\ $ हमें भी मिलता है $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ तथा \begin{align} p_{0\,2n}&=p_{0\,2n-1}\\ &=p_{0\,2n-2}+\frac{p_{1\,2n-2}}{2}\\ &= p_{0\,2n-2}+\frac{2n-2\choose n-1}{n2^{2n-1}} \end{align} यह प्रेरण द्वारा सत्यापित किया जा सकता है कि इस पुनरावृत्ति का समाधान है \begin{align} p_{0\,2n}&=1-\frac{2n\choose n}{2^{2n}}\\ &=1-\frac{2n-1\choose n-1}{2^{2n-1}}\\ &=p_{0\,2n-1}\ . \end{align} अभी $\ p_{0n}\ $ संभावना है कि के बाद है $\ n^\text{th}\ $टॉस खेल समाप्त हो गया है, इसलिए संभावना है कि खेल के बाद खेल समाप्त नहीं हुआ है$\ n^\text{th}\ $ टॉस है $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ जैसा की ऊपर कहा गया है।