2

What is the probability that a simple 1d random walk is between (-k,k), exclusive, in 100 moves?

My initial though was: $1-\sum_{i=k}^{100}P_i$, where $P_i$ stands for the probability that it reaches $k$ in $i$ number of moves.

user334639
  • 363
  • 3
  • 6
  • for it to be between -k and +k, that means that , after 100 steps, the sum of the ups and downs has to be between -k and +k. So, you can sum the binomial pdf from -k to k. The resulting pdf is $\sum_{i=-k}^{i=+k} p^{i}(1-p)^{(100-i)}$ where $k \le 100$. – mlofton Aug 23 '22 at 03:55
  • Note that, in the above, $p = $ the probability of a +1. – mlofton Aug 23 '22 at 03:57
  • @mlofton that expression for the pdf is not entirely right. There needs to be an additional binomial coefficient in the expression of the mdf and the index $i$ should not run from $-k$ till $k$ (instead it should be something like a difference with 50, e.g. when k=10 then you have between 40 to 60 heads/ups and 60 to 40 tails/downs). – Sextus Empiricus Aug 23 '22 at 05:21
  • user334639, The use of brackets $[-k,k]$ instead of $(-k,k)$ suggests that $-k$ and $k$ are included. But the text 'between' instead of 'within' suggest that the $-k$ and $k$ are not included. You might want to clarify this in your question. – Sextus Empiricus Aug 23 '22 at 05:29
  • 1
    How do the moves count that were outside $[-k, k]$ in some of the moves below 100 but inside the range on the 100-th move? This precision of the question changes the answer by a factor 2. – Sextus Empiricus Aug 23 '22 at 05:36
  • By "between ... in 100 moves" do you mean at the end of the 100 moves or would you mean during the entire period?? – whuber Aug 23 '22 at 13:46
  • @Sextus Empiricus: Thanks for pointing out both problems. Definitely leaving the choose term out was dopey. And yes, the summation should be over the difference rather than $k$ but I'm not sure how to fix that. Hopefully, either you or the answer below fixes it. My apologies for mistakes. – mlofton Aug 23 '22 at 14:57
  • @Sextus Empiricus: Based on what you said below, it sounds a lot harder than I realized. Hopefully someone with a sharper mind ( like yourself ) can come up with the correct answer. I'll leave it alone and just tell the OP to disregard my attempt. OP: Disregard my attempt. – mlofton Aug 23 '22 at 14:59
  • @whuber During the period – user334639 Aug 23 '22 at 15:08
  • @mlofton Your point about the binomial distribution was correct (from that point onwards it is just writing out the equations which can pick up mistakes when it is done online in a comment). That is why I only gave two hints in my answer and left the derivation of an exact solution to the OP (and also because it seems like selfstudy). It's easy to make tiny mistakes here (although computing the Markov chain would not be so difficult). – Sextus Empiricus Aug 23 '22 at 15:45
  • This can be viewed as a random walk on a circle with $2k$ nodes. https://stats.stackexchange.com/questions/244428/ and https://stats.stackexchange.com/questions/441354 are closely related. It can also be formulated in terms of swapping balls between two urns, each starting with $k-1$ balls. https://stats.stackexchange.com/questions/292076 (with balls removed rather than swapped) gives one approach to working out the time to reach the "absorbing barrier" where a selected jar is empty. – whuber Aug 23 '22 at 18:00
  • @Sextus Empiricus: Thanks but putting -k in the summation made absolutely no sense. It was late so that's a small excuse. I'd like to see the actual correct expression so I'll check out those links that whuber and you provided. And yes, it does sound like a homework problem. Hopefully, I didn't confuse the OP too much with my wrong answer !!!!!! – mlofton Aug 24 '22 at 12:46
  • @mlofton the actual correct expression is gonna be an ugly expression that needs to take into account many reflections and also whether the numbers are odd or even. When the question can be simplified then it can be expressed more elegant. But how to simplify will depend on the background which the OP does not provide. – Sextus Empiricus Aug 24 '22 at 13:44
  • @Sextus Empiricus: Thanks for heads up. It sounds like, given my TODO list, it's best to leave it alone for now. It's interesting how a seemingly straightforward problem can be way more difficult than one initially thinks. Maybe that's because the random walk is a straightforward process so it lures one into thinking that every question associated with it is straightforward. :) – mlofton Aug 25 '22 at 16:06

1 Answers1

2

You can find a solution by considering two aspects:

  • The distribution of the one-dimensional random walk on a lattice can be modelled with a binomial distribution.
  • If you are not just interested in the position after 100 moves but also about the position of the path in all 99 previous moves, then you can use the reflection principle. This would more or less double the probability of the path extending outside $[-k,k]$ (that would be the case for a continuous distribution with continuous time, for a discrete distribution and discrete time steps it is slightly bit more tricky to work it out and the factor is not exactly 2).

Several questions and answers on this website already have dealt with this and they might help you to get an idea. See: https://stats.stackexchange.com/search?q=%22reflection+principle%22

Another relating post is https://stats.stackexchange.com/a/492091/164061 and you can also compute the probability by considering a Markov chain and compute the distribution step by step, or you can approximate this with an inverse Gaussian distribution.

Sextus Empiricus
  • 77,915
  • Applying the reflection principle is actually not so easy, as there will be multiple reflections that you need to take into account. – Sextus Empiricus Aug 23 '22 at 09:03