The penalised t-walk

This vignette is precomputed: its code is run when the package is developed, not when it is installed, because some experiments take a few minutes. The full source is in vignettes/penalised_twalk.Rmd.orig.

The four moves of the t-walk adapt to the scale and correlation of the target, but like most MCMC samplers the t-walk can get trapped in one mode when the modes are separated by regions of very low density. Medina-Aguayo and Christen proposed a fifth move for this situation:

Medina-Aguayo, F. J. and Christen, J. A. (2022). Penalised t-walk MCMC. Journal of Statistical Planning and Inference, 221, 230–247. doi:10.1016/j.jspi.2022.04.008

Rtwalk implements the gradient-free version of the move (Section 2.3 of the paper), which needs nothing beyond the log posterior. It is off by default and is turned on with twalk_control(penalty_prob = ...). This document explains the move, checks the implementation against the paper, and reproduces the paper’s examples.

library(Rtwalk)

1. The move

The t-walk keeps two points, \(x\) and \(x'\), and targets \(\pi(x)\pi(x')\). The penalised move summarises the current pair by its midpoint \(\mu = (x + x')/2\) and its coordinate-wise scale \(s = |x - x'|\). It draws a new centre \(w\) from a heavy-tailed distribution around \(\mu\) whose density has been penalised near \(\mu\), so that points far from the current location are favoured, and then shifts both points by the same vector:

\[u = x + (w - \mu), \qquad v = x' + (w - \mu) \qquad \text{(equation 5)},\]

or, with the labels exchanged, \(u = x' + (w - \mu)\) and \(v = x + (w - \mu)\) (equation 6). The existing four moves update only one of the two points at a time, which the authors note could leave them stuck in different modes; this move carries both together.

The default configuration of the paper (Section 3), which Rtwalk uses, is:

Paper Content Rtwalk
Sec. 2.3, Algorithm 2 rejection sampler for \(g\varphi\) penalty_shift()
Sec. 2.3, eqs. (5)–(6) shift of both points, optional exchange penalty_step() in the engines
Sec. 2.3, eq. (9) acceptance ratio see below
Sec. 3 \(\kappa = 3\), \(t_1\) proposal, \(t_2\) penalty twalk_control(penalty_kappa = 3)
Sec. 3, Example 2 move used in about 10% of iterations twalk_control(penalty_prob = 0.1)

The acceptance ratio

Equation (9) of the paper gives the Metropolis–Hastings ratio

\[r = \frac{\pi(u)\,\pi(v)\; g(\mu_{xx'} \mid u, v)\; \varphi_{uv}(\mu_{xx'})} {\pi(x)\,\pi(x')\; g(w \mid x, x')\; \varphi_{xx'}(w)}.\]

It simplifies. The shift preserves the difference between the two points, \(|u - v| = |x - x'|\), so the scale is the same before and after the move, and the midpoint of \((u, v)\) is \(w\). Since \(g\) and \(\rho\) are symmetric location-scale densities, the reverse proposal has the same density as the forward one: \(g(\mu_{xx'} \mid u, v) = g(w \mid x, x')\) and \(\varphi_{uv}(\mu_{xx'}) = \varphi_{xx'}(w)\). The normalising constants of the penalised proposals are equal too (Proposition 2 of the paper). Each of equations (5) and (6) is its own inverse, so choosing between them with a fixed probability (Rtwalk uses 1/2) keeps the move reversible. What remains is

\[r = \frac{\pi(u)\,\pi(v)}{\pi(x)\,\pi(x')}.\]

A penalised move therefore costs two evaluations of the log posterior (Rtwalk skips the second one when the first point falls outside the support), and no proposal density needs to be computed.

Coordinates in which \(x_j = x'_j\) have zero scale. They are left unchanged, and the dimension of \(\rho\) is then the number of remaining coordinates; the move is still reversible because it preserves which coordinates are equal.

2. The rejection sampler: Table 1 of the paper

By Proposition 2 of the paper, the acceptance probability of the rejection step does not depend on the state; it is \(Z = 1 - \rho(0)^{-1}\int g(w)\,\rho(\kappa w)\,dw\), and Table 1 reports it for several dimensions \(d\) and values of \(\kappa\). Since \(Z\) is the mean of \(\varphi\) under the proposal, it can be estimated precisely from draws of \(g\) alone. With \(z \sim N(0, I_d)\) and \(\zeta \sim N(0, 1)\), a draw of the standardised proposal is \(\kappa z/|\zeta|\):

penalty_rate <- function(d, kappa, n = 1e6) {
  zeta <- rnorm(n)
  q <- kappa^2 * rowSums(matrix(rnorm(n * d), n)^2) / zeta^2
  mean(1 - (1 + q / 2)^(-(d + 2) / 2))
}

set.seed(1)
paper <- rbind(
  "d = 2" = c(0.8671, 0.9275, 0.9551),
  "d = 4" = c(0.9802, 0.9931, 0.9970),
  "d = 8" = c(0.9993, 0.9999, NA)
)
ours <- t(sapply(c(2, 4, 8), function(d) {
  sapply(c(2, 3, 4), function(kappa) penalty_rate(d, kappa))
}))
dimnames(ours) <- dimnames(paper) <- list(rownames(paper), paste("kappa =", 2:4))
round(paper, 4)
#>       kappa = 2 kappa = 3 kappa = 4
#> d = 2    0.8671    0.9275    0.9551
#> d = 4    0.9802    0.9931    0.9970
#> d = 8    0.9993    0.9999        NA
round(ours, 4)
#>       kappa = 2 kappa = 3 kappa = 4
#> d = 2    0.8695    0.9268    0.9536
#> d = 4    0.9791    0.9931    0.9971
#> d = 8    0.9994    0.9999    1.0000

The two tables agree to the precision of the Monte Carlo estimates (the paper reports the entry for \(d = 8\), \(\kappa = 4\) only as \(> 1 - 10^{-5}\)). The same rate can be measured on the sampler itself, from the number of trials that penalty_shift() needs:

set.seed(2)
trials <- vapply(seq_len(1e5), function(i) {
  Rtwalk:::penalty_shift(c(0, 0), c(1, 1), kappa = 3)$n_trials
}, integer(1))
c(paper = 0.9275, sampler = 1e5 / sum(trials))
#>     paper   sampler 
#> 0.9275000 0.9269817

The distribution of the shift itself can be compared with the penalised density. In one dimension with scale 1 the shift has density proportional to a Cauchy density with scale \(\kappa\) times \(1 - (1 + t^2/2)^{-3/2}\):

set.seed(3)
shifts <- vapply(seq_len(1e5), function(i) {
  Rtwalk:::penalty_shift(0, 1, kappa = 3)$delta
}, numeric(1))

penalised <- function(t) dcauchy(t, scale = 3) * (1 - (1 + t^2 / 2)^(-3 / 2))
# The histogram shows the draws in (-20, 20), so normalise over that range.
z_const <- integrate(penalised, -20, 20)$value

kept <- shifts[abs(shifts) < 20]
hist(kept, breaks = 200, freq = FALSE, border = NA, col = "grey75",
     main = "Shift of the penalised move (d = 1, scale 1)", xlab = "w - mu",
     ylim = c(0, 0.09))
curve(penalised(x) / z_const, add = TRUE, lwd = 2, col = "firebrick", n = 1001)
legend("topright", c("draws", "penalised density"), bty = "n",
       fill = c("grey75", NA), border = NA, lwd = c(NA, 2),
       col = c(NA, "firebrick"))
plot of chunk shift-density

plot of chunk shift-density

The density vanishes at the current midpoint, so the move never proposes to stay where the pair is.

3. Example 2: two well-separated modes

Example 1 of the paper is a mixture of two bivariate Gaussians with very different shapes,

\[\pi(x) = 0.5\,N(x \mid \mu_1, \Sigma_1) + 0.5\,N(x \mid \mu_2, \Sigma_2),\]

with \(\mu_1 = (0, 0)\), \(\mu_2 = (20, -20)\), unit variances and correlation 0.1 in \(\Sigma_1\), and standard deviations 4 and 5 with correlation 0.8 in \(\Sigma_2\). Example 2 runs the standard and the penalised t-walk on it for 5 million iterations, with the penalised move in 10% of them.

mixture <- function(w) {
  mu2 <- c(20, -20)
  sigma1 <- matrix(c(1, 0.1, 0.1, 1), 2)
  sigma2 <- matrix(c(16, 16, 16, 25), 2)
  prec1 <- solve(sigma1)
  prec2 <- solve(sigma2)
  const1 <- log(w) - 0.5 * log(det(sigma1))
  const2 <- log(1 - w) - 0.5 * log(det(sigma2))
  function(x) {
    d2 <- x - mu2
    a <- const1 - 0.5 * sum(x * (prec1 %*% x))
    b <- const2 - 0.5 * sum(d2 * (prec2 %*% d2))
    m <- max(a, b)
    m + log(exp(a - m) + exp(b - m))
  }
}
log_example1 <- mixture(0.5)

To see how often each sampler leaves the first mode, we run 16 chains of 5 million iterations each, all started as in the paper with both points near the first mode, and store every 10th iteration.

run_example2 <- function(penalty_prob) {
  set.seed(2022)
  start <- matrix(c(0, 0), 16, 2, byrow = TRUE)
  twalk(log_example1, n_iter = 5e6, x0 = start, xp0 = start + 0.5,
        n_chains = 16, n_cores = min(8, parallel::detectCores()), thin = 10,
        show_progress = FALSE,
        control = twalk_control(penalty_prob = penalty_prob,
                                store_companion = FALSE))
}
standard <- run_example2(0)
penalised <- run_example2(0.1)
chain_stats <- function(fit) {
  per_chain <- t(vapply(fit$individual_chains, function(chain) {
    in_second <- chain$samples[, 1] > 10
    c(reached = any(in_second), switches = sum(diff(in_second) != 0),
      second = mean(in_second))
  }, numeric(3)))
  stats <- fit$kernel_statistics
  c(
    "chains that reach the second mode" = sum(per_chain[, "reached"]),
    "median mode switches per chain" = stats::median(per_chain[, "switches"]),
    "mean acceptance (%)" = 100 * fit$acceptance_rate,
    "penalised move acceptance (%)" =
      if (nrow(stats) == 5) 100 * stats$acceptance_rate[5] else NA,
    "evaluations per iteration" = fit$n_evaluations / fit$total_iterations
  )
}
round(cbind(standard = chain_stats(standard), penalised = chain_stats(penalised)), 2)
#>                                   standard penalised
#> chains that reach the second mode     9.00     16.00
#> median mode switches per chain      268.00   1362.50
#> mean acceptance (%)                  35.46     19.37
#> penalised move acceptance (%)           NA      3.84
#> evaluations per iteration             1.00      1.10
op <- par(mfrow = c(2, 1), mar = c(4, 4, 2, 1))
keep <- seq(1, 5e5, by = 50)
for (name in c("standard", "penalised")) {
  chain <- get(name)$individual_chains[[1]]
  matplot(10 * keep, chain$samples[keep, ], type = "l", lty = 1,
          col = c("steelblue", "darkorange"), xlab = "iteration", ylab = "x",
          main = paste(name, "t-walk, chain 1"))
}
plot of chunk example2-trace

plot of chunk example2-trace

par(op)

The penalised t-walk reaches the second mode in every chain and switches between the modes regularly. The global acceptance rate falls from about 35% to 19%, and the penalised move is accepted about 4% of the time; the paper reports 33%, 16% and 3%. The paper does not give its seeds, the choice between equations (5) and (6) or the code of its implementation, so close but not exact agreement is what we expect.

The standard t-walk does better here than in the paper, where it visits the second mode only three times in 5 million iterations (Figure 2, which compares it with the gradient-based penalty). Some of our standard chains reach the second mode, and some of them then switch often. The reason is the mechanism of the t-walk itself: the Traverse move sends one point past the other along the direction \(x - x'\), so when the two points sit in different modes it can carry a point across the gap. What the standard t-walk cannot easily do is the first crossing, when both points are in the same mode and \(|x - x'|\) is small compared with the distance between the modes. That is the situation the penalised move is designed for, since it proposes distances several times larger than \(|x - x'|\) with a heavy tail.

Are the mode weights right?

Switching modes is not enough: the chain must also spend the right fraction of time in each. This is hard to check on a single chain, because the switches are rare and the time between them varies a lot, and because chains started in one mode are biased towards it for a long time. The clean check removes the second problem: start each chain from exact draws of the target, so that it is stationary from the first iteration and the average time in each mode is an unbiased estimate of its weight, whatever the length of the chain.

We use a version of the target with unequal weights, 0.3 and 0.7, and 64 chains of a million iterations.

log_unequal <- mixture(0.3)
draw_unequal <- function(n) {
  second <- runif(n) > 0.3
  z <- matrix(rnorm(2 * n), n)
  x <- z %*% chol(matrix(c(1, 0.1, 0.1, 1), 2))
  y <- sweep(z %*% chol(matrix(c(16, 16, 16, 25), 2)), 2, c(20, -20), "+")
  x[second, ] <- y[second, ]
  x
}

run_weights <- function(penalty_prob) {
  set.seed(64)
  fit <- twalk(log_unequal, n_iter = 1e6, x0 = draw_unequal(64),
               xp0 = draw_unequal(64), n_chains = 64,
               n_cores = min(8, parallel::detectCores()), thin = 10,
               show_progress = FALSE,
               control = twalk_control(penalty_prob = penalty_prob,
                                       store_companion = FALSE))
  vapply(fit$individual_chains, function(chain) {
    mean(chain$samples[, 1] > 10)
  }, numeric(1))
}
fraction <- sapply(c(standard = 0, penalised = 0.1), run_weights)
rbind(exact = 0.7, mean = colMeans(fraction),
      std_error = apply(fraction, 2, sd) / sqrt(64))
#>            standard  penalised
#> exact     0.7000000 0.70000000
#> mean      0.7203787 0.70860937
#> std_error 0.0352032 0.02316482
hist(fraction[, "penalised"], breaks = 20, col = "grey75", border = "white",
     main = "Penalised t-walk: time in the second mode, 64 chains",
     xlab = "fraction")
abline(v = 0.7, col = "firebrick", lwd = 2)
plot of chunk weights-hist

plot of chunk weights-hist

Both samplers estimate the weight without bias, as they should: each one leaves the target invariant, and started from the target each one stays there. This is the check that the penalised move is correct. The difference between them is the precision: the penalised chains vary less from one to another, so the standard error of their average is smaller.

In practice chains do not start from the target. Started in one mode, they are biased towards it until they have switched modes many times; for the standard t-walk, in Example 2, some chains never switched at all. On a multimodal target, run several chains from dispersed starting points and compare them before trusting the estimated weights.

4. Example 3: nine modes in three dimensions

Example 3 is a mixture of nine spherical Gaussians in three dimensions: eight centred at the vertices of the cube \(\{-10, 10\}^3\) and one at \((30, 30, 30)\) with variance 10. The paper says only that the variances of the first eight “range from 0.25 to 10”, so we space them evenly in that range. All components have the same weight.

centres <- rbind(as.matrix(expand.grid(c(10, -10), c(10, -10), c(10, -10))),
                 c(30, 30, 30))
variances <- c(seq(0.25, 10, length.out = 8), 10)
log_example3 <- function(x) {
  a <- -1.5 * log(2 * pi * variances) -
    0.5 * colSums((t(centres) - x)^2) / variances
  m <- max(a)
  m + log(sum(exp(a - m)))
}
nearest_mode <- function(samples) {
  apply(samples, 1, function(x) which.min(colSums((t(centres) - x)^2)))
}

run_example3 <- function(penalty_prob) {
  set.seed(3)
  twalk(log_example3, n_iter = 1e6, x0 = c(10, 10, 10), xp0 = c(10.5, 10.5, 10.5),
        show_progress = FALSE,
        control = twalk_control(penalty_prob = penalty_prob,
                                store_companion = FALSE))
}
example3 <- lapply(c(standard = 0, penalised = 0.1), run_example3)

occupancy <- sapply(example3, function(fit) {
  modes <- nearest_mode(fit$samples[seq(1, 1e6, by = 10), ])
  tabulate(modes, 9) / length(modes)
})
rownames(occupancy) <- paste("mode", 1:9)
round(rbind(occupancy, "acceptance" = sapply(example3, `[[`, "acceptance_rate")), 3)
#>            standard penalised
#> mode 1        1.000     0.145
#> mode 2        0.000     0.139
#> mode 3        0.000     0.102
#> mode 4        0.000     0.136
#> mode 5        0.000     0.115
#> mode 6        0.000     0.118
#> mode 7        0.000     0.103
#> mode 8        0.000     0.084
#> mode 9        0.000     0.058
#> acceptance    0.326     0.046

The standard t-walk stays in the mode where it starts. The penalised t-walk visits all nine within the first million iterations, as in the paper, with a global acceptance of about 5% (the paper reports 4%). Each mode has weight 1/9 = 0.111; one million iterations are not enough to estimate these weights precisely, which matches the paper’s remark that convergence is slow but the method at least exposes the multimodality.

5. Example 4: a mixture of bananas in ten dimensions

Example 4 is a mixture of three “banana-shaped” distributions in ten dimensions, \(\pi(x) \propto \sum_{i=1}^{3} N(\phi_{b_i}(x) \mid \mu_i, \Sigma)\), with \(\mu_i\) equal to \(-3\), \(0\) and \(3\) in every coordinate, \(b = (-0.03, 0, 0.03)\) and \(\Sigma = \mathrm{diag}(100, 1, \ldots, 1)\). The paper prints the transformation as \(\phi_b(x) = (x_1 + b x_1^2 - 100b, x_2, \ldots, x_d)\); we use the usual banana transformation of Haario et al., \(\phi_b(x) = (x_1, x_2 + b x_1^2 - 100b, x_3, \ldots, x_d)\), which bends the second coordinate and has unit Jacobian. With it the acceptance rates match those of the paper closely.

bend <- c(-0.03, 0, 0.03)
centre <- c(-3, 0, 3)
log_example4 <- function(x) {
  a <- vapply(1:3, function(i) {
    y <- x
    y[2] <- x[2] + bend[i] * x[1]^2 - 100 * bend[i]
    -0.5 * ((y[1] - centre[i])^2 / 100 + sum((y[-1] - centre[i])^2))
  }, numeric(1))
  m <- max(a)
  m + log(sum(exp(a - m)))
}

run_example4 <- function(penalty_prob) {
  set.seed(4)
  twalk(log_example4, n_iter = 1e6, x0 = rep(0, 10), xp0 = rep(0.5, 10),
        show_progress = FALSE,
        control = twalk_control(penalty_prob = penalty_prob,
                                store_companion = FALSE))
}
example4 <- lapply(c(standard = 0, penalised = 0.1), run_example4)

iat <- function(fit) {
  lp <- fit$log_posterior[-(1:1e5)]
  length(lp) / coda::effectiveSize(lp)
}
penalty_acceptance <- example4$penalised$kernel_statistics$acceptance_rate[5]
rbind(
  "acceptance, paper (%)" = c(13, 10),
  "acceptance, Rtwalk (%)" = round(100 * sapply(example4, `[[`, "acceptance_rate"), 1),
  "IAT of log posterior, paper" = c(630, 578),
  "IAT of log posterior, Rtwalk" = round(sapply(example4, iat))
)
#>                              standard penalised
#> acceptance, paper (%)            13.0      10.0
#> acceptance, Rtwalk (%)           13.7      11.1
#> IAT of log posterior, paper     630.0     578.0
#> IAT of log posterior, Rtwalk    354.0     328.0
c("penalised move acceptance (%), paper" = 0.3,
  "penalised move acceptance (%), Rtwalk" = round(100 * penalty_acceptance, 3))
#>  penalised move acceptance (%), paper penalised move acceptance (%), Rtwalk 
#>                                 0.300                                 0.025

The modes overlap here, so the standard t-walk already explores the target and the penalised move is almost never accepted. The paper concludes that the benefit in this example is minimal but the move does not interfere. We find the same acceptance rates, and the IATs with and without the move are similar, as in the paper; the penalised move is accepted even less often than there. Our IATs are about half of the paper’s, which does not say which quantity its IAT refers to (we report that of the log posterior) or how long its chains were.

6. What is not reproduced

7. Using the move in practice

fit <- twalk(log_post, n_iter = 1e6, x0 = x0, xp0 = xp0, n_chains = 4,
             control = twalk_control(penalty_prob = 0.1))
fit$kernel_statistics
sessionInfo()
#> R version 4.6.2 (2026-10-29 ucrt)
#> Platform: x86_64-w64-mingw32/x64
#> Running under: Windows 11 x64 (build 26300)
#> 
#> Matrix products: default
#>   LAPACK version 3.12.1
#> 
#> locale:
#> [1] LC_COLLATE=Portuguese_Brazil.utf8  LC_CTYPE=Portuguese_Brazil.utf8   
#> [3] LC_MONETARY=Portuguese_Brazil.utf8 LC_NUMERIC=C                      
#> [5] LC_TIME=Portuguese_Brazil.utf8    
#> 
#> time zone: America/Sao_Paulo
#> tzcode source: internal
#> 
#> attached base packages:
#> [1] stats     graphics  grDevices utils     datasets  methods   base     
#> 
#> other attached packages:
#> [1] Rtwalk_2.3.0   testthat_3.3.2
#> 
#> loaded via a namespace (and not attached):
#>  [1] digest_0.6.39    desc_1.4.3       R6_2.6.1         codetools_0.2-20
#>  [5] xfun_0.62        lattice_0.23-1   magrittr_2.0.5   coda_0.19-4.1   
#>  [9] knitr_1.52       parallel_4.6.2   lifecycle_1.0.5  cli_3.6.6       
#> [13] grid_4.6.2       pkgload_1.5.3    compiler_4.6.2   rprojroot_2.1.1 
#> [17] tools_4.6.2      pkgbuild_1.4.8   brio_1.1.5       evaluate_1.0.5  
#> [21] Rcpp_1.1.2       otel_0.3.0       rlang_1.3.0