공정한 도박꾼의 파멸 꼬리 확률
나는 공정한 도박꾼의 파멸 문제의 다음과 같은 변형을보고 있습니다. 도박꾼은 1 달러로 시작합니다. 그들은 공정한 동전을 반복해서 던집니다. 앞면, +1 달러; 꼬리 -1 달러. 도박꾼이 0 달러에 도달하면 게임이 중지됩니다.
게임이 확률 1로 끝나고 게임이 끝나는 평균 시간이 무한하다는 것은 잘 알려져 있습니다.
다음 질문에 관심이 있습니다. 게임이 아직 끝나지 않은 (점근 적) 확률은 얼마입니까? $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}}\ . $$첫 번째 표현의 증명은 제가 처음에 예상했던 것보다 더 간단합니다. 점근 적 근사는 중앙 이항 계수에 대한 잘 알려진 점근 적 표현을 따릅니다.\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}\ , $$ 상술 한 바와 같이.