0

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?

Kevinlove
  • 171
  • @angryavian: In the original post, it looks like there is a $0.5$ chance of moving forward $1$ step, and a $0.5$ chance of going all the way back to $0$ (on any given step of the process, other than when the position is $0$). – paw88789 Dec 18 '23 at 16:18
  • 1
    @paw88789 Yes, that is exactly what I meant. 0.5 to move forward and 0.5 to go all the way back – Kevinlove Dec 18 '23 at 16:21
  • @kevinlove I believe that is not usually called a simple random walk. In a simple random walk, I think you only go one step per move. https://en.wikipedia.org/wiki/Random_walk#:~:text=In%20a%20simple%20random%20walk,immediate%20neighbors%20are%20the%20same. – paw88789 Dec 18 '23 at 16:25
  • Why is it $\frac{1}{2^n}$ and not $\frac{1}{2^{499999}}$? By your method it would appear we would get to $\frac{1}{500000}$ for $X_{n-500000}$ except when $X_i = 0$ we always step forward one so we don’t divide by two in the last step unless i misunderstand your process? – Robert Murray Dec 18 '23 at 16:38
  • @RobertMurray yes, you are right actually. I fixed it – Kevinlove Dec 18 '23 at 17:04

3 Answers3

1

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.]

paw88789
  • 40,402
  • it specifies in a finite number of trials, a geometric distribution has the probability of success being at 1 for an infinite number of trials. – Robert Murray Dec 18 '23 at 16:47
  • @RobertMurray I respectfully disagree. The probability of needing infinitely many trials to get a success is $0$. (It's one of those cases where a theoretically possible thing has probability $0$). For a simpler case, what is the probability that in flipping a fair coin, you eventually get heads? Answer: 1 (even though conceptually you might never get heads). The event of an infinite string of tails is possible, but has probability $0$. – paw88789 Dec 18 '23 at 17:05
  • In my mind: Let $Y \thicksim Geo(p)$. $\mathbb{P}(G > n) = (1-p)^n$. For finite n, this number is calculable and finite. However, $\lim_{n \rightarrow \infty} (1-p)^n = 0$. In other words, the odds of us needing more than n trials for a finite n is a non-zero number. The odds of us needing more than n trials for a finite n is zero. Not saying you're incorrect but you need to prove that the probabilities for finite and infinite are the same. – Robert Murray Dec 18 '23 at 17:10
  • @paw88789 Thank you for your answer. I am not sure why Formally the probability of never getting a success is 0. Intuitively its obvious, but why formally the geometric random variable being with a positive probability of success on any given trial means that the probability of never getting a success is 0? I am pretty new to this subject, sorry if its a "stupid" question – Kevinlove Dec 18 '23 at 17:10
  • @Kevinlove Because the sum of the probabilities of getting a success on the $n$th trial add up to $1$ as $n\to\infty$. It's a situation where a possible event (never getting to $500000$ in your situation) has probability $0$. – paw88789 Dec 18 '23 at 17:15
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.

Robert Murray
  • 1,788
0

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.

tomasz
  • 35,474
  • Thank you for your comment. This is a nice way to look at the random walk! I understood that the probability of having 50000 heads in a row is positive ( small however, but positive ), but i am not sure how formally i can conclude from here that in the end, after enough coin throws, ill get this exact sequence. If you could expand a bit more about the formal way of this conclusion, it would be much appreciated. Thank you! – Kevinlove Dec 18 '23 at 17:19
  • @Kevinlove: The point is that it is not just positive, it is equal to $1$. Consider $\bigcap_nA_n$. – tomasz Dec 18 '23 at 21:43