The maximum a-posteriori (MAP) perturbation framework is a method for sampling from Gibbs distributions by leveraging fast MAP solvers. While this works on paper, the computational cost of generating so many high-dimensional random variables for the perturbations can be prohibitive. More efficient algorithms use sequential sampling strategies based on the expected value of low dimensional MAP perturbations. This work develops new measure concentration inequalities that bound the number of samples needed to estimate such expected values.