Probability with Infinite Coins A player is blindfolded and picks coins from a bag. There are two types of coins: black and white. There is no bias in the player’s picking, there are an infinite amount of coins and there is a perfect 50/50 chance of picking either.
Imagine the player has a score, which starts at 0. Should they pick a white coin, the score will go up by one (+1). Should the player pick a black coin, the score will go down by one (-1). Should the player’s score go beneath 0, the game will end. Each time the player picks a coin, a turn has passed (i.e. turn one is the first coin picked).
My question is: can you calculate the chances of the player reaching $n$ turns in terms of $n$? 
 A: By a flip sequence of length $k$, we mean a $k$-term sequence where each term is $+1$ or $-1$. The score of a flip sequence is just the sum of its terms. By a proper initial subsequence of a flip sequence, we mean a subsequence of consecutive terms starting with the first term, and ending before the last.

For each nonnegative integer $m$, let


*

*$A(m)$ be the set of flip sequences of length $2m+1$ with score $-1$ such that all proper initial subsequences have nonnegative scores, and let $a(m)=|A(m)|$.$\\[4pt]$

*$B(m)$ be the set of flip sequences of length $2m$ with score $0$ such that all proper initial subsequences have positive scores, and let $b(m)=|B(m)|$.$\\[4pt]$

*$C(m)$ be the set of flip sequences of length $2m$ with score $0$ such that all proper initial subsequences have nonnegative scores, and let $c(m)=|C(m)|$.


There are obvious one-to-one correspondences between $A(m)$ and $B(m+1)$, and between $A(m)$ and $C(m)$, hence for all nonnegative integers $m$, we have
$a(m)=b(m+1)$ and $a(m)=c(m)$.

For $c(m)$, we have the initial value $c(0)=1$, and for $m\ge 1$, we have
\begin{align*}
c(m)&=\sum_{k=1}^{m}b(k)c(m-k)\\[4pt]
&=\sum_{k=1}^{m}a(k-1)c(m-k)\\[4pt]
&=\sum_{k=1}^{m}c(k-1)c(m-k)\\[4pt]
&=\sum_{k=0}^{m-1}c(k)c((m-1)-k)\\[4pt]
\end{align*}
Thus, for all nonnegative integers $m$, we have
$$
c(m+1)=\sum_{k=0}^m c(k)c(m-k)
\qquad\qquad\;
$$
which matches the recursion for the Catalan numbers.

Hence for all nonnegative integers $m$, we have
$$
c(m)=\frac{1}{m+1}\binom{2m}{m}
\qquad\qquad\;\;\;
$$

Next consider probabilities . . .

For each positive integer $n$, let 


*

*$p(n)$ be the probability that a random flip sequence of length $n$ corresponds to a game which ends after exactly $n$ flips.

*$q(n)$ be the probability that a random flip sequence of length $n$ corresponds to a game which hasn't yet ended.


First let's compute $p(n)$ . . .

If $n$ is even, we have $p(n)=0$, and if $n$ is odd, we have
\begin{align*}
p(n)&=\frac{a(m)}{2^{n}}
\qquad\qquad\qquad\qquad
\\[4pt]
&=\frac{c(m)}{2^{n}}\\[4pt]
&=
\frac
{\large{
\frac{1}{m+1}\binom{2m}{m}
}}
{2^{n}}\\[4pt]
&\;\text{where}\;\;m={\small{\frac{n-1}{2}}}\\[4pt]
\end{align*}
In particular, for odd $n$ with $1 \le n \le 19$, we get
$$
\begin{array}
{
|c|
c|c|c|c|c|c|c|c|c|c|
} 
\hline
n 
& 1 
& 3 
& 5 
& 7 
& 9 
& 11 
& 13
& 15
& 17
& 19
\\ 
\hline
p(n) 
& {\Large{\frac{1}{2^1}}}
& {\Large{\frac{1}{2^3}}}
& {\Large{\frac{2}{2^5}}}
& {\Large{\frac{5}{2^7}}}
& {\Large{\frac{14}{2^9}}}
& {\Large{\frac{42}{2^{11}}}}
& {\Large{\frac{132}{2^{13}}}}
& {\Large{\frac{429}{2^{15}}}}
& {\Large{\frac{1430}{2^{17}}}}
& {\Large{\frac{4862}{2^{19}}}}
\\
\hline
\end{array}
$$
Next let's compute $q(n)$ . . .

Clearly, we have $q(0)=1$.

Since games can only end after an odd number of flips, it follows that for all even $n > 0$, we have $q(n)=q(n-1)$.

If $n$ is an odd positive integer, then
$$q(n)=1-\left(\sum_{m=0}^{{\large{\frac{n-1}{2}}}}p(2m+1)\right)$$
hence for all odd positive integers, we have
$$
q(n+2)=q(n)-p(n+2)
\qquad\qquad\;\;\;\;
$$
By a straightforward induction, it follows that for all odd positive integers $n$, we have
$$
q(n)=
{\large{\frac
{\large{
\binom{n}{m}
}}
{2^{n}}
}}
,\;\,\text{where}\;\,m={\small{\frac{n-1}{2}}}
$$
In particular, for odd $n$ with $1 \le n \le 19$, we get
$$
\begin{array}
{
|c|
c|c|c|c|c|c|c|c|c|c|
} 
\hline
n 
& 1 
& 3 
& 5 
& 7 
& 9 
& 11 
& 13
& 15
& 17
& 19
\\ 
\hline
q(n) 
& {\Large{\frac{1}{2^1}}}
& {\Large{\frac{3}{2^3}}}
& {\Large{\frac{10}{2^5}}}
& {\Large{\frac{35}{2^7}}}
& {\Large{\frac{126}{2^9}}}
& {\Large{\frac{462}{2^{11}}}}
& {\Large{\frac{1716}{2^{13}}}}
& {\Large{\frac{6435}{2^{15}}}}
& {\Large{\frac{24310}{2^{17}}}}
& {\Large{\frac{92378}{2^{19}}}}
\\
\hline
\end{array}
$$
