Kemungkinan kehancuran ekor penjudi yang adil
Saya melihat varian berikut dari masalah kehancuran penjudi adil: Penjudi mulai dengan 1 dolar. Mereka berulang kali melempar koin yang adil. Kepala, +1 dolar; Ekor -1 dolar. Permainan berhenti ketika penjudi mencapai 0 dolar.
Diketahui dengan baik bahwa permainan berakhir dengan probabilitas 1, dan bahwa waktu rata-rata untuk permainan berakhir tidak terbatas.
Saya tertarik dengan pertanyaan berikut: Berapa probabilitas (asimtotik) bahwa permainan belum berakhir setelahnya $n$ membalik?
Dari argumen heuristik, saya cukup yakin bahwa jawabannya adalah $\theta(1/\sqrt{n})$. Dari simulasi terlihat bahwa jawabannya adalah tentang$0.8/\sqrt{n}$.
Saya ingin tahu jawaban pastinya, dan saya ingin tahu bagaimana memperolehnya secara analitis. Setidaknya, saya ingin tahu bagaimana membuktikan bahwa kemungkinannya adalah$\theta(1/\sqrt{n})$. Saya menduga buktinya melibatkan martingale, tetapi saya tidak dapat menemukannya sendiri.
Jawaban
Kemungkinan pasti bahwa permainan belum berakhir setelah $\ n^\text{th}\ $ lemparan adalah $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$Bukti ekspresi pertama ternyata lebih lugas dari yang saya duga sebelumnya. Perkiraan asimtotik mengikuti ekspresi asimtotik terkenal untuk koefisien binomial pusat:\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} Untuk $\ i\ge1\ $ membiarkan $\ p_{in}\ $ menjadi probabilitas yang dimiliki pemain $\ i\ $ dolar setelah $\ n^\text{th}\ $ lempar, dan biarkan $\ p_{0n}\ $ menjadi probabilitas permainan berakhir pada atau sebelum $\ n^\text{th}\ $melemparkan. Kemudian\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} Untuk menyederhanakan perhitungan, biarkan $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ untuk $\ 0\le j<n\ $. Kemudian\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} Ini mengikuti dari identitas terakhir itu $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ Angka-angka $\ T_{nj}\ $adalah entri dalam segitiga Catalan . Angka-angka$\ T_{nn}\ $sepanjang diagonal adalah nomor Catalan ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ dari mana kami memperoleh \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} Dari pengulangan selama $\ p_{in}\ $ kami juga mendapatkan $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ dan \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} Dapat dibuktikan dengan induksi bahwa solusi dari pengulangan ini adalah \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} Sekarang $\ p_{0n}\ $ adalah probabilitas setelah $\ n^\text{th}\ $melempar permainan telah berakhir, jadi kemungkinan permainan belum berakhir setelah$\ n^\text{th}\ $ lemparan adalah $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ sebagaimana disebutkan di atas.