Algorithms for Retrospective and Rolling Maximum Drawdown
Article Quant Q&A · Author: jbmusso
Summary
The document compares ways to compute maximum drawdown from a price or return series. For a single pass over a fixed history, track the running peak and the largest decline that follows it; define the lookback window carefully because the peak must precede the trough. For rolling windows, an answer describes maintaining state as each observation arrives and recomputing when an old peak leaves the window. Other examples use cumulative returns, pairwise peak-to-later-value comparisons, or library operations to find the worst peak-to-trough interval.
The discussion includes timing comparisons for a rolling implementation against repeated full-window recalculation, and for a vectorized Python approach against a nested-loop version on a random series. These examples illustrate potential efficiency gains, but are specific to the implementations and test setup shown. The central linear scan is suitable for a fixed series; rolling-window bookkeeping is more involved, and reported timings do not establish a universal fastest method.
Key ideas
- A single pass can find the worst drawdown by tracking the highest value seen and subsequent declines.
- The lookback window and whether the measure uses prices or compounded returns must be defined.
- Rolling windows require handling cases where the peak or trough leaves the active window.
- The document reports timing comparisons, but their results depend on the implementations and test data.
Tags
Full text
# Fastest algorithm for calculating retrospective maximum drawdown
# 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.
## Answer by Matt Wolf (score 7)
https://quant.stackexchange.com/a/4887
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).
## Answer by DaManJ (score 6)
https://quant.stackexchange.com/a/14157
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));
}
```
## Answer by fawce (score 3)
https://quant.stackexchange.com/a/4912
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
## Answer by Vim (score 3)
https://quant.stackexchange.com/a/43544
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.
## Answer by Brian B (score 1)
https://quant.stackexchange.com/a/4888
(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.
## Answer by piRSquared (score 1)
https://quant.stackexchange.com/a/25503
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 = pd.DataFrame(returns).add(1).cumprod()
# 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
r = returns.add(1).cumprod()
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
## Answer by assylias (score 1)
https://quant.stackexchange.com/a/34153
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.
## Answer by Stefano Falasca (score 1)
https://quant.stackexchange.com/a/45043
I use a quick and dirty C++ solution:
```
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::ifstream file("/home/sfalasca/pads2/build/devel/pads/balance.txt");
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.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.