  We consider a multi-step algorithm for the computation of the historical
expected shortfall such as defined by the Basel Minimum Capital Requirements
for Market Risk. At each step of the algorithm, we use Monte Carlo simulations
to reduce the number of historical scenarios that potentially belong to the set
of worst scenarios. The number of simulations increases as the number of
candidate scenarios is reduced and the distance between them diminishes. For
the most naive scheme, we show that the L p-error of the estimator of the
Expected Shortfall is bounded by a linear combination of the probabilities of
inversion of favorable and unfavorable scenarios at each step, and of the last
step Monte Carlo error associated to each scenario. By using concentration
inequalities, we then show that, for sub-gamma pricing errors, the
probabilities of inversion converge at an exponential rate in the number of
simulated paths. We then propose an adaptative version in which the algorithm
improves step by step its knowledge on the unknown parameters of interest: mean
and variance of the Monte Carlo estimators of the different scenarios. Both
schemes can be optimized by using dynamic programming algorithms that can be
solved off-line. To our knowledge, these are the first non-asymptotic bounds
for such estimators. Our hypotheses are weak enough to allow for the use of
estimators for the different scenarios and steps based on the same random
variables, which, in practice, reduces considerably the computational effort.
First numerical tests are performed.
