Let $x[n]$ be a Gaussian random walk, so $x[0] = 0$ and $x[n+1] = x[n] + v$, where $v$ is an independent random variable with normal distribution, $0$ mean and standard deviation $s$.

What is the probability that in $k$ steps $x$ has crossed above threshold $T$? So for any $0 \lt n \leq k$ $x[n]\gt T$?

I could work out the probability that $x[k]$, the final value, is under or over $T$. $x[k]$ will have a normal distribution with $0$ mean, and $s\cdot\sqrt{k}$ standard deviation.

But I can't work out the probability that any value within k steps has crossed over T.

I tried to approach the problem in a way to work out $1-P(all\ x[1...k] \lt T)$. So all steps stay under T, and take the inverse of that.

I thought this would be $P(x[1] < T\ and\ x[2] < T \ldots) = P(x[1] < T) \cdot P(x[2] < T)\cdot \ldots$

where $P(x[n] < T)$ is evaluated as the normal distribution of the n-step random walk...

But this seems to be incorrect, based on simulations, and I'm lost. This is not a homework btw.

  • $\begingroup$ Hi: I've had a similar question and have looked around. I'm not 100 percent sure but I'm fairly certain that the only solution is simulation. Also, note that for small $k$, I'm still not sure if simulation is even reliable because, even if you replicate millions of times, you still have a small sample size. I'll try to find the thread created when I asked a similar question. $\endgroup$ – mlofton Jan 5 '20 at 4:40
  • $\begingroup$ Hi: Here it is: quant.stackexchange.com/questions/41548/…. My question may not seem like yours at first glance. But the deterministic steps that Slowmo takes don't matter. They are still the same questions because mine can be restated as: as: "Slowmo follows a random walk ( to the north and south ) and starts at zero. What is the probablility that, in k steps, slowmo ever crosses above zero". $\endgroup$ – mlofton Jan 5 '20 at 4:57
  • $\begingroup$ Hi! Thanks for the input. Your other question indeed looks to be the same thing. I've tried simulation as well. I was messing around with the formula, came up with this for P(x[k]<T): P0 = 1; P(k) = P(k-1) * (1.955-P(k-1)) * Phi(T,0, s*sqrt(k)). Based on simulation, this is about +-5% accurate. $\endgroup$ – bencsikg Jan 7 '20 at 18:47
  • $\begingroup$ @bencislg: I think the only way is through simulation because, even if the closed form solution was complicated, there are many smart people ( waaaaay better than me ) that work on those types of things so it should be around somewhere. Yet, I looked around a lot and never found a formula. Also, what I find problematic is that, if you simulate for small k, will the simulation converge to some value even if $k$ is small ? That's somewhat troubling and I'm not sure about that. If you find anything interesting with regard to that question, the info is appreciated. $\endgroup$ – mlofton Jan 8 '20 at 15:45
  • $\begingroup$ Well, I simulated it in Python. I don't really get your concern about small k (maybe cause I'm inexperienced). But I think random numbers are just random numbers. You run it 100000 times for k=2, in the end you get 200000 random number to add / average in some way. For k=2, s=1,T=1 the experimental formula gives (for crossing) P=0.2966 and the simulation turns up results around P=0.29 +-0.01 (each run averages 100000 cases). For k=6, calculation gives P=0.499, simulation about P=0.52. For large ks, it seems to approach P=1, for example k=100 -> P~=0.88, k=1000->P~=0.96 $\endgroup$ – bencsikg Jan 8 '20 at 20:26

I thought this would be P(x[1] < T and x[2] < T ...) = P(x[1] < T) * P(x[2] < T)*...

You can't factorize this way because the events are dependent. It is factorized the following way: $$P(X_1<T)\prod_{n=2}^k P\left(\sum_{i=1}^n X_i<T\ \bigg|\bigcap_{j=1}^{n-1} \sum_{i=1}^{j} X_i<T\right)$$

I feel that each of these multiplicands is very hard (and maybe analytically impossible) to find. Consider only the case where $k=2$, and you have $v_1,v_2$: $$\begin{align}P(V_1<T\cap V_1+V_2<T)&=\int_{-\infty}^T\int_{-\infty}^{T-u} f_{V_1}(u)f_{V_2}(w)dw du\\&=\int_{-\infty}^T f_{V_1}(u)\Phi\left(\frac{T-u}{s}\right) du\end{align}$$ where $\Phi(x)$ denotes the CDF of standard normal RV. I don't think we could be able to make our way out of this integral.

  • $\begingroup$ Thanks! At least this explains why I couldn't get far with this problem. It was never my intention to get the analytic result in terms of some exp() function, but maybe in terms of erf(), or some recursive formula to calculate it. How would this integral formula generalize for k=3 and up? $\endgroup$ – bencsikg Jan 7 '20 at 18:59

I know I'm not providing an answer to this question but wanted to provide an alternative path that I am myself trying to solve this same problem and that I have not seen anybody else suggest here.

In my case, I want to calculate several probabilities related my random walker not reaching two absorbing states: one above the starting point and one below it. I also would like to have an equation that would give me these probabilities based on the standard deviation and the positions of the absorbing states. I have a general idea of what the values of my standard deviation can be and the places where the absorbing states can be, so I'm setting limits (a lower and upper value for standard deviation and positions of absorbing states) and then running multiple simulations within those values (it takes a very long time to run). With the results from those simulations I'm training a neural network to map the input variables (position of absorbing states and standard deviation) to the probabilities of never touching the absorbing states. In my case, I have set fixed the number of steps into the future, so I basically have only 3 variables as input and the probability as output.

Let's see how this turns out.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.