random walk on $\mathbb{N}$

Question

Consider a simple random walk on $\mathbb{N}$, defined as:

on any given step of the process there is a 0.5 chance of moving forward 1 step, and a 0.5 chance of going all the way back to 0.

find the probability that in finite amount of time, we will hit a.

help?

Answer 1

First, let $X_i$ be the position on our $i^{th}$ move of the random walk. Then, $\mathbb{P}(X_i = 500,000) = (\frac{1}{2})^{499999}$, as our first most is guaranteed upwards and every other one is a coin flip. Next, we consider $G \thicksim Geom((\frac{1}{2})^{499,999})$, and by the pmf of a geometric distribution we know that $$\mathbb{P}(G < n) = 1 - \mathbb{P}(G = n) - \mathbb{P}(G > n) = 1 - (1-p)^n - p(1-p)^{n-1}$$ Where $p = (\frac{1}{2})^{499999}$. We want a finite number of moves, so if we have $$\lim_{n \rightarrow \infty} \mathbb{P}(G < n) = \lim_{n \rightarrow \infty} 1 - (1-p)^n - p(1-p)^{n-1} = 1$$Would tell us the probability that $G < \infty$, meaning G is finite.

Answer 2

Starting at $0$, one of two things will occur:

(a) We will get to $50000$ without ever going back to $0$. The probability of this is $\frac{1}{2^{49999}}$ (not $\frac{1}{2^{50000}}$ because the first step to $1$ is automatic.) (We will call this result 'success'.)

(b) We will go back to $0$ before we get to $50000$. (We will call this result 'failure'.)

If we have a success, we are done. If we have a failure, we try again.

So we can conceptualize this process as a geometric random variable with probability of success being $\frac{1}{2^{49999}}$. The probability of never getting a success (with a geometric random variable with a positive probability of success on any given trial), is $0$.

So with probability $1$, we will have a success (i.e., get to $500000$).

[But don't try this at home, unless you are immortal.]

Answer 3

Another way to see this is to consider an infinite walk.

For simplicity, assume instead that when we are at $0$, we actually stay there with probability $\frac12$ and otherwise we move forward (this makes it slightly more difficult to reach $50000$ and simplifies the computation).

Instead of drawing the probability one at a time, take an infinite sequence of independent fair coin tosses and then just walk according to the pre-rolled sequence (say, we go ahead on heads, go back to/stay at $0$ on tails).

The only sequences which don't end up on $50000$ at some point are those which have no sequences of $50000$ heads in a row.

But in general, every sequence occurs with probability $1$.

To see this in this example, let $A_n$ be the event that there is a tail in places $50000n$ up to $50000(n+1)-1$ inclusive. The probability of this happening is $(1-2^{-50000})$. It follows easily from the assumptions that the $A_n$ are independent, which should quickly lead you to the conclusion.