Brownian Approximation of Downswings of Walks with Positive Drift - MathOverflow

Brownian Approximation of Downswings of Walks with Positive Drift

2010-01-09T06:33:28Z

I'm interested in the downswings of discrete walks w(t) whose steps are IID, bounded, and have positive mean. A simple example might have steps which are +1 with probability 2/3, and -1 with probability 1/3. A downswing of size at least D on [0,t] means 0<=a<b<=t and w(a)-w(b)>D.

Natural questions include the expected size of the largest downswing within [0,t] and the expected minimum b so that there is a downswing of size D ending at b.

One possible approach is to use a Brownian approximation with the same mean and standard deviation. This has the advantage that the distribution of the largest downswing on [0,t] has been studied. The expected time before a downswing of size D is computable and has a simple formula. Asymptotic expressions for the average size of the largest downswing on [0,t] have been computed. See Amrit Pratap's MS thesis.

However, the Brownian approximation has the disadvantage that it is wrong, and sometimes it is wrong by a lot. For example, a walk with only positive steps has no downswings at all.

I'd like to know how bad I should expect the Brownian approximation should be for steps which can be negative, with relatively small positive mean relative to the standard deviation. For example, -1 with probability 4/5, +5 with probability 1/5. I'd like to know if a skew in the positive direction means that large downswings are less common in the discrete walk than in the Brownian approximation.

Any help would be appreciated.

Answer by fedja for Brownian Approximation of Downswings of Walks with Positive Drift

2010-12-25T03:48:43Z

I just accidentally stumbled upon this nice question. I suspect that by now you know the answer yourself, but still, let me do one simple computation. If you like it, I'll think more of the question.

The process in question is just the following. A particle departs from the origin and does i.i.d. random steps with positive mean. If it ever ends up to the right of the origin, it is put back there. The question is what is the leftmost position it visited after $t$ steps.

I want to argue as follows. Let's look at the probability that it'll reach $-D$ before it comes back to the origin. It is about $Ce^{-\lambda D}$ where $\lambda>0$ is the only positive solution of the equation $\int p(x)e^{-\lambda x}dx=1$ and $p$ is the density of the step distribution. The value of $C$ is also possible to compute. Now, each attempt to depart from the origin lasts for some time with exponentially decaying tails. Let $T$ be the average time of travel. Then, by the time $t$, the number of attempted departures is about $t/T$. Thus, the probability of success is about $(1-Ce^{-\lambda D})^{t/T}$ meaning that $ED_{\text{min}}\approx \lambda^{-1}(\log t+\log(C/T)+U)$ where $U$ is some universal constant ($U=\int_0^\infty (e^{-e^{-x}}+e^{-e^x}-1)dx$, if I haven't mistaken). This would mean that, for large times, you are always a constant number of times off with the Brownian approximation.

Of course, this is just a back of envelope computation, but, since I don't even know if you are still interested, I'd rather stop here.