# On the tractability of posterior distributions

I am trying to understand what makes estimating the posterior distribution such a hard problem.

So, imagine I need to estimate the posterior distribution over a set of parameters given the data y, so a quantity $P(\theta|y)$ and $\theta$ is generally high dimensional.

The prior over $\theta$ is a multivariate Gaussian i.e. $P(\theta) \sim N(\theta; 0, \Sigma)$

The likelihood i.e. $P(y|\theta)$ can be written down as product over Gaussian likelihoods.

Now, it seems to be that the posterior distribution will also be Gaussian. Is that correct?

Secondly, going through Bishop's book, it seems that the conditional posterior distributions and the marginal distributions will be Gaussian as well (assuming that the joint distribution over the parameters and data is Gaussian) and should have a closed form solution. If that is the case, why is this problem intractable?

If I need to find the parameters of this posterior distribution, can this not be set as an optimisation problem where I estimate the mean and covariance of the posterior Gaussian? I am basically having trouble visualising why this problem is complicated?

• Is the reference saying that the posterior distribution for the Normal-Normal problem is intractable or is it saying IN GENERAL the problem is intractable? In general the problem is intractable, but for certain special cases ("conjugate priors") the problem is easy, and the Normal-Normal is one of those special cases. Feb 14, 2014 at 18:47
• Thanks for the comment. Yes, it says it is intractable in general. OK, let me ask it in a different way. So, we have a likelihood with unknown mean but known variance and we know that the conjugate prior is a multivariate normal. So, of course the aim of the inference is to know the mean and the variance of the posterior distribution. So, I am given a bunch of data points. Can I estimate the posterior distribution (i.e. its mean and variance) without resorting to methods like MCMC, Variational Bayes etc. and the result will be exact?
– Luca
Feb 14, 2014 at 22:04
• There are two common issues when doing Bayesian analysis in (nontrivial) problems involving multiple parameters: (i) finding the joint posterior, and (ii) finding the marginal posteriors. With a nice (jointly) conjugate prior for all parameters, you might be able to write down the joint posterior just fine, but the marginals would still require integrations that may not be so easily accomplished. The nice thing about many of the computational techniques is you usually only need to be able to do something relatively simple in place of the integrations. Feb 14, 2014 at 22:28
• Thanks for the reply. In the case we discuss though, as the joint is Gaussian, are the marginals not Gaussian as well? i thought if I have the joint distribution with the mean vector and covariance matrix, I could just read off the corresponding mean entry and the diagonal entry in the covariance matrix to get my marginal.
– Luca
Feb 15, 2014 at 16:32
• Are you asking this in reference to expectation propagation? Feb 18, 2014 at 22:53

• Chamberlain Foncha, if you have the covariance matrix, you just calculate a matrix square root (using the Cholesky decomposition, or if $N$ is too big for that to yield stable results, the eigendecomposition) and then use a matrix-affine transformation of a product of standard normal random variates. This will work until $N$ is so big that the eigendecomposition computation outstrips one's computing resources.