Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  Ori Gurel-Gurevich Jun 29 '12 at 7:12
    
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. –  Anthony Quas Jun 30 '12 at 1:47
    
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. –  Ori Gurel-Gurevich Jun 30 '12 at 20:39
    
Thanks @Ori - this sounds like exactly the kind of thing that I was hoping for in posing the question –  Anthony Quas Jun 30 '12 at 21:05
add comment

1 Answer

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.

share|improve this answer
    
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? –  Anthony Quas Jul 2 '12 at 0:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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