MCMC using Hamiltonian dynamics: a Lua implementation of the No-U-Turn Sampler

The HMC (Hamiltonian Monte Carlo) was proposed by Duane et al. to simulate quantum chromodymanics; they combined Metropolis algorithm with a deterministic molecular dynamics following a Hamiltonian trajectory. Thus, HMC is a MCMC (Markov Chain Monte Carlo) according to Metropolis algorithm in which states of an ergodic Markov Chain are proposed by computing its trajectory following a Hamiltonian dynamics, which is reversible ensuring convergence. However, the Hamiltonian dynamics must be discretized to allow its computation and this is done by using the leapfrog method that requires the input L and ε which are, respectively, the number of steps utilized and the size of each step. These parameters can destroy ergodicity or increase sharply computation time if they are set badly. Therefore, M. D. Hoffman and A. Gelman proposed NUTS (No-U-Turn Sampler), which is a user-friendly HMC algorithm as it automatically tunes both L and ε. In particular, NUTS generates a reversible process by randomly taking forward and backward leapfrog steps building a balanced binary tree whose nodes are Markov chain's states; this process is stopped when a subtrajectory of any subtree of the binary tree starts making a U-turn, i.e. generating states already visited. At this point NUTS halts the simulation and starts sampling states that preserve convergence toward the desired distribution. Thus, NUTS improves simulation techniques that are essential in Bayesian statistics. Indeed, the inference on the posterior density function is rarely tractable and so it needs to use approximating statistical inference method based on MCMC. Moreover, the efficiency of NUTS can be improved by using proper software to run it. For example, Lua is a scripting language that allows implementing easily complex algorithms and LuaJIT is its Just-In-Time (JIT) compiler which combines the easy use of scripting languages with the high performance of compiled languages. Therefore, it constitutes the base of SciLua project by Stefano Peluchetti which offers a complete framework for numerical computing based on LuaJIT, which is essential for running NUTS and its Bayesian implementation. Thus, the thesis is structured in three chapters. The first chapter deals with HMC by demonstrating the properties of Hamiltonian dynamics, which allows providing a detailed derivation of HMC. Moreover, it is showed a comparison between Metropolis algorithm and HMC highlighting their advantages and drawbacks. The second chapter deals with NUTS by showing its detailed derivation. Furthermore, it is provided a comparison between NUTS and HMC stressing the practical superiority of the former. The third chapter provides an implementation of NUTS in Bayesian estimation of GARCH model, which is extremely used in both financial and actuarial modelling, by using Scilua. In particular, the chapter firstly shows in details how NUTS is written in Lua, subsequently it deals with GARCH model and its Bayesian inference. Finally, the chapter shows the construction of the algorithm in Lua to perform this Bayesian inference and comments the simulation results obtained.