We investigate approximation algorithms for the problem of prioritized broadcast transmissions over independent erasure channels first described in Tran et al., 2009. In this work, the authors showed that under some settings, the achievable throughput regions for prioritized broadcast transmissions can be computed by a polynomial-time algorithm. In this paper, we study a class of approximate algorithms based on the Markov Chain Mote Carlo (MCMC) method, for obtaining the maximum sum of prioritized receiver's throughputs. Theoretical analysis and simulation results show the correctness and the convergence speed of the proposed algorithms.