# Brownian Approximation of Downswings of Walks with Positive Drift

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.

-
The set of walks with downswings of at most a certain size is a regular language, so there are well-known techniques for computing the quantities you want, at least when the distribution is discrete (documented for example in Flajolet and Sedgewick's Analytic Combinatorics). – Qiaochu Yuan Jan 9 '10 at 8:06
The link to Pratap's thesis has been changed. This URL should work: thesis.library.caltech.edu/2132 – Douglas Zare Apr 7 '10 at 19:47

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.