Is this a well-known probabilistic model?

2010-02-03T18:47:56Z

While I was thinking about the Erdős discrepancy problem, the following random walk model arose rather naturally. You fix a positive integer k, and you take a random step of 1 or -1 at each stage, except if that stage is a multiple of k, in which case you get to choose. Your object is to keep the walk as close to the origin as you can.

An obvious strategy is a greedy one: each time you have the choice, if the walk is currently positive you choose -1 and if it's currently negative you choose +1. (Clearly it makes no difference to the outcome what you do if it is zero.) This is like giving your random walk a drift term of size 1/k, but the drift is always directed towards the origin.

A slightly different question would be if you are presented with the entire walk up to kN-1 and you then choose the signs at k, 2k, 3k, ... , Nk, attempting to minimize the maximum distance it ever goes from the origin.

It is not hard to see that it must go at least logarithmically far, since by the time you get to M you will probably have had a run of log M 1s in the random walk, which you can do almost nothing about. I have thought about the problem in a non-rigorous way and it feels to me as though it shouldn't be too hard to prove that by the time you get to M you won't have gone further than $(\log M)^2$ or $(\log M)^3$ or something like that. (The rough argument is that if you look at a run of $k^2$ steps, it won't tend to drift more than about k, and you'll have k steps that you can choose so as to cancel out the drift. That is what usually happens, and the exceptions ought to be exponentially rare, so to speak.)

My main question is this: are these, or something like them, well-known questions? (Or do answers to them follow almost instantly from known results?)

Answer by Douglas Zare for Is this a well-known probabilistic model?

2010-02-03T19:07:34Z

If you apply the greedy algorithm, that is very close to asking for the maximum drawdown of a random walk with positive drift.

The distribution of maximum drawdowns of a Brownian motion with constant drift have been studied, and some answers are on page 2 here. The expected maximum drawdown with positive drift grows asymptotically like $c \log M$. I'm not sure how the tails look.

I asked how badly the Brownian approximation behaves for discrete walks here. It can be far off for some skewed distributions, but it should be off by a small constant factor for these nearly symmetric steps.

The globally optimal adjustments can't reduce the maximum excursion by more than a factor of 2 compared with the greedy algorithm, since on the largest (without loss of generality) positive excursion to $d$, the greedy algorithm was all -1s. Then any change made would still mean the walk increases by at least $d$, so at best a global optimization could move the start to $-d/2$ which would make the maximum at least $d/2$ in both directions.

Is this a well-known probabilistic model? - MathOverflow

Is this a well-known probabilistic model?

Answer by Douglas Zare for Is this a well-known probabilistic model?