ความน่าจะเป็นของการทำลายล้างของนักพนันที่ยุติธรรม
ฉันกำลังดูรูปแบบต่อไปนี้ของปัญหาความพินาศของนักพนันที่ยุติธรรม: นักพนันเริ่มต้นด้วย 1 ดอลลาร์ พวกเขาพลิกเหรียญที่ยุติธรรมซ้ำ ๆ หัว +1 ดอลลาร์; หาง -1 ดอล. เกมจะหยุดเมื่อนักพนันถึง 0 ดอลลาร์
เป็นที่ทราบกันดีว่าเกมจบลงด้วยความน่าจะเป็น 1 และเวลาเฉลี่ยที่เกมจะจบลงนั้นไม่มีที่สิ้นสุด
ฉันสนใจคำถามต่อไปนี้: อะไรคือความน่าจะเป็น (asymptotic) ที่เกมยังไม่จบ $n$ พลิก?
จากการโต้แย้งแบบฮิวริสติกฉันค่อนข้างมั่นใจว่าคำตอบคือ $\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}}\ . $$การพิสูจน์สำนวนแรกนั้นตรงไปตรงมามากกว่าที่ฉันคาดไว้ในตอนแรก การประมาณแบบ asymptotic มาจากนิพจน์ asymptotic ที่รู้จักกันดีสำหรับสัมประสิทธิ์ทวินามกลาง:\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}\ , $$ ตามที่ระบุไว้ข้างต้น.