  ## 1 For $k=1,\ldots,K$, Sample 
$$x_{k}^{(i+1)}\sim p\big{(}x_{k}\,|x_{1:k-1}^{(i+1)},x_{k+1:K}^{(i)}\big{)}\tag{15}$$
In contrast to the Metropolis algorithm, where the new candidate is a vector x', the Gibbs sampler uses the exact marginal p ( x | x − k ) as the proposal distribution. At each step, the sampler updates only one coordinate of the current state x, namely x k, and the new candidate is guaranteed to be accepted.

Note that, in principle we don't need to sample x k sequentially, i.e., we can choose k randomly provided that each slice is visited equally often in the limit. However, a deterministic scan algorithm where k = 1 , . . K , provides important time savings in the type of models that we consider here.

## 3.1  Simulated Annealing And Iterative Improvement

Now we shift our focus from sampling to MAP state estimation.  In principle, one can use the samples generated by any sampling algorithm (Metropolis-Hastings or Gibbs) to estimate the MAP state x* of p(x) by argmaxp(x(i). However, unless the posterior is very much concentrated around the MAP state, the sampler may not visit x* even though the samples x ( ) are obtained from the stationary distribution. In this case, the problem can be simply reformulated to sample not from p ( x ) but from a distribution that is concentrated at local maxima of p ( x ).  One su class of distributions are given by p p , ( x ) å p ( x ) oj .  A sequence of exponents ρ 1 < ρ 2 < · · < ρ i < · · is called to be a cooling schedule or annealing schedule owing to the inverse temperature interpretation of ρ j in statistical mechanics, hence the nme Simulated Annealing (SA) (Aarts & van Laarhoven, 1985). When ρ i → ∞ sufficiently slowly in j , the cascade of MCMC samplers each with the stationary distribution p o (x) is guaranteed (in the limit) to converge to the global maximum of p ( x ).  Unfortunately, for this convergence result to hold, the cooling schedule must go very slowly (in fact, logarithmically)
to infinity. In practice, faster cooling schedules must be employed.

Iterative improvement (II) (Aarts & van Laarhoven, 1985) is a heuristic simulated annaling algorithm with a very fast cooling schedule. In fact, ρ j = ∞ for all j . The eventual advantage of this greedy algorithm is that it converges in a few iterations to a local maximum. By restarting many times from different initial configurations x , one hopes to find different local maxima of p ( x ) and eventually visit the MAP state x * . In practice, by using the II heuristic one may find better solutions than SA for a limited computation time.

From an implementation point of view, it is trivial to convert MCMC code to SA (or II)
code. For example, consider the Gibbs sampler. To implement SA, we need to construct a cascade of Gibbs samplers, each with stationary distribution p (x) ρ i . The exact one time slice marginal of this distribution is p ( x k | x - k ) β j .  So, SA just samples from the actual (temperature=1) marginal p(xk | x_k ) raised to a power pj.

## 3.2 The Switching State Space Model And Map Estimation

To solve the rhythm quantization problem, we need to calculate the MAP state of the posterior in Eq. 11

$$\begin{array}{r c l}{{p(\gamma_{1:K}|y_{0:K})}}&{{\propto}}&{{p(\gamma_{1:K})\int d z_{0:K}p{\big(}y_{0:K}|z_{0:K},\,\gamma_{1:K}{\big)}p{\big(}z_{0:K}|\gamma_{1:K}{\big)}}}\end{array}$$
$$(16)$$
