Fair gambler's ruin tail probability I'm looking at the following variant of the fair gambler's ruin problem: The gambler starts with 1 dollar. They repeatedly flip a fair coin. Heads, +1 dollar; Tails -1 dollar. The game stops when the gambler reaches 0 dollars.
It is well known that the game ends with probability 1, and that the mean time for the game to end is infinite.
I am interested in the following question: What is the (asymptotic) probability that the game is not yet over after $n$ flips?
From a heuristic argument, I'm fairly certain that the answer is $\theta(1/\sqrt{n})$. From simulation, it appears that the answer is about $0.8/\sqrt{n}$.
I'd like to know the exact answer, and I'd like to know how to derive it analytically. At least, I'd like to know how to prove that the probability is $\theta(1/\sqrt{n})$. I'm guessing the proof involves a martingale, but I can't find it myself.
 A: The exact probability that the game has not ended after the $\ n^\text{th}\ $ toss is
$$
\frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ .
$$
The proof of the first expression turns out to be more straightforward than I had initially expected.  The asymptotic approximation follows from the well known asymptotic expressions for the central binomial coefficients:
\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}
For $\ i\ge1\ $ let $\ p_{in}\ $ be the probability that the player has $\ i\ $ dollars after the $\ n^\text{th}\ $ toss, and let $\ p_{0n}\ $ be the probability the game ends on or before the $\ n^\text{th}\ $ toss.  Then
\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}
To simplify the calculation, let $\ T_{nj}=2^{n+j}p_{n+1-j\,n+j}\ $ for $\ 0\le j<n\ $. Then
\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}
It follows from the last of these identities that
$$
T_{nk}=\sum_{j=0}^kT_{n-1\,j}\ .
$$
The numbers $\ T_{nj}\ $ are the entries in Catalan's triangle. The numbers $\ T_{nn}\ $ along the diagonal are the Catalan numbers,
$$
T_{nn}=\frac{2n\choose n}{n+1}\ ,
$$
from which we obtain
\begin{align}
p_{1\,2n}&=\frac{T_{nn}}{2^{2n}}\\
&= \frac{2n\choose n}{(n+1)2^{2n}}\ .
\end{align}
From the recurrence for $\ p_{in}\ $ we also get $\ p_{1\,2n+1}=p_{2\,2n}=0\ $ and
\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}
It can be verified by induction that the solution of this recurrence is
\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}
Now $\ p_{0n}\ $ is the probability that after the $\ n^\text{th}\ $ toss the game has ended, so the probability that the game has not ended after the $\ n^\text{th}\ $ toss is
$$
1-p_{0\,n}= \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\ ,
$$
as stated above.
