This paper describes algorithms for probabilistically evaluating multi-frame data-association hypotheses formed in multiple-hypothesis, multiple-target tracking, using Markov chain Monte Carlo (MCMC) methods (also known as sequential Monte Carlo (SMC) methods). Each algorithm is designed to sequentially, randomly generate multi-frame data association hypotheses, and to converge to a stationary process with the a posteriori probabilities of the multi-frame hypotheses, as the stationary (target) probability distribution. The paper explores three sampling designs: the metropolis sampling, the metropolis sampling with Boltzman acceptance probability, and the metropolis-hasting sampling. Their performances are compared with each other and with the hypothesis evaluation obtained by a K-best hypothesis selection algorithm, using two simple examples.