  In the current work we present two generalizations of the Parallel Tempering
algorithm, inspired by the so-called continuous-time Infinite Swapping
algorithm. Such a method, found its origins in the molecular dynamics
community, and can be understood as the limit case of the continuous-time
Parallel Tempering algorithm, where the (random) time between swaps of states
between two parallel chains goes to zero. Thus, swapping states between chains
occurs continuously. In the current work, we extend this idea to the context of
time-discrete Markov chains and present two Markov chain Monte Carlo algorithms
that follow the same paradigm as the continuous-time infinite swapping
procedure. We analyze the convergence properties of such discrete-time
algorithms in terms of their spectral gap, and implement them to sample from
different target distributions. Numerical results show that the proposed
methods significantly improve over more traditional sampling algorithms such as
Random Walk Metropolis and (traditional) Parallel Tempering.
