Xác suất hỏng đuôi của người đánh bạc công bằng
Tôi đang xem xét biến thể sau đây của vấn đề phá hoại của người đánh bạc công bằng: Người đánh bạc bắt đầu với 1 đô la. Họ liên tục lật một đồng xu công bằng. Thủ trưởng, +1 đô la; Tails -1 đô la. Trò chơi dừng khi con bạc đạt 0 đô la.
Ai cũng biết rằng trò chơi kết thúc với xác suất 1 và thời gian trung bình để trò chơi kết thúc là vô hạn.
Tôi quan tâm đến câu hỏi sau: Xác suất (tiệm cận) mà trò chơi vẫn chưa kết thúc sau đó là bao nhiêu $n$ lật?
Từ một lập luận heuristic, tôi khá chắc chắn rằng câu trả lời là $\theta(1/\sqrt{n})$. Từ mô phỏng, có vẻ như câu trả lời là về$0.8/\sqrt{n}$.
Tôi muốn biết câu trả lời chính xác, và tôi muốn biết cách phân tích nó. Ít nhất, tôi muốn biết cách chứng minh rằng xác suất là$\theta(1/\sqrt{n})$. Tôi đoán rằng bằng chứng liên quan đến một martingale, nhưng tôi không thể tự tìm ra nó.
Trả lời
Xác suất chính xác mà trò chơi vẫn chưa kết thúc sau $\ n^\text{th}\ $ quăng là $$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$Bằng chứng của biểu thức đầu tiên hóa ra đơn giản hơn tôi mong đợi ban đầu. Phép gần đúng tiệm cận sau từ các biểu thức tiệm cận nổi tiếng cho các hệ số nhị thức trung tâm:\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 với $\ i\ge1\ $ để cho $\ p_{in}\ $ là xác suất mà người chơi có $\ i\ $ đô la sau $\ n^\text{th}\ $ quăng, và để $\ p_{0n}\ $ là xác suất trò chơi kết thúc vào hoặc trước $\ n^\text{th}\ $quăng. Sau đó\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} Để đơn giản hóa việc tính toán, hãy $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ cho $\ 0\le j<n\ $. Sau đó\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} Nó theo sau từ danh tính cuối cùng $$ T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ . $$ Những con số $\ T_{nj}\ $là các mục trong tam giác Catalan . Những con số$\ T_{nn}\ $dọc theo đường chéo là các số Catalan ,$$ T_{nn}=\frac{2n\choose n}{n+1}\ , $$ từ đó chúng tôi có được \begin{align} p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\ &= \frac{2n\choose n}{(n+1)2^{2n}}\ . \end{align} Từ sự lặp lại cho $\ p_{in}\ $ chúng tôi cũng nhận được $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ và \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} Có thể xác minh bằng cách quy nạp rằng giải pháp của sự tái diễn này là \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} Hiện nay $\ p_{0n}\ $ là xác suất mà sau $\ n^\text{th}\ $trò chơi ném đã kết thúc, vì vậy xác suất trò chơi vẫn chưa kết thúc sau khi$\ n^\text{th}\ $ quăng là $$ 1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ , $$ như đã nêu ở trên.