Research On A New Monte-Carlo-Type Sampler And Approximation Algorithm

In general,Monte Carlo method is used to estimate the approximate result of a problem which is hard to get its exact result,and it will become more accurate with more repetitive experiments.Monte Carlo method is used in various fields because of its simplicity and handy implementation,the central point of which is to construct a(approximate)uniform sampler over the targeted sampling space.It means that each sample point is sampled with the same probability during each experiment.The property mentioned above guarantees the accuracy of the Monte Carlo method.This article aims at the construction of an approximate uniform sampler over a sampling space whose size is n!,as well as the applications and prospects of this type of uniform sampler.We use MCMC method to construct the required sampler,in other words,we construct a Markov Chain whose stationary distribution is exactly the uniform distribution over the targeted sampling space,sampling it with a certain criterion.We propose a new shuffling method satisfying such requirements in this paper to realize it.In addition,we can prove that the new shuffling method will reach its stationary distribution in polynomial-time with the usage of coupling technique.The(approximate)uniform sampler,therefore,constructed in this paper is efficient in theoretic.Moreover,we also use a concrete example illustrating the application of this new uniform sampler,and at the same time point out that there are many prospective applications in other scenarios.