# 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$?

• I wrote the question myself. I am curious to know what is the answer and if the question is well-formulated. – Dan Brumleve Nov 22 '09 at 9:28
• It's not that it doesn't seem interesting - it's that it seems like the sort of thing where someone with access to a maths library could go and try to look it up, or just sit down and work it out. It smells like the sort of question that must have been answered somewhere without recourse to very advanced work. How about Feller's book, for instance? – Yemon Choi Nov 22 '09 at 12:47
• I thin I disagree. It might be that easy, but it might take a bit of work, especially for someone who doesn't work in probability. Why don't we just wait and see whether an expert comes by and knows this? – David E Speyer Nov 22 '09 at 14:30
• @David: Fair enough. I guess it's a question of phrasing: I am always more sympathetic to questions which ask "is this known?" or "I've tried this, but it didn't work, should I look at something else?" Questions are easy (I have 50+ pages of my own, unanswered); attainable questions less so... – Yemon Choi Nov 22 '09 at 14:36
• If you ask for the smallest index greater than T_0, this is a very natural question. Consider $k=2$: Suppose you are trying to reject a null hypothesis on, say, whether a coin is fair. If the coin actually is fair, how much data do you need to collect before you can incorrectly reject the null hypothesis at the 2 standard deviation level of significance? I don't think this is a homework-level question for an undergraduate probability course, and it would require hints in a graduate course. – Douglas Zare Jan 31 '10 at 21:11

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.

• This answer is also about a slightly different question but it has the most new information for me, so I am accepting it as the bounty is almost over. – Dan Brumleve Aug 23 '10 at 0:14

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))$.

• I haven't looked at this too closely, but I think the expectation should be infinite. The median or other quantiles may be suggested by a version of the law of the iterated logarithm. – Douglas Zare Jan 31 '10 at 20:32
• Humm, you are absolutely right, the expectation is infinite for k larger than 1 (Theorem 1.7, Chapter 3 in Durrett's book "Theory and Examples"). – Guillaume Aubrun Feb 5 '10 at 12:21

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.

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

• For any $k \gt 0$, the infimum of the times where a Brownian motion is more than $k \sqrt T$ is 0. This may be counterintuitive, but it's a consequence of the combination of time inversion ($t W(1/t)$ is also Brownian) and the law of the iterated logarithm. – Douglas Zare Jan 31 '10 at 20:30
• Thanks! it really has been too long since I learned/practiced any of this... – Yemon Choi Jan 31 '10 at 20:40