How long for a simple random walk to exceed $\sqrt{T}$? Let $R_n$ be a simple random walk with $R_0 = 0$, and let $T$ be the smallest index such that $k\sqrt{T} < |R_T|$ for some positive $k$.
What is an expression for the probability distribution of $T$?
 A: For a Brownian motion, Novikov finds an explicit expression for any real moments (positive and negative) of the random variable $(\tau(a,b,c)+c)$, where
$$
\tau(a,b,c) = \inf(t \geq 0, W(t) \leq -a +b(t+c)^{1/2}) 
$$
with $a \geq 0$, $c \geq 0$, and $bc^{1/2} < a$. Shepp provides similar results but with W(t) replaced by |W(t)| in the definition, and the range of permissible $a,b,c$ restricted accordingly. Shepp also cites papers by Blackwell and Freedman (1964), Chow, Robbins, and Teicher (1965), and Chow and Teicher (1965), which look like they prove similar but weaker results when the Brownian motion is replaced by a random walk with finite variance. I don't have time to read those references at the moment but I figure these papers should lead you to your answer.
A: I doubt whether you can write down an exact formula for the distribution of T.
If you are interested in large values of k, the law of the iterated logarithm will enter into the picture. The typical value of T (say, the median) should be of order $\exp(\exp(k^2/2))$.
A: Building on Yemon, who suggests that the solution is some distribution of a hitting time, if we assume the threshold for the 'hit' is $\sqrt{T}$, and that variance, $u$, of the random variable is directly proportional to the square root of time, then the mean time for that variable to exceed $\sqrt{T}$ may equal $ku\sqrt{T} \Phi(1)/2$, or approximately $ku\sqrt{T} \cdot 0.16$, distributed lognormally.
A: Following a naive heuristic that rescaling a simple random walk (on the line, say) will give us Brownian motion, the question looks like a discrete version of the following question: what is the distribution of the hitting time for a standard Brownian motion starting at the origin?
The question as posed might have a messier answer, but one might be able to make progress more directly. For instance, the probability that $T> n$ is the probability that $R_j^2 \leq k^2j$ for all $j=1,2,\dots, n$, and one might be able to calculate or at least estimate that probability directly by a brute-force counting argument. (I'm sure there should be a better way, though, involving judicious use of conditional probabilities.)
