## How long for a simple random walk to exceed sqrt(T)?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2009 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 2009 at 12:47

6
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 Speyer Nov 22 2009 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 2009 at 14:36

2
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 2010 at 21:11
show 4 more comments

## 4 Answers

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 2010 at 0:14

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 expectation) should be of order $exp(exp(k^2/2))$.

-

3
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 2010 at 20:32

2
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 2010 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 k * u * sqrt(T) * Phi(1)/2, or approximately k * u * sqrt(T) * 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.)

-

3
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 2010 at 20:30
Thanks! it really has been too long since I learned/practiced any of this... – Yemon Choi Jan 31 2010 at 20:40
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 13, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9468916058540344, "perplexity_flag": "head"}