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$?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ I wrote the question myself. I am curious to know what is the answer and if the question is well-formulated. $\endgroup$– Dan BrumleveNov 22, 2009 at 9:28
-
$\begingroup$ 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? $\endgroup$– Yemon ChoiNov 22, 2009 at 12:47
-
7$\begingroup$ 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? $\endgroup$– David E SpeyerNov 22, 2009 at 14:30
-
$\begingroup$ @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... $\endgroup$– Yemon ChoiNov 22, 2009 at 14:36
-
3$\begingroup$ 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. $\endgroup$– Douglas ZareJan 31, 2010 at 21:11
|
Show 4 more comments
4 Answers
$\begingroup$
$\endgroup$
1
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.
answered Aug 22, 2010 at 22:37
-
$\begingroup$ 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. $\endgroup$ Aug 23, 2010 at 0:14
$\begingroup$
$\endgroup$
2
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))$.
answered Nov 23, 2009 at 8:47
-
5$\begingroup$ 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. $\endgroup$ Jan 31, 2010 at 20:32
-
3$\begingroup$ 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"). $\endgroup$ Feb 5, 2010 at 12:21
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.)
answered Nov 22, 2009 at 14:51
-
5$\begingroup$ 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. $\endgroup$ Jan 31, 2010 at 20:30
-
$\begingroup$ Thanks! it really has been too long since I learned/practiced any of this... $\endgroup$ Jan 31, 2010 at 20:40