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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.