  The popularity of Adaptive MCMC has been fueled on the one hand by its
success in applications, and on the other hand, by mathematically appealing and
computationally straightforward optimisation criteria for the Metropolis
algorithm acceptance rate (and, equivalently, proposal scale). Similarly
principled and operational criteria for optimising the selection probabilities
of the Random Scan Gibbs Sampler have not been devised to date.
  In the present work, we close this gap and develop a general purpose Adaptive
Random Scan Gibbs Sampler that adapts the selection probabilities. The
adaptation is guided by optimising the $L_2-$spectral gap for the target's
Gaussian analogue, gradually, as target's global covariance is learned by the
sampler. The additional computational cost of the adaptation represents a small
fraction of the total simulation effort. ` We present a number of moderately-
and high-dimensional examples, including truncated Gaussians, Bayesian
Hierarchical Models and Hidden Markov Models, where significant computational
gains are empirically observed for both, Adaptive Gibbs, and Adaptive
Metropolis within Adaptive Gibbs version of the algorithm. We argue that
Adaptive Random Scan Gibbs Samplers can be routinely implemented and
substantial computational gains will be observed across many typical Gibbs
sampling problems.
  We shall give conditions under which ergodicity of the adaptive algorithms
can be established.
