As operational variational analysis schemes evolve to accommodate more adaptive representations of the estimated background error covariance, including inhomogeneities and anisotropies, there is a corresponding greater need for objective statistical methods to establish the parameters of the covariances involved on a case-to-case basis. In their traditional form, methods for maximum-likelihood and Bayesian estimation, while statistically `efficient', are prohibitively expensive to apply directly when the measurement datasets are as large as those typical of a modern meteorological assimilation system. However, the Monte-Carlo method of randomized trace estimation, proposed in another context by D. Girard, which sidesteps the exorbitant cost of directly estimating the trace of a large symmetric matrix, can be exploited to eliminate the computational bottle-neck of the Bayesian estimation problem. This makes it possible to extract objective real-time estimates of several covariance parameters simultaneously from the observation data. We present an outline of the method and preliminary results in the context of NCEP's regional 3D variational analysis scheme.