Why do we need Gibbs sampling (and MCMC)?

Question

I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$.

Maybe my alternative suggestion would sound somewhat naive (even stupid) but why can't we just draw a number in random from $[0,M]$ for some sufficiently large enough $M$. Then, we divide the range to buckets with appropriate sizes according to the distribution.

This will be a true sampling of $\pi$.

One could argue that my suggestion demands a PRNG, but Gibbs Sampling uses randomness too when deciding the next state from the neighbors of the current state.

So for a reasonable distribution, wouldn't my suggestion work way better? It's essentially $O(1)$ and accurate.

Answer 1

The approach you described sounds like the common algorithms for sampling. If by reasonable distribution, you mean a smallish finite discrete distribution, then see the following references for how to do that. You would be right that Gibbs sampling would be a worse choice, probably, when these methods apply.

https://stats.stackexchange.com/questions/26858/how-to-generate-numbers-based-on-an-arbitrary-discrete-distribution

https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/

For many problems it is computationally infeasible (or impossible in the case of infinite state spaces) to enumerate all possibilities, nor even choose a sufficiently large M. (The M you describe is actually the partition function, i.e., the sum of all the un-normalized probabilities of all events). For instance, imagine sampling from an Ising model, which has 2^N states, where N is the number of binary variables.

Answer 2

It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time.

Further, sampling from a Markov chain allows you to sample without having to construct the probability distribution explicitly or even the state space, explicitly. For example, how do you propose to randomly sample matchings in a graph by your method, even uniformly? You'd need to first construct the set of all matchings (of which there can be exponentially many), then select one. And note that constructing the set of matchings implies being able to count them, which is #P-hard, so very unlikely to be doable efficiently. With a Gibbs sampler, you just run a Markov chain for polynomially many steps and you have yourself a matching chosen uniformly at random.

Answer 3

It's because we're not sampling integers. If we were sampling integers, and the distribution were given explicitly, you are right, there would be simpler methods. But instead we often want to sample from a set of objects, where each object is some more complicated thing (it's not just an integer), and there's no clear way to do that.