Adaptive Monte Carlo methods for solving eigenvalue problems.

摘要

Simulation has become a very important computational method for solving many different kinds of problems in science and engineering. One of the objectives of a successful application is an efficient simulation scheme. Importance Sampling is such an efficient simulation method. Under certain conditions, it requires only one simulation outcome to exactly compute the expectation of random a quantity. This optimal importance sampling technique involves the use of an alternative sampling distribution, which results in a zero-variance estimator. The practical problem with this method is the lack of knowledge about the zero-variance measure. A newer class of simulation techniques has been proposed which mitigates this drawback by learning about the structure of the zero-variance measure at each iterate and utilizing this knowledge to make increasingly accurate guesses of the zero-variance measure for the next iterate. This learning feature justifies the name learning algorithm or adaptive algorithm.; In this work we establish a framework which provides certain sufficient conditions and results, under which an adaptive algorithm is guaranteed to converge exponentially fast to the optimal or the zero-variance solution. These results are based upon the properties of general state space and discrete time Markov chains and utilize Lyapunov function-like ideas in this context.; As an application of this result, we propose an adaptive Monte Carlo algorithm for computing the Perron-Frobenius eigenvalue and eigenvector for non-negative and irreducible matrices. Although the eigenvalue problem is simple to state, it is by no means easy to solve. Moreover, it has many applications and routinely arises in many different branches of the basic sciences, mathematics, and economics. We prove the exponential convergence of the proposed algorithm using the framework that we have established. We also provide numerical illustrations of this algorithm and compare the results with other numerical methods for solving the eigenvalue problem.