Suppose we have a particle whose position is confined to the points of $\mathbb{Z}$ and suppose the particle starts at $x=0$. At each step, there is $1/2$ probability that the particle jumps to the left and $1/2$ probability that the particle jumps to the right. This creates a 1D random walk.
To put it another way, we have a sequence $a_{1}, a_{2}, a_{3}, \ldots\in \{-1, +1\}$ where for each $i$, we have $a_{i} = +1$ with $1/2$ probability and $a_{i}=-1$ with $1/2$ probability. This generates another sequence $x_{0}, x_{1}, x_{2}, x_{3}, \ldots\in\mathbb{Z}$ by $x_{n} = \sum_{i=1}^{n} a_{i}$.
My question is, is it the case that for any positive integer $M$, it almost surely guaranteed that there exist $m, n > 0$ such that $$ x_{m} < -M \qquad\text{ and }\qquad x_{n} > M? $$ My intuition for this conjecture is that if a particle really is doing a random walk, it should eventually wander off arbitrarily far to the right and eventually wander off arbitrarily far to the left. Am I correct in this intuition? If so, how can I prove this rigorously?
Yes. Let $N \in \mathbb{N}$ be arbitrary. We aim to show that for every $x \in \{1, \dots, N - 1\}$, $E_x(V_{\{0, N\}}) < \infty$, where for $A \subset \mathbb{N}$ we define $V_A = \inf\{n \geq 0 : X_n \in A\}$. This is a stronger statement than $P_x(V_{\{0, N\}} < \infty) = 1$ since in general, if $Y \geq 0$, then $E(Y) < \infty \implies P(Y = \infty) = 0$. First note that for any $x \in \{1, \dots, N - 1\}$, there is a path from $x$ to $\{0, N\}$ of length at most $N$, so $P_x(V_{\{0, N\}} > N) \leq 1 - 2^{-N}$. Then using a standard Markov property argument, we can deduce that for every integer $k \geq 1$, $P_x(V_{\{0, N\}} > kN) \leq (1 - 2^{-N})^k$. Using this tail bound it is easy to prove that $$E_x(V_{\{0, N\}}) = \sum_{n = 0}^{\infty}P_x(V_{\{0, N\}} > n) < \infty.$$
Knowing that this expectation is finite, we can even compute it explicitly: Let $f(x) = E_x(V_{\{0, N\}})$ be the expected time that the chain starting at $x$ hits $\{0, N\}$. Conditioning on the first step and using the Markov property yields that for $x \in \{1, \dots, N - 1\}$. $$f(x) = \frac{1}{2}(1 + f(x - 1)) + \frac{1}{2}(1 + f(x + 1)).$$ The initial conditions are $f(0) = f(N) = 0$. This kind of recurrence can be solved mechanically. The solution is $f(x) = x(N - x)$.