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.

  • 1
    $\begingroup$ 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). $\endgroup$ – Qiaochu Yuan Jan 9 '10 at 8:06
  • $\begingroup$ The link to Pratap's thesis has been changed. This URL should work: thesis.library.caltech.edu/2132 $\endgroup$ – Douglas Zare Apr 7 '10 at 19:47

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.

  • $\begingroup$ I'm still interested, and I hadn't gotten that far. Thanks. $\endgroup$ – Douglas Zare Dec 25 '10 at 5:13
  • $\begingroup$ OK, I'll try to make accurate estimates and post them later today then :). $\endgroup$ – fedja Dec 25 '10 at 16:45
  • $\begingroup$ Sorry for the delay. I have the asymptotics for the bounded step discrete case neat and clean now (including "explicit" formulae for the related parameters and checking against numerics), but the continuous case still gives me a headache, especially when the steps are unbounded. Unfortunately, you cannot just pass to the limit from the discrete bounded step version if you want the accuracy I declared and I'm reluctant to settle for less. $\endgroup$ – fedja Dec 29 '10 at 2:30

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.