###### tags: `one-offs` `expository` `monte carlo`

# Vertical and Horizontal Structures in Stochastic Computations

**Overview**: In this note, I describe some abstract properties of stochastic computational algorithms which I find to be useful.

## Vertical, Horizontal, and Examples

One occasionally hears mnemonics to the tune of "Lebesgue integration is vertical, Riemann integration is horizontal". I like this presentation, and I also find that it extends nicely to a bunch of algorithms for sampling and computing integrals. Some examples:

1. Rejection Sampling is vertical, Inverse Transform Sampling is horizontal

2. Integration by Importance Sampling is vertical, but Integration by MCMC is horizontal.

3. Sequential Monte Carlo is both horizontal (when particles move) and verticle (when particles are reweighted).

4. Metropolis-Hastings algorithms typically propose moves horizontally, but the { accept / reject } decision is conducted vertically.

5. MCMC methods like { Pseudo-Marginal MH, Exchange Algorithm, Delayed Acceptance, ... } are MH algorithms for which the vertical component is particularly involved.

6. Gibbs sampling is (usually) mostly horizontal.

7. Convergence in Integral Probability Metrics (e.g. transport distances, maximum mean discrepancy) is horizontal, whereas convergence in Density Ratio Divergences (e.g. total variation, relative entropy, $\chi^{2}$-divergence) is vertical.

8. Working with continuous-time processes often lets one think in a purely horizontal way. Working with discrete-time processes often means that vertical thinking is required in order to mitigate biases.

9. Many (even most?) algorithms which are asymptotically biased will incur that bias by focusing more on horizontal considerations (e.g. improved discretisation of dynamics) than on vertical considerations (e.g. leaving distributions exactly invariant).

Many other examples doubtless exist.