  We propose a randomized a posteriori error estimator for reduced order
approximations of parametrized (partial) differential equations. The error
estimator has several important properties: the effectivity is close to unity
with prescribed lower and upper bounds at specified high probability; the
estimator does not require the calculation of stability (coercivity, or
inf-sup) constants; the online cost to evaluate the a posteriori error
estimator is commensurate with the cost to find the reduced order
approximation; the probabilistic bounds extend to many queries with only modest
increase in cost. To build this estimator, we first estimate the norm of the
error with a Monte-Carlo estimator using Gaussian random vectors whose
covariance is chosen according to the desired error measure, e.g. user-defined
norms or quantity of interest. Then, we introduce a dual problem with random
right-hand side the solution of which allows us to rewrite the error estimator
in terms of the residual of the original equation. In order to have a
fast-to-evaluate estimator, model order reduction methods can be used to
approximate the random dual solutions. Here, we propose a greedy algorithm that
is guided by a scalar quantity of interest depending on the error estimator.
Numerical experiments on a multi-parametric Helmholtz problem demonstrate that
this strategy yields rather low-dimensional reduced dual spaces.
