  Subset weighted-Tempered Gibbs Sampler (wTGS) has been recently introduced by
Jankowiak to reduce the computation complexity per MCMC iteration in
high-dimensional applications where the exact calculation of the posterior
inclusion probabilities (PIP) is not essential. However, the Rao-Backwellized
estimator associated with this sampler has a high variance as the ratio between
the signal dimension and the number of conditional PIP estimations is large. In
this paper, we design a new subset weighted-Tempered Gibbs Sampler (wTGS) where
the expected number of computations of conditional PIPs per MCMC iteration can
be much smaller than the signal dimension. Different from the subset wTGS and
wTGS, our sampler has a variable complexity per MCMC iteration. We provide an
upper bound on the variance of an associated Rao-Blackwellized estimator for
this sampler at a finite number of iterations, $T$, and show that the variance
is $O\big(\big(\frac{P}{S}\big)^2 \frac{\log T}{T}\big)$ for a given dataset
where $S$ is the expected number of conditional PIP computations per MCMC
iteration. Experiments show that our Rao-Blackwellized estimator can have a
smaller variance than its counterpart associated with the subset wTGS.
