We explore applications of Markov chain Monte Carlo methods for weight estimation over inputs to the Weighted Majority (WM) and Winnow algorithms. This is useful when there are exponentially many such inputs and no apparent means to efficiently compute their weighted sum. The applications we examine are pruning classifier ensembles using WM and learning general DNF formulas using Winnow. These uses require exponentially many inputs, so we define Markov chains over the inputs to approximate the weighted sums. We state performance guarantees for our algorithms and present preliminary empirical results.