Efficient Monte Carlo Simulation of Absorbing Random Walks: Variance Reduction and Numerical Verification

Abstract

The one-dimensional absorbing random walk with two barriers is a fundamental model in probability theory and financial risk analysis. The closed-form solutions of absorption probability and expected arrival time can be obtained by difference equation and martingale method, but the naive Monte Carlo (MC) simulation has the problems of slow convergence and large variance. Therefore, in rare-event and high-precision estimation, the calculation cost is too high to be used. This paper proposes an efficient simulation framework, which uses AV-CV strategy, which combines antithetic variates (AV) and control variates (CV). AV method uses evenly distributed symmetry to construct negatively correlated road pairs. CV method uses Optional Stopping Theorem, and uses the terminal state of analytically knowing the expected value as control variate. We derive the variance limit of each estimator. In the case of AV method, when the initial capital is a=N/2 with a symmetric transition probability of p=0.5, the paired paths become completely negative correlation. For CV method, under the same symmetry condition, the correlation coefficient between ruin index and terminal state is ρ = 1, which reaches the limit of minimum variance. A large number of facts have proved that the logic of the theory is correct. Under the general conditions of a=50, N=100 and p=0.5, the estimation deviation is reduced by 10 orders of magnitude by using the method of combining AV-CV, and the standard deviation of the estimator is less than the machine precision (<). In the case of AV method, the ratio of stagger near the symmetry point of p=0.5 is approximately 3, and the coefficient of stagger deviation is approximately 6. The same peak will appear in CV method, but it can be seen that when P deviates from symmetry, the value will gradually decrease, and it has strong stability even if the parameters change. It can also be seen more clearly from the three-dimensional sensitivity surface that AV strongly depends on the symmetry of the problem, and CV can get relatively stable results in the whole parameter range.