TITLE: Does this game make you arbitrarily rich with probability one?
QUESTION [1 upvotes]: We toss a coin. If it's heads we win $\$ 1$, otherwise we lose $ \$ 1$. Fix some large sum. Will we be winning this amount with probability one at some point? We assume that we have infinitely many throws and an infinite amount of money.
More formally (please correct me if if there are errors). Consider the following Markov process: $$X_{i+1} = X_{i}+d_i,$$
where each $d_i$ is a random variable taking values 1 and -1 with an equal probability (if $i \neq j$ $d_i$ and $d_j$ are independent). Let $M \in \mathbb{Z}_+$ and define a Markov time $$\tau_M = \min \left\{ i \: \middle| \: X_i = M \right\}.$$
Is it true that $$ P(\tau_M < \infty ) = 1$$
for all $M$?
I'd guess it's true and that there is a simple proof. Are there some canonical ways of dealing with these type of questions? Not a homework, something I just thought about.

REPLY [0 votes]: Let we say that a sequence of $2n$ throws is balanced if at any point we are not winning any dollar, but with the last throw we are losing zero. It is well-known that the number of balanced sequences of length $2n$ is given by the Catalan number:
$$ C_n = \frac{1}{n+1}\binom{2n}{n}. $$
If we say that a sequence of $2n$ throws is returning if at any point we are losing a positive amount of dollars, but with the last throw we are losing zero, then the number of returning sequences of length $2n$ is given by:
$$ R_n = \frac{1}{n}\binom{2n-2}{n-1} \geq \frac{2^{2n}}{4\sqrt{\pi} \left(n-\frac{1}{4}\right)^{3/2}},$$
so the probability to be winning $k$ dollars at some time is greater than:
$$ \frac{1}{2^k}\sum_{n=1}^{+\infty}\frac{1}{4\sqrt{\pi}\left(n-\frac{1}{4}\right)^{3/2}}\geq \frac{13}{28\cdot 2^k}.$$
Since $$\sum_{n\geq 1}R_n z^n = \frac{1-\sqrt{1-4z}}{2}$$
by evaluating the RHS at $z=\frac{1}{4}$ we have that any losing streak ends with probability $1$, as well as any winning streak. That gives that we go back to the original configuration with probability $1$, so the "zero money" state is a recurring state for our random walk, as well as any other state, since the probability that we may go on playing forever without winning or losing more than $k$ dollars is clearly zero.
{"set_name": "stack_exchange", "score": 1, "question_id": 1408031}