Hacker News Reader

It's a Markov chain because you use the previous sample to sample the next. A chain of random variables where each variable depends on the previous one (and only the previous one) is by definition a Markov chain.

The theory of Markov chains also provides a useful theorem, which is that (under suitable conditions) the distribution of each sample converges to a particular 'limit' distribution. In fact it converges to the so called 'stationary' distribution. It's called stationary because if you start the Markov Chain at a sample from the stationary distribution then all following samples of the chain will have the exact same distribution.

For the finite case, if you put the probabilities of transitioning from state i to state j in a matrix M then the stationary distribution is a vector p such that Mp = p (or pM = p depending on what convention is used).

The MCMC methods consist of trying to design a Markov chain which has a useful stationary distribution. This allows you to sample the stationary distribution by sampling the Markov chain.

I humbly submit my article as an alternative. I clearly explain why there is no alternative, and give a concrete description of the markov chain. Though after the initial description of what problem MCMC is solving, I do dip into the math.

https://jeremykun.com/2015/04/06/markov-chain-monte-carlo-wi...

Your article is interesting. But I see a problem in your exposition, in MCMC we don't know the probabilities of individual events. For example let p_n proportional to 1/n^3. We know that 1/n^3 converges but we don't know the sum. The key factor here is that we can compute the transition probabilities without computing the sum of the series. In the continuous variable setting we can compute the transition probabilities without computing difficult integrals. I hope you can incorporate this key factor to improve the quality of your article.

I'm sorry but I can't make any sense of what you've written.

Let X be the random variable that takes values in natural numbers n>1 with p(X=k)=A/k^3 with constant A such that sum p(X=k)=1, you can't apply MCMC with ypur explanation since you don't have an oracle for p(x=k). To apply MCMC you only need an oracle for the quotient of probabilies, here the transition probabilities are k^3/j^3 and you don't need to compute the unknown constant A.

I don't think this distinction is key. You're talking about a detail of the Metropolis-Hastings algorithm, while I'm defining a problem that Metropolis-Hastings is one of many algorithms to solve. Sure, Metropolis-Hastings might not need an oracle, but providing an oracle doesn't make the sampling problem any easier, and the way I wrote it makes it clearer why the sampling problem is hard. "Avoiding a difficult integral" is an engineering detail.

On one hand, mathematically speaking, the problem of sampling a finite state system when the probabilities of each state are known is a trivial one, as you know very well since you have shown that method in your posts (computing cumulative probabilities ...) On the other side, your blog is about computation and math, and in the realm of computation the complexity of algorithms is a key factor. Mixing time and burning time of markov chains are also computationally important.

The curse of dimensionality is a cause of Monte Carlo methods to be used instead of other numerical methods in high dimensional problems.

You should communicate to your audience that the advances in stochastic sampling and its application to science has revolutionize the field not because a breathrough in maths but because great key insights that allow us to explore multidimensional problems effectively with the help of computers.

Another important factor is that MCMC is used extensively in Bayesian statistics, but to explain that main application of MCMC in your blog it is necessary to introduce concepts like Bayer's theorem, likelihood, posterior density function, and prior probabilities.

There are some blogs in which all those concepts are illustrated and code in R or python is provided. Perhaps MCMC requires more than one post to be adequately explained.

To sum up, I am a follower of your posts and I appreciate the effort you take to show the main ingredients and the python code. My only desire is for you to continue improving the content of your blog for us to follow and enjoy.

Merry Christmas to you and your family from a follower in Spain.

>>Actually, I still have no idea why there is a Markov chain. What is the structure of the chain? Where does it come from and why can't we just sample the parameter without using a chain?

If the parameter can be sampled from the posterior directly, then no chain is usually needed, just sample it. However, most often you can not directly sample from the posterior. Note that this is not necessarily because "posterior is hard to analytically compute". Most times you know the analytical expression for the posterior distribution (up to the normalization constant) but this does not mean you can generate samples from it easily.

So, instead, you construct a Markov chain, from which you can sample easily, and which has the property that in the limit its distribution coincides with your posterior. Then you sample the chain for a long time an hope for the best.

Any chain for which you can show that its stationary distribution is the posterior works in principle. But some chains are better than others. There are also some generic ways to construct such chains, most famous are the Gibbs and the Metropolis-Hastings samplers.

Finally, do not sample blogs by "wikipedia researchers". Sample books like "Bayesian Data Analysis" by Gelman et al. They will not lie to you.

You can not sample the distribution directly when “it is impossible to solve for analytically”. There are a few methods to overcome this issue, in particular “MCMC methods allow us to estimate the shape of a posterior distribution in case we can’t compute it directly”.

You only need to be able to compute the relative values of the function you want to integrate (in this case a probability density) at the current point and the proposed destination. Where is this function coming from is not relevant to understand MCMC methods, they can be applied in many problems unrelated to Bayesian statistics.

Here is another (non-zero-math) introduction to the topic: https://arxiv.org/pdf/cond-mat/9612186.pdf https://www.coursera.org/learn/statistical-mechanics/lecture...

I think probably the single most intuitive way of implementing a Bayesian model for a programmer is ABC: https://en.wikipedia.org/wiki/Approximate_Bayesian_computati... because it is generative and inherently algorithmic. I wonder if there is a good tutorial way of starting with ABC and developing into MCMC and other more efficient methods? It's easy to transition from simple Monte Carlo methods to ABC rejection sampling, but I'm not sure how to link up ABC and MCMC (in part because I don't grok MCMC myself well enough to explain it).

If you're going to go for the "zero-math introduction", it seems only reasonable to expect some "glossing over [of] the actual explanation".

This is like describing a painting to a blind person. Describing "a dust-covered sunflower" as a "yellow flower" doesn't much help the blind person and certainly doesn't help the sighted.