# Fastest algorithm for calculating retrospective maximum drawdown

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.

• 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. – jbmusso Dec 30 '12 at 15:24

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

• 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
• @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? – Matthias Wolf Dec 31 '12 at 8:25

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; }
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;
Peak = peak;
Trough = peak;
}

/// <summary>
/// adds a new observation on the drawdown curve
/// </summary>
/// <param name="newValue"></param>
{
//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
//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
}
}

//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)
{
}

//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));
}


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

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

disclosure: I'm one of the zipline maintainers

• The links above no longer work – chollida Jul 30 '14 at 17:36

In Python, a very slick implementation that exploits the rolling functionality in pandas is like this

import pandas as pd

def get_max_dd(nvs: pd.Series, window=None) -> float:
"""
:param nvs: net value series
:param window: lookback window, int or None
if None, look back entire history
"""
n = len(nvs)
if window is None:
window = n
# rolling peak values
peak_series = nvs.rolling(window=window, min_periods=1).max()
return (nvs / peak_series - 1.0).min()


This will be faster than manually writing for loops etc., because pandas is underlyingly C-accelerated. By only using pandas's native components we kind of "steal" a lot of speed boost from C.

(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.

I was looking for someone else's answer to compare with mine.

Vectorization is clearly the way to go. Question is, how do we vectorize this problem. Below is a commented function that accomplishes this in python using numpy and pandas.

import numpy as np
import pandas as pd

def max_dd(returns, rolling=None):
# make into a DataFrame so that it is a 2-dimensional
# matrix such that I can perform an nx1 by 1xn matrix
# multiplication and end up with an nxn matrix
#
# add 1 and produce a series of cumulative products
# because the cumulative product acts as a return
# index.  We'll use the return index to calculate
# returns between two periods.

# r is nx1 and 1 / r.T is 1xn.  x is nxn
# I copy r.T to ensure r's index is not the same
# object as 1 / r.T's columns object
#
# x is now a matrix of every combination of one
# period's return index divided by another period's
# return index then subtract one.  So every element
# of this matrix represents the return from the period
# specified in the column to the period specified in
# the row.
x = r.dot(1 / r.T.copy()) - 1
x.columns.name, x.index.name = 'start', 'end'

# let's make sure we only calculate a return when start
# is less than end.
y = x.stack().reset_index()
y = y[y.start < y.end]

# if rolling isn't None then we care about limiting the
# window over which we calculate max draw down
if not rolling is None:
y = y[y.end - y.start <= rolling]

# my choice is to return the periods and the actual max
# draw down
z = y.set_index(['start', 'end']).iloc[:, 0]
return z.min(), z.argmin()


For comparison purposes, I've included a looping version (without comments)

def max_dd_loop(returns):
max_so_far = None
start, end = None, None
for r_start in r.index:
for r_end in r.index:
if r_start < r_end:
current = r.ix[r_end] / r.ix[r_start] - 1
if (max_so_far is None) or (current < max_so_far):
max_so_far = current
start, end = r_start, r_end
return max_so_far, (start, end)


Create a random return series

returns = pd.Series(np.random.randn(1000) / 100 + 0.001)


now calculate max draw down and print time it took

stamp = pd.Timestamp.now()
max_dd(returns)
delta_vector = pd.Timestamp.now() - stamp
print delta_vector

(-0.13730942629746501, (730, 787))
0 days 00:00:00.088714


Do the same for looped version

stamp = pd.Timestamp.now()
max_dd_loop(returns)
delta_loop = pd.Timestamp.now() - stamp
print delta_loop

(-0.13730942629746501, (730, 787))
0 days 00:00:26.465571
print delta_loop / delta_vector

298.324627455


This is a huge improvement

Here is an O(n) version in Java (easily adaptable to another language) - the idea is to keep track of the highest price seen so far. Since you need to visit all the prices to calculate the result, I don't think you can find an algorithm that's more efficient.

public static double maxDrawdown(double[] prices) {
if (prices.length <= 1) return 0;

double maxPrice = prices[0];
double maxDd = 0;

for (int i = 1; i < prices.length; i++) {
if (prices[i] > maxPrice) maxPrice = prices[i];
else if (prices[i] < maxPrice) maxDd = Math.min(maxDd, prices[i] / maxPrice - 1);
}

return maxDd;
}


Inspired by this post.

I use a quick and dirty C++ solution:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
std::istream_iterator<double> start(file);
std::istream_iterator<double> end;
std::vector<double> balance(start, end);

auto max = 0.;
auto maxDrawdown = 0.;
for (auto it = balance.begin(); it != balance.end(); ++it) {
if (*it > max) {
max = *it;
auto minElement = std::min_element(std::next(it), balance.end());
maxDrawdown = std::max(maxDrawdown, max - *minElement);
}
}

std::cout << maxDrawdown << std::endl;
}


hope this helps.