most recent 30 from http://mathoverflow.net 2013-06-19T20:59:30Z http://mathoverflow.net/feeds/question/6444 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6444/how-long-for-a-simple-random-walk-to-exceed-sqrtt Dan Brumleve 2009-11-22T08:48:55Z 2010-09-13T22:07:10Z

<p>Let {R_n} be a simple random walk with R_0 = 0, and let T be the smallest index such that k * sqrt(T) &lt; |R_T| for some positive k. What is an expression for the probability distribution of T?</p>

http://mathoverflow.net/questions/6444/how-long-for-a-simple-random-walk-to-exceed-sqrtt/6463#6463 Yemon Choi 2009-11-22T14:51:08Z 2009-11-22T14:51:08Z

<p>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 <a href="http://en.wikipedia.org/wiki/Hitting%5Ftime" rel="nofollow">hitting time</a> for a standard Brownian motion starting at the origin?</p> <p>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.)</p>

http://mathoverflow.net/questions/6444/how-long-for-a-simple-random-walk-to-exceed-sqrtt/6545#6545 Guillaume Aubrun 2009-11-23T08:47:27Z 2009-11-23T08:47:27Z

<p>I doubt whether you can write down an exact formula for the distribution of T.</p> <p>If you are interested in large values of k, the <a href="http://en.wikipedia.org/wiki/Law%5Fof%5Fthe%5Fiterated%5Flogarithm" rel="nofollow">law of the iterated logarithm</a> will enter into the picture. The typical value of T (say, the expectation) should be of order $exp(exp(k^2/2))$.</p>

http://mathoverflow.net/questions/6444/how-long-for-a-simple-random-walk-to-exceed-sqrtt/36413#36413 Louigi Addario-Berry 2010-08-22T22:37:49Z 2010-08-22T22:37:49Z

<p>For a Brownian motion, <a href="http://siamdl.aip.org/getabs/servlet/GetabsServlet?prog=normal&amp;id=TPRBAU000016000003000449000001&amp;idtype=cvips&amp;gifs=Yes" rel="nofollow">Novikov</a> 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} &lt; a$. <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aoms/1177698626" rel="nofollow">Shepp</a> 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. </p>

http://mathoverflow.net/questions/6444/how-long-for-a-simple-random-walk-to-exceed-sqrtt/38621#38621 calculus 2010-09-13T20:35:57Z 2010-09-13T22:07:10Z

<p>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.</p>