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

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

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

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

  • 1
    $\begingroup$ I am not sure what you mean by "systematic way". If you asked me to prove this statement, I would say that the hitting time $T$ is concentrated around $T_0=M/\bar{U}$ with variance of the same order. This means that I only have to check the value of $Y_{T_0}$, which has the average and variation you write, and then $|Y_T-Y_{T_0}| is about $T_0^{1/4}$ which is small compared to the standard deviation. $\endgroup$ Jun 29, 2012 at 7:12
  • $\begingroup$ Thanks @Ori. This is roughly the approach I was using. But I think that $|Y_T-Y_{T_0}|$ is of the order $T_0^{1/2}$ which is of the same order as the standard deviation. If you don't account for this, then the variance of $Y_T$ would be just $T_0$ times the variance of $V$, but I don't think this is right. I used the approximation $Y_T\approx Y_{T_0}-(\bar V/\bar U)(X_{T_0}-M)$ and then computed the variance of that quantity. I am seeking justification for that approximation. $\endgroup$ Jun 30, 2012 at 1:47
  • $\begingroup$ You're right about the exponent being $\frac12$, I was thinking about the case where $\bar{V}=0$. You can get the result you want in a more systematic way defining $Y'_t=Y_t - t \bar{V}$ which is a martingale. I will write a more complete answer later. $\endgroup$ Jun 30, 2012 at 20:39
  • $\begingroup$ Thanks @Ori - this sounds like exactly the kind of thing that I was hoping for in posing the question $\endgroup$ Jun 30, 2012 at 21:05

1 Answer 1


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

There is a slight delicate point here: If $X_s<M$ the additional steps are independent and you just use use the LLN for them. If $X_s>M$ 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 < M$ whp.

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.

  • $\begingroup$ Thanks a lot @Omer. I'm trying to parse the second paragraph. Were you saying if $X_s>M$, then $Y_T-Y_s$ depends on the first $s$ steps? $\endgroup$ Jul 2, 2012 at 0:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .