Вероятность разорения честного игрока
Я рассматриваю следующий вариант проблемы разорения честного игрока: игрок начинает с 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}\ , $$ как указано выше.