Classical Estimation of the Free Energy and Quantum Gibbs Sampling from the Markov Entropy Decomposition