Where does directed random walk hit the boundary of a region? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:20:45Z http://mathoverflow.net/feeds/question/100903 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100903/where-does-directed-random-walk-hit-the-boundary-of-a-region Where does directed random walk hit the boundary of a region? Anthony Quas 2012-06-29T02:52:22Z 2012-07-01T22:12:04Z <p>I have a problem that I more or less know the answer to (in an ad hoc way), but would really like to see it done in a systematic way. In spite of this, I will pose the question in quite a concrete way. Note: this question was previously posted on <a href="http://math.stackexchange.com/questions/163850/where-does-directed-random-walk-hit-the-boundary" rel="nofollow">stackexchange</a>.</p> <p>Consider a two-dimensional random walk on $\mathbb Z^2$. Fix a finite subset $S$ of $\mathbb Z^2$ in which each element of $S$ has strictly positive $x$-coordinate and assign a probability measure $\mu$ to $S$ Write the location of the 2D walk as $(X_n,Y_n)$ and let $(X_{n+1},Y_{n+1})=(X_n,Y_n)+(u,v)$, where $(u,v)$ is a randomly chosen element of $S$, chosen with distribution $\mu$.</p> <p>Let $T=\inf\lbrace n\colon X_n\ge M\rbrace$ for some (large) fixed $M$. I'm looking for a way to describe $Y_T$. </p> <p>Here's what I think is the answer: Write $(U,V)$ for a random element of $S$, write $\bar U=\mathbb EU$ and $\bar V=\mathbb EV$ (here $\mathbb E$ is with respect to $\mu$). I expect that $Y_T$ will have a distribution (for large $M$) close to a normal distribution with mean $M\bar V/\bar U$ and variance $(M/\bar U)\mathbb E(V-U\bar V/\bar U)^2$.</p> http://mathoverflow.net/questions/100903/where-does-directed-random-walk-hit-the-boundary-of-a-region/101099#101099 Answer by Omer for Where does directed random walk hit the boundary of a region? Omer 2012-07-01T22:00:16Z 2012-07-01T22:12:04Z <p>You can get a CLT for $Y_T$ directly as well. If $s=M/\bar{U}$ is the approximate hitting time, then $X_s,Y_s$ are a Gaussian vector, and $|M-X_s|=O(\sqrt{M})$ (all $O(\cdot)$ are in distribution). Given $X_s$ we know $T-s$ up to $O(M^{1/4})$, and therefore also know $Y_T-Y_s$ up to $O(M^{1/4})$. </p> <p>There is a slight delicate point here: If $X_sM$ they depend on the first $s$ steps. You can justify this case either by a large deviation estimate (not much more than the LLN is needed), or by using $s'=(1-\epsilon)s$ instead of $s$, and then $X_s &lt; M$ whp. </p> <p>I hadn't carried out the computation, but your formula for the variance seems plausible. In any case, you have that $(X_s,Y_s)$ is Gaussian and $Y_t$ is a projection of that in a fixed direction, so is also Gaussian.</p>