  The classical approach to system identification is based on stochastic
assumptions about the measurement error, and provides estimates that have
random nature. Worst-case identification, on the other hand, only assumes the
knowledge of deterministic error bounds, and establishes guaranteed estimates,
thus being in principle better suited for the use in control design. However, a
main limitation of such deterministic bounds lies on their potential
conservatism, thus leading to estimates of restricted use.
  In this paper, we propose a rapprochement between the stochastic and
worst-case paradigms. In particular, based on a probabilistic framework for
linear estimation problems, we derive new computational results. These results
combine elements from information-based complexity with recent developments in
the theory of randomized algorithms. The main idea in this line of research is
to "discard" sets of measure at most \epsilon, where \epsilon is a
probabilistic accuracy, from the set of deterministic estimates. Therefore, we
are decreasing the so-called worst-case radius of information at the expense of
a given probabilistic ``risk."
  In this setting, we compute a trade-off curve, called violation function,
which shows how the radius of information decreases as a function of the
accuracy. To this end, we construct randomized and deterministic algorithms
which provide approximations of this function. We report extensive simulations
showing numerical comparisons between the stochastic, worst-case and
probabilistic approaches, thus demonstrating the efficacy of the methods
proposed in this paper.
