The Rearrangement Algorithm
The Rearrangement Algorithm (RA) is a practical and straightforward method to determine the worst-VaR sum. The RA works by iteratively making each marginal crossed (counter-monotonic) with the sum of the other marginal distributions. It is easy to program and suitable for problems involving hundreds of variables and millions of simulations.
The Rearrangement Algorithm was introduced in Puccetti and Ruschendorf [2012] and subsequently improved in Embrechts et al. [2013].
Algorithm Input: Input samples are arranged in a matrix \(\tilde X = (x_{ij})\) with \(i=1,\dots, M\) rows corresponding to the simulations and \(j=1,\dots, d\) columns corresponding to the different marginals. VaR probability parameter \(p\). Accuracy threshold \(\epsilon>0\) specifies convergence criterion.
Algorithm Steps
Sort each column of \(\tilde X\) in descending order.
Set \(N := \lceil (1-p)M \rceil\).
Create matrix \(X\) as the \(N\times d\) submatrix of the top \(N\) rows of \(\tilde X\).
Randomly permute rows within each column of \(X\).
Do Loop
Create a new matrix \(Y\) as follows. For column \(j=1,\dots,d\):
Create a temporary matrix \(V_j\) by deleting the \(j\)th column of \(X\)
Create a column vector \(v\) whose \(i\)th element equals the sum of the elements in the \(i\)th row of \(V_j\)
Set the \(j\)th column of \(Y\) equal to the \(j\)th column of \(X\) arranged to have the opposite order to \(v\), i.e., the largest element in the \(j\)th column of \(X\) is placed in the row of \(Y\) corresponding to the smallest element in \(v\), the second largest with second smallest, etc.
Compute \(y\), the \(N\times 1\) vector with \(i\)th element equal to the sum of the elements in the \(i\)th row of \(Y\).
Compute \(x\) from \(X\) similarly.
Compute \(y^{\ast}:=\min(y)\), the smallest element of \(y\).
Compute \(x^{\ast}:=\min(x)\).
If \(y^{\ast}-x^{\ast} \ge \epsilon\) then set \(X:=Y\) and repeat the loop.
If \(y^{\ast}-x^{\ast} < \epsilon\) then break from the loop.
Stack \(Y\) on top of the \((M-N)\times d\) submatrix of \(M-N\) bottom rows of \(\tilde X\).
Output: The result approximates the worst \(\mathsf{VaR}_p\) arrangement of \(\tilde X\).
Only the top \(N\) values need special treatment; all the smaller values can be combined arbitrarily because they aren’t included in the worst-VaR rearrangement. Given that \(X\) consists of the worst \(1-p\) proportion of each marginal, the required estimated \(\mathsf{VaR}_p\) is the least row sum of \(Y\), that is \(y^{\ast}\). In implementation, \(x^{\ast}\) can be carried forward as the \(y^{\ast}\) from the previous iteration and not recomputed. The statistics \(x^{\ast}\) and \(y^{\ast}\) can be replaced with the variance of the row-sums of \(X\) and \(Y\) and yield essentially the same results.
Embrechts et al. [2013] report that while there is no analytic proof the algorithm always works, it performs very well based on examples and tests where we can compute the answer analytically.
Worked Example
Setup. Compute the worst \(\mathsf{VaR}_{0.99}\) of the sum of lognormal distributions with mean 10 and coefficient of variations 1, 2, and 3 by applying the Rearrangement Algorithm to a stratified sample of \(N=40\) observations at and above the 99th percentile for the matrix \(X\).
Solution. The table below shows the input and output of the Rearrangement Algorithm.
\(x_0\) |
\(x_1\) |
\(x_2\) |
Sum |
\(s_0\) |
\(s_1\) |
\(s_2\) |
Max VaR |
|---|---|---|---|---|---|---|---|
49.0 |
85.6 |
107.9 |
242.5 |
87.1 |
124.6 |
141.1 |
352.8 |
49.4 |
86.6 |
109.5 |
245.6 |
70.8 |
113.6 |
169.3 |
353.7 |
49.9 |
87.7 |
111.2 |
248.8 |
98.8 |
127.9 |
127.4 |
354.1 |
50.3 |
88.9 |
112.9 |
252.1 |
79.9 |
118.8 |
155.5 |
354.1 |
50.7 |
90.0 |
114.7 |
255.5 |
83.1 |
107.1 |
164.3 |
354.5 |
51.2 |
91.3 |
116.6 |
259.1 |
92.1 |
139.7 |
122.8 |
354.6 |
51.6 |
92.6 |
118.6 |
262.8 |
67.7 |
135.4 |
151.5 |
354.7 |
52.1 |
93.9 |
120.6 |
266.6 |
108.8 |
116.1 |
129.8 |
354.7 |
52.6 |
95.3 |
122.8 |
270.7 |
62.8 |
105.1 |
186.9 |
354.8 |
53.2 |
96.7 |
125.0 |
274.9 |
63.9 |
170.6 |
120.6 |
355.0 |
53.7 |
98.3 |
127.4 |
279.3 |
69.2 |
111.3 |
174.6 |
355.1 |
54.3 |
99.9 |
129.8 |
284.0 |
72.7 |
144.5 |
138.1 |
355.3 |
54.9 |
101.5 |
132.4 |
288.8 |
59.9 |
101.5 |
194.1 |
355.5 |
55.5 |
103.3 |
135.2 |
293.9 |
127.5 |
103.3 |
125.0 |
355.8 |
56.1 |
105.1 |
138.1 |
299.3 |
60.8 |
162.6 |
132.4 |
355.9 |
56.8 |
107.1 |
141.1 |
305.0 |
66.3 |
109.1 |
180.5 |
355.9 |
57.5 |
109.1 |
144.4 |
311.1 |
61.8 |
149.8 |
144.4 |
356.0 |
58.3 |
111.3 |
147.9 |
317.5 |
65.0 |
155.8 |
135.2 |
356.0 |
59.1 |
113.6 |
151.5 |
324.3 |
74.8 |
121.6 |
159.7 |
356.1 |
59.9 |
116.1 |
155.5 |
331.5 |
77.1 |
131.5 |
147.9 |
356.5 |
60.8 |
118.8 |
159.7 |
339.3 |
59.1 |
179.9 |
118.6 |
357.5 |
61.8 |
121.6 |
164.3 |
347.7 |
58.3 |
99.9 |
202.0 |
360.1 |
62.8 |
124.6 |
169.3 |
356.7 |
57.5 |
191.1 |
116.6 |
365.3 |
63.9 |
127.9 |
174.6 |
366.4 |
56.8 |
98.3 |
210.9 |
366.0 |
65.0 |
131.5 |
180.5 |
377.0 |
56.1 |
96.7 |
221.0 |
373.9 |
66.3 |
135.4 |
186.9 |
388.7 |
55.5 |
205.1 |
114.7 |
375.4 |
67.7 |
139.7 |
194.1 |
401.5 |
54.9 |
95.3 |
232.7 |
382.9 |
69.2 |
144.5 |
202.0 |
415.7 |
54.3 |
223.3 |
112.9 |
390.5 |
70.8 |
149.8 |
210.9 |
431.6 |
53.7 |
93.9 |
246.3 |
393.9 |
72.7 |
155.8 |
221.0 |
449.5 |
53.2 |
92.6 |
262.5 |
408.2 |
74.8 |
162.6 |
232.7 |
470.1 |
52.6 |
248.7 |
111.2 |
412.5 |
77.1 |
170.6 |
246.3 |
494.0 |
52.1 |
91.3 |
282.3 |
417.7 |
79.9 |
179.9 |
262.5 |
522.3 |
51.2 |
288.1 |
109.5 |
448.8 |
83.1 |
191.1 |
282.3 |
556.5 |
51.6 |
90.0 |
307.2 |
448.9 |
87.1 |
205.1 |
307.2 |
599.4 |
50.7 |
88.9 |
340.0 |
479.6 |
92.1 |
223.3 |
340.0 |
655.5 |
50.3 |
87.7 |
386.6 |
524.6 |
98.8 |
248.7 |
386.6 |
734.1 |
49.9 |
366.9 |
107.9 |
524.7 |
108.8 |
288.1 |
461.1 |
858.0 |
49.4 |
86.6 |
461.1 |
597.2 |
127.5 |
366.9 |
615.7 |
1110.1 |
49.0 |
85.6 |
615.7 |
750.3 |
The table illustrates the worst-case VaR may be substantially higher than when the marginals are perfectly correlated, here 45 percent higher at 352.8 vs. 242.5. The form of the output columns shows the two part structure. There is a series of values up to 356 involving moderate sized losses from each marginal with approximately the same total. The larger values of the rearrangement are formed from a large value from one marginal combined with smaller values from the other two.
The bold entry \(366.4\) indicates when the comonotonic sum of marginals exceeds the worst 0.99-VaR arrangement.
Performing the same calculation with \(N=1000\) samples from the largest 1 percent of each marginal produces an estimated worst VaR of 360.5.
The following code replicates this calculation in aggregate. The answer relies on random seeds and is slightly different from the table above.
In [1]: import aggregate as agg
In [2]: import numpy as np
In [3]: import pandas as pd
In [4]: import scipy.stats as ss
In [5]: ps = np.linspace(0.99, 1, 40, endpoint=False)
In [6]: params = {i: agg.mu_sigma_from_mean_cv(10, i) for i in [1,2,3]}
In [7]: df = pd.DataFrame({f'x_{i}': ss.lognorm(params[i][1],
...: scale=np.exp(params[i][0])).isf(1-ps)
...: for i in [1,2,3]}, index=ps)
...:
In [8]: df_ra = agg.rearrangement_algorithm_max_VaR(df)
In [9]: agg.qd(df_ra, float_format=lambda x: f'{x:.1f}', max_rows=100)
x_1 x_2 x_3 total
39 65.5 110.4 176.9 352.8
11 71.3 120.1 161.9 353.3
22 66.8 136.9 149.9 353.5
14 109.5 112.6 131.6 353.7
3 99.4 117.4 137.0 353.8
27 69.7 164.3 120.2 354.2
18 73.2 141.2 140.0 354.4
38 68.2 114.9 171.5 354.5
24 92.6 132.9 129.1 354.7
37 63.2 157.4 134.3 354.9
5 64.3 108.3 182.8 355.5
28 61.3 151.4 143.1 355.7
35 75.3 122.9 157.6 355.8
4 87.6 146.0 122.3 356.0
16 62.2 104.5 189.3 356.0
19 80.4 129.3 146.4 356.1
33 83.7 106.3 166.5 356.5
12 59.5 101.0 196.5 357.1
36 60.4 172.3 124.5 357.2
23 77.7 126.0 153.6 357.2
2 128.2 102.7 126.8 357.7
6 58.7 181.7 118.3 358.7
0 58.0 99.4 204.6 361.9
1 57.3 193.0 116.4 366.7
15 56.6 97.9 213.6 368.0
13 55.9 96.4 223.8 376.1
10 55.3 207.1 114.5 377.0
29 54.7 95.0 235.6 385.3
34 54.1 225.5 112.8 392.4
32 53.6 93.7 249.3 396.5
26 53.0 92.4 265.7 411.1
9 52.5 251.0 111.1 414.6
21 52.0 91.1 285.6 428.8
7 51.6 290.7 109.5 451.8
25 51.1 89.9 310.8 451.8
30 50.7 88.8 343.9 483.4
17 50.3 370.1 107.9 528.2
20 49.8 87.7 391.0 528.5
31 49.4 86.6 466.1 602.1
8 49.0 85.6 622.1 756.7
There are several important points to note about the Rearrangement Algorithm output and the failure of subadditivity it induces. They mirror the case \(d=2\).
The dependence structure does not have right tail dependence.
In Table 1, the comonotonic sum is greater than the maximum VaR sum for the top 40 percent observations, above 366.4. The algorithm output is tailored to a specific value of \(p\) and does not work for other \(p\)s. It produces relatively thinner tails for higher values of \(p\) than the comonotonic copula.
The algorithm works for any non-trivial marginal distributions—it is universal.
The implied dependence structure specifies only how the larger values of each marginal are related; any dependence structure can be used for values below \(\mathsf{VaR}_p\).
The Rearrangement Algorithm gives a definitive answer to the question “Just how bad could things get?” and perhaps provides a better base against which to measure diversification effect than either independence or the comonotonic copula. While the multivariate structure it reveals is odd and specific to \(p\), it is not wholly improbable. It pinpoints a worst-case driven by a combination of moderately severe, but not extreme, tail event outcomes. Anyone who remembers watching their investment portfolio during a financial crisis has seen that behavior before! It is a valuable additional feature for any risk aggregation software.