Probability of Normal (Gaussian) random walk crossing threshold within k steps 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.
 A: 
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.
A: 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.
