3 ms·
> drawing x with probability p(x) given p(x) for every x in finite set X sounds pretty trivial thing to program w/o knowing anything about Markov chains and stu
by j2kun 10y ago
> drawing x with probability p(x) given p(x) for every x in finite set X sounds pretty trivial thing to program w/o knowing anything about Markov chains and stuff
Then you misunderstood the complexity of the problem. It's okay, I did too when I first learned about MCMC, and I proposed the same algorithm as you did (in fact, your proposed algorithm is right there in the fifth paragraph of the post. Did you read it before commenting here?). The problem is that if X is exponentially large, and many of the probabilities are exponentially small, your algorithm takes exponential time to draw even a single example.
- krick 10y agoThat's correct, that would be misunderstanding. No offense, I'm actually quite a fan of your blog, but this one explanation was easy to misunderstand, in my opinion. I didn't even quite understand, what we are trying to achieve here, and suddenly found myself reading about Perron-Frobenius theorem. Compare it to the explanations at stackexchange, especially this: > The way MCMC achieves this is to "wander around" on that distribution in such a way that the amount of time spent in each location is proportional to the height of the distribution. In fact, yes, I read the fifth paragraph, but didn't quite recognize what I proposed as a "solution" earlier before you pointed this out.