Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

Simple question - what would be the fastest algorithm for calculating retrospective maximum drawdown ?

I've found some interesting talks but I was wondering what people thought of this question here.

share|improve this question
1  
Your question is not clear to me. Do you mean the easiest technique to code, or code that is CPU efficient? –  montyhall Dec 30 '12 at 6:28
    
A vectorized approach (since inception) is very fast. –  pat Dec 30 '12 at 9:18
    
You should probably clarify your question. Most readers are assuming you are asking about retrospective maximum drawdown, whereas I infer from the PDF you want to compute an expectation of it. –  Brian B Dec 30 '12 at 15:13
    
Sorry for the confusion, I indeed meant algorithm/code that is CPU efficient for calculating retrospective maximum drawdown. –  gulthor Dec 30 '12 at 15:24

4 Answers 4

I won't give you the answer delivered on a silver platter but hopefully the following will get your started:

a) you need to define exactly over which look-back period you aim to derive the maximum drawdown.

b) you need to keep track of the max price while you iterate the look-back window.

c) you need to keep track of the min price SUBSEQUENT to any NEW max, thus each time you make a new max you need to reset the max low to zero (relatively speaking as a divergence from the max value)

this should get you pretty easily to where you want to get without having to iterate the time series more than once. I disagree that a vectorized approach will solve this problem (@Pat, please provide an answer if you disagree I would be curious how you would approach this in a vectorized manner because the algorithm here is path-dependent).

share|improve this answer
    
There is only 1 path from inception (and only 1 iteration required with vectorized dd result of that path). What you are describing above is a rolling dd (*Note I specified since inception). If you have a time series and can show an example of your algorithm and time, I will reproduce using a vectorized approach and compare times. –  pat Dec 30 '12 at 23:15
1  
@pat, "rolling dd", well, that is pretty much industry practice. Nobody cares about the maximum draw down over a ten year window, at least I do not know of too many investors with such long term memory. Please go ahead and show your vectorized version (even the one where you define maximum dd from inception), it would add a lot of value to other users. What holds you back? –  Matt Wolf Dec 31 '12 at 8:25

Zipline, the opensource python backtester, has a batch and iterative implementation for max drawdown.

Here is the batch: https://github.com/quantopian/zipline/blob/master/zipline/finance/risk.py#L284

Here is the iterative: https://github.com/quantopian/zipline/blob/master/zipline/finance/risk.py#L578

disclosure: I'm one of the zipline maintainers

share|improve this answer

(After the clarification, this answer is no longer relevant)

Expected maximum drawdown is going to be highly sensitive to your choice of SDE, and to your calibration of it. Therefore you should play with a variety of parameterizations to estimate your model error.

So far as efficient computation goes, we can regard this as a payoff very similar to a lookback option (much as in the PDF you linked). As with lookback options, the first instinct is to price them using Monte Carlo techniques, but one can actually do so much more quickly using a multi-level PDE solver, at least for sufficiently simple SDEs.

The way a 2-level PDE solver works for a payoff like this is that, rather than having a grid of $(S,t)$ values on which you run your difference equations and boundary conditions, you have a grid of $( \{M,S\}, t )$ values, where $M$ represents the maximum achieved so far. Obviously there are some new boundary conditions that go with it, for example that $\frac{\partial M}{\partial S}=1$ at and above the line $S=M$.

Differencing and updating on this grid, you ultimately end up with a value $V_{0,0}$ corresponding to today's maximum $M_0$ and stock price $S_0$.

See section 5.3.2 of this pdf for how it works with lookbacks. Max drawdowns will be very similar.

share|improve this answer

Hello people. This is quite a complex problem if you want to solve this in a computationally efficient way for a rolling window. I have gone ahead and written a solution to this in C#. I want to share this as the effort required to replicate this work is quite high.

First, here are the results:

here we take a simple drawdown implementation and re-calculate for the full window each time

test1 - simple drawdown test with 30 period rolling window. run 100 times.
total seconds 0.8060461
test2 - simple drawdown test with 60 period rolling window. run 100 times.
total seconds 1.416081
test3 - simple drawdown test with 180 period rolling window. run 100 times.
total seconds 3.6602093
test4 - simple drawdown test with 360 period rolling window. run 100 times.
total seconds 6.696383
test5 - simple drawdown test with 500 period rolling window. run 100 times.
total seconds 8.9815137

here we compare to the results generated from my efficient rolling window algorithm where only the latest observation is added and then it does it's magic

test6 - running drawdown test with 30 period rolling window. run 100 times.
total seconds 0.2940168
test7 - running drawdown test with 60 period rolling window. run 100 times.
total seconds 0.3050175
test8 - running drawdown test with 180 period rolling window. run 100 times.
total seconds 0.3780216
test9 - running drawdown test with 360 period rolling window. run 100 times.
total seconds 0.4560261
test10 - running drawdown test with 500 period rolling window. run 100 times.
total seconds 0.5050288

At at 500 period window. We are achieving about a 20:1 improvement in calculation time.

Here is the code of the simple drawdown class used for the comparisons:

public class SimpleDrawDown
{
    public double Peak { get; set; }
    public double Trough { get; set; }
    public double MaxDrawDown { get; set; }

    public SimpleDrawDown()
    {
        Peak = double.NegativeInfinity;
        Trough = double.PositiveInfinity;
        MaxDrawDown = 0;
    }

    public void Calculate(double newValue)
    {
        if (newValue > Peak)
        {
            Peak = newValue;
            Trough = Peak;
        }
        else if (newValue < Trough)
        {
            Trough = newValue;
            var tmpDrawDown = Peak - Trough;
            if (tmpDrawDown > MaxDrawDown)
                MaxDrawDown = tmpDrawDown;
        }
    }
}

And here is the code for the full efficient implementation. Hopefully the code comments make sense.

internal class DrawDown
{
    int _n;
    int _startIndex, _endIndex, _troughIndex;
    public int Count { get; set; }
    LinkedList<double> _values;
    public double Peak { get; set; }
    public double Trough { get; set; }
    public bool SkipMoveBackDoubleCalc { get; set; }

    public int PeakIndex
    {
        get
        {
            return _startIndex;
        }
    }
    public int TroughIndex
    {
        get
        {
            return _troughIndex;
        }
    }

    //peak to trough return
    public double DrawDownAmount
    {
        get
        {
            return Peak - Trough;
        }
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="n">max window for drawdown period</param>
    /// <param name="peak">drawdown peak i.e. start value</param>
    public DrawDown(int n, double peak)
    {
        _n = n - 1;
        _startIndex = _n;
        _endIndex = _n;
        _troughIndex = _n;
        Count = 1;
        _values = new LinkedList<double>();
        _values.AddLast(peak);
        Peak = peak;
        Trough = peak;
    }

    /// <summary>
    /// adds a new observation on the drawdown curve
    /// </summary>
    /// <param name="newValue"></param>
    public void Add(double newValue)
    {
        //push the start of this drawdown backwards
        //_startIndex--;
        //the end of the drawdown is the current period end
        _endIndex = _n;
        //the total periods increases with a new observation
        Count++;
        //track what all point values are in the drawdown curve
        _values.AddLast(newValue);
        //update if we have a new trough
        if (newValue < Trough)
        {
            Trough = newValue;
            _troughIndex = _endIndex;
        }
    }

    /// <summary>
    /// Shift this Drawdown backwards in the observation window
    /// </summary>
    /// <param name="trackingNewPeak">whether we are already tracking a new peak or not</param>
    /// <returns>a new drawdown to track if a new peak becomes active</returns>
    public DrawDown MoveBack(bool trackingNewPeak, bool recomputeWindow = true)
    {
        if (!SkipMoveBackDoubleCalc)
        {
            _startIndex--;
            _endIndex--;
            _troughIndex--;
            if (recomputeWindow)
                return RecomputeDrawdownToWindowSize(trackingNewPeak);
        }
        else
            SkipMoveBackDoubleCalc = false;

        return null;
    }

    private DrawDown RecomputeDrawdownToWindowSize(bool trackingNewPeak)
    {
        //the start of this drawdown has fallen out of the start of our observation window, so we have to recalculate the peak of the drawdown
        if (_startIndex < 0)
        {
            Peak = double.NegativeInfinity;
            _values.RemoveFirst();
            Count--;

            //there is the possibility now that there is a higher peak, within the current drawdown curve, than our first observation
            //when we find it, remove all data points prior to this point
            //the new peak must be before the current known trough point
            int iObservation = 0, iNewPeak = 0, iNewTrough = _troughIndex, iTmpNewPeak = 0, iTempTrough = 0;
            double newDrawDown = 0, tmpPeak = 0, tmpTrough = double.NegativeInfinity;
            DrawDown newDrawDownObj = null;
            foreach (var pointOnDrawDown in _values)
            {
                if (iObservation < _troughIndex)
                {
                    if (pointOnDrawDown > Peak)
                    {
                        iNewPeak = iObservation;
                        Peak = pointOnDrawDown;
                    }
                }
                else if (iObservation == _troughIndex)
                {
                    newDrawDown = Peak - Trough;
                    tmpPeak = Peak;
                }
                else
                {
                    //now continue on through the remaining points, to determine if there is a nested-drawdown, that is now larger than the newDrawDown
                    //e.g. higher peak beyond _troughIndex, with higher trough than that at _troughIndex, but where new peak minus new trough is > newDrawDown
                    if (pointOnDrawDown > tmpPeak)
                    {
                        tmpPeak = pointOnDrawDown;
                        tmpTrough = tmpPeak;
                        iTmpNewPeak = iObservation;
                        //we need a new drawdown object, as we have a new higher peak
                        if (!trackingNewPeak) 
                            newDrawDownObj = new DrawDown(_n + 1, tmpPeak);
                    }
                    else
                    {
                        if (!trackingNewPeak && newDrawDownObj != null)
                        {
                            newDrawDownObj.MoveBack(true, false); //recomputeWindow is irrelevant for this as it will never fall before period 0 in this usage scenario
                            newDrawDownObj.Add(pointOnDrawDown);  //keep tracking this new drawdown peak
                        }

                        if (pointOnDrawDown < tmpTrough)
                        {
                            tmpTrough = pointOnDrawDown;
                            iTempTrough = iObservation;
                            var tmpDrawDown = tmpPeak - tmpTrough;

                            if (tmpDrawDown > newDrawDown)
                            {
                                newDrawDown = tmpDrawDown;
                                iNewPeak = iTmpNewPeak;
                                iNewTrough = iTempTrough;
                                Peak = tmpPeak;
                                Trough = tmpTrough;
                            }
                        }
                    }
                }
                iObservation++;
            }

            _startIndex = iNewPeak; //our drawdown now starts from here in our observation window
            _troughIndex = iNewTrough;
            for (int i = 0; i < _startIndex; i++)
            {
                _values.RemoveFirst(); //get rid of the data points prior to this new drawdown peak
                Count--;
            }
            return newDrawDownObj;
        }
        return null;
    }

}

public class RunningDrawDown
{

    int _n;
    List<DrawDown> _drawdownObjs;
    DrawDown _currentDrawDown;
    DrawDown _maxDrawDownObj;

    /// <summary>
    /// The Peak of the MaxDrawDown
    /// </summary>
    public double DrawDownPeak
    {
        get
        {
            if (_maxDrawDownObj == null) return double.NegativeInfinity;
            return _maxDrawDownObj.Peak;
        }
    }
    /// <summary>
    /// The Trough of the Max DrawDown
    /// </summary>
    public double DrawDownTrough
    {
        get
        {
            if (_maxDrawDownObj == null) return double.PositiveInfinity;
            return _maxDrawDownObj.Trough;
        }
    }
    /// <summary>
    /// The Size of the DrawDown - Peak to Trough
    /// </summary>
    public double DrawDown
    {
        get
        {
            if (_maxDrawDownObj == null) return 0;
            return _maxDrawDownObj.DrawDownAmount;
        }
    }
    /// <summary>
    /// The Index into the Window that the Peak of the DrawDown is seen
    /// </summary>
    public int PeakIndex
    {
        get
        {
            if (_maxDrawDownObj == null) return 0;
            return _maxDrawDownObj.PeakIndex;
        }
    }
    /// <summary>
    /// The Index into the Window that the Trough of the DrawDown is seen
    /// </summary>
    public int TroughIndex
    {
        get
        {
            if (_maxDrawDownObj == null) return 0;
            return _maxDrawDownObj.TroughIndex;
        }
    }

    /// <summary>
    /// Creates a running window for the calculation of MaxDrawDown within the window
    /// </summary>
    /// <param name="n">the number of periods within the window</param>
    public RunningDrawDown(int n)
    {
        _n = n;
        _currentDrawDown = null;
        _drawdownObjs = new List<DrawDown>();
    }

    /// <summary>
    /// The new value to add onto the end of the current window (the first value will drop off)
    /// </summary>
    /// <param name="newValue">the new point on the curve</param>
    public void Calculate(double newValue)
    {
        if (double.IsNaN(newValue)) return;

        if (_currentDrawDown == null)
        {
            var drawDown = new DrawDown(_n, newValue);
            _currentDrawDown = drawDown;
            _maxDrawDownObj = drawDown;
        }
        else
        {
            //shift current drawdown back one. and if the first observation falling outside the window means we encounter a new peak after the current trough, we start tracking a new drawdown
            var drawDownFromNewPeak = _currentDrawDown.MoveBack(false);

            //this is a special case, where a new lower peak (now the highest) is created due to the drop of of the pre-existing highest peak, and we are not yet tracking a new peak
            if (drawDownFromNewPeak != null)
            {
                _drawdownObjs.Add(_currentDrawDown); //record this drawdown into our running drawdowns list)
                _currentDrawDown.SkipMoveBackDoubleCalc = true; //MoveBack() is calculated again below in _drawdownObjs collection, so we make sure that is skipped this first time
                _currentDrawDown = drawDownFromNewPeak;
                _currentDrawDown.MoveBack(true);
            }

            if (newValue > _currentDrawDown.Peak)
            {
                //we need a new drawdown object, as we have a new higher peak
                var drawDown = new DrawDown(_n, newValue);
                //do we have an existing drawdown object, and does it have more than 1 observation
                if (_currentDrawDown.Count > 1)
                {
                    _drawdownObjs.Add(_currentDrawDown); //record this drawdown into our running drawdowns list)
                    _currentDrawDown.SkipMoveBackDoubleCalc = true; //MoveBack() is calculated again below in _drawdownObjs collection, so we make sure that is skipped this first time
                }
                _currentDrawDown = drawDown;
            }
            else
            {
                //add the new observation to the current drawdown
                _currentDrawDown.Add(newValue);
            }
        }

        //does our new drawdown surpass any of the previous drawdowns?
        //if so, we can drop the old drawdowns, as for the remainer of the old drawdowns lives in our lookup window, they will be smaller than the new one
        var newDrawDown = _currentDrawDown.DrawDownAmount;
        _maxDrawDownObj = _currentDrawDown;
        var maxDrawDown = newDrawDown;
        var keepDrawDownsList = new List<DrawDown>();
        foreach (var drawDownObj in _drawdownObjs)
        {
            drawDownObj.MoveBack(true);
            if (drawDownObj.DrawDownAmount > newDrawDown)
            {
                keepDrawDownsList.Add(drawDownObj);
            }

            //also calculate our max drawdown here
            if (drawDownObj.DrawDownAmount > maxDrawDown)
            {
                maxDrawDown = drawDownObj.DrawDownAmount;
                _maxDrawDownObj = drawDownObj;
            }

        }
        _drawdownObjs = keepDrawDownsList;

    }

}

Example usage:

RunningDrawDown rd = new RunningDrawDown(500);
foreach (var input in data)
{
    rd.Calculate(input);
    Console.WriteLine(string.Format("max draw {0:0.00000}, peak {1:0.00000}, trough {2:0.00000}, drawstart {3:0.00000}, drawend {4:0.00000}",
        rd.DrawDown, rd.DrawDownPeak, rd.DrawDownTrough, rd.PeakIndex, rd.TroughIndex));
}
share|improve this answer
    
also posted here where the code can be formatted nicely. stackoverflow.com/questions/24937128/… –  DaManJ yesterday

Your Answer

 
discard

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.