  We introduce a framework for efficient Markov Chain Monte Carlo (MCMC)
algorithms targeting discrete-valued high-dimensional distributions, such as
posterior distributions in Bayesian variable selection (BVS) problems. We show
that many recently introduced algorithms, such as the locally informed sampler
and the Adaptively Scaled Individual adaptation sampler (ASI), can be viewed as
particular cases within the framework. We then describe a novel algorithm, the
Adaptive Random Neighbourhood Informed sampler (ARNI), by combining ideas from
both of these existing approaches. We show using several examples of both real
and simulated datasets that a computationally efficient point-wise
implementation (PARNI) leads to relatively more reliable inferences on a range
of variable selection problems, particularly in the very large $p$ setting.
