Big data research has become a globally hot topic in recent years. One of the core problems in big data learning is how to extract effective information from the huge data. In this paper, we propose a Markov resampling algorithm to draw useful samples for handling coefficient-based regularized regression (CBRR) problem. The proposed Markov resampling algorithm is a selective sampling method, which can automatically select uniformly ergodic Markov chain (u.e.M.c.) samples according to transition probabilities. Based on u.e.M.c. samples, we analyze the theoretical performance of CBRR algorithm and generalize the existing results on independent and identically distributed observations. To be specific, when the kernel is infinitely differentiable, the learning rate depending on the sample size m can be arbitrarily close to O(m) under a mild regularity condition on the regression function. The good generalization ability of the proposed method is validated by experiments on simulated and real data sets.