Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConvergence of the Wang-Landau algorithm
238
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyze the convergence properties of the Wang-Landau algorithm. This sampling method belongs to the general class of adaptive importance sampling strategies which use the free energy along a chosen reaction coordinate as a bias. Such algorithms are very helpful to enhance the sampling properties of Markov Chain Monte Carlo algorithms, when the dynamics is metastable. We prove the convergence of the Wang-Landau algorithm and an associated central limit theorem.
rate research
Read More
We propose a strategy to achieve the fastest convergence in the Wang-Landau algorithm with varying modification factors. With this strategy, the convergence of a simulation is at least as good as the conventional Monte Carlo algorithm, i.e. the statistical error vanishes as $1/sqrt{t}$, where $t$ is a normalized time of the simulation. However, we also prove that the error cannot vanish faster than $1/t$. Our findings are consistent with the $1/t$ Wang-Landau algorithm discovered recently, and we argue that one needs external information in the simulation to beat the conventional Monte Carlo algorithm.
This review paper provides an introduction of Markov chains and their convergence rates which is an important and interesting mathematical topic which also has important applications for very widely used Markov chain Monte Carlo (MCMC) algorithm. We first discuss eigenvalue analysis for Markov chains on finite state spaces. Then, using the coupling construction, we prove two quantitative bounds based on minorization condition and drift conditions, and provide descriptive and intuitive examples to showcase how these theorems can be implemented in practice. This paper is meant to provide a general overview of the subject and spark interest in new Markov chain research areas.
We establish a quantitative version of the Tracy--Widom law for the largest eigenvalue of high dimensional sample covariance matrices. To be precise, we show that the fluctuations of the largest eigenvalue of a sample covariance matrix $X^*X$ converge to its Tracy--Widom limit at a rate nearly $N^{-1/3}$, where $X$ is an $M times N$ random matrix whose entries are independent real or complex random variables, assuming that both $M$ and $N$ tend to infinity at a constant rate. This result improves the previous estimate $N^{-2/9}$ obtained by Wang [73]. Our proof relies on a Green function comparison method [27] using iterative cumulant expansions, the local laws for the Green function and asymptotic properties of the correlation kernel of the white Wishart ensemble.
We study the rate of convergence of the Mallows distance between the empirical distribution of a sample and the underlying population. The surprising feature of our results is that the convergence rate is slower in the discrete case than in the absolutely continuous setting. We show how the hazard function plays a significant role in these calculations. As an application, we recall that the quantity studied provides an upper bound on the distance between the bootstrap distribution of a sample mean and its true sampling distribution. Moreover, the convenient properties of the Mallows metric yield a straightforward lower bound, and therefore a relatively precise description of the asymptotic performance of the bootstrap in this problem.
We prove the asymptotic independence of the empirical process $alpha_n = sqrt{n}( F_n - F)$ and the rescaled empirical distribution function $beta_n = n (F_n(tau+frac{cdot}{n})-F_n(tau))$, where $F$ is an arbitrary cdf, differentiable at some point $tau$, and $F_n$ the corresponding empricial cdf. This seems rather counterintuitive, since, for every $n in N$, there is a deterministic correspondence between $alpha_n$ and $beta_n$. Precisely, we show that the pair $(alpha_n,beta_n)$ converges in law to a limit having independent components, namely a time-transformed Brownian bridge and a two-sided Poisson process. Since these processes have jumps, in particular if $F$ itself has jumps, the Skorokhod product space $D(R) times D(R)$ is the adequate choice for modeling this convergence in. We develop a short convergence theory for $D(R) times D(R)$ by establishing the classical principle, devised by Yu. V. Prokhorov, that finite-dimensional convergence and tightness imply weak convergence. Several tightness criteria are given. Finally, the convergence of the pair $(alpha_n,beta_n)$ implies convergence of each of its components, thus, in passing, we provide a thorough proof of these known convergence results in a very general setting. In fact, the condition on $F$ to be differentiable in at least one point is only required for $beta_n$ to converge and can be further weakened.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
