3 ms·

Yeah, that wasn't exactly what was promised in the preface. In fact, unlike many other his posts, this one is worse than a commonplace math-heavy explanation. T

by krick 10y ago

Yeah, that wasn't exactly what was promised in the preface. In fact, unlike many other his posts, this one is worse than a commonplace math-heavy explanation. That way I wouldn't even understand what is the problem we are solving, as 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: I know for sure I can generate random uniform number y somehow, so this one is a solved problem, and mapping y to the distribution over a finite set D is simple: if y <= p(x1) return x1, if y <= p(x1) + p(x2) return x2, ..., return xn. The link to stackexchange in the comments is way more enlightening.

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 ago
  That'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.

by krick 10y ago

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 ago
That'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.