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

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?)

share|improve this question
You say "an obvious strategy is..." Is it not obvious that this is the best strategy? (Assuming that you make the decisions at time kn having only seen the outcomes at previous times.) –  Pete L. Clark Feb 3 '10 at 20:00
Not globally. You might push in the positive direction when t is small, and then be forced to accept a large positive excursion you could have partly prevented. –  Douglas Zare Feb 3 '10 at 20:07
When k = 2, I claim that this strategy is fantastic. For larger k, I'm afraid I'm still not getting it. Again, we are talking about the case where you make your decisions sequentially, not all at once. What could be a better strategy? –  Pete L. Clark Feb 3 '10 at 20:16
I'm talking about the "slightly different question." k=3. -1,-1,?,+1,+1,?,+1,+1,?,+1,+1,?,+1,+1,?,+1,+1,?. Greedy chooses +1, -1, -1, -1, -1, -1. Global chooses -1, -1, -1, -1, -1, -1. –  Douglas Zare Feb 3 '10 at 20:29
Was it not clear from my initial comment that I was not talking about the "slightly different question"? –  Pete L. Clark Feb 3 '10 at 22:20
show 1 more comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


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.