公正なギャンブラーの破滅の尾の確率
私は公正なギャンブラーの破滅問題の次の変種を見ています：ギャンブラーは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}\ , $$ 上記のように。