I first <a href="https://cstheory.stackexchange.com/questions/2773/ensemble-of-tree-decompositions-for-all-pairs-problem">asked this</a> on cstheory.SE but got no reply.

Let $P(X_i=x)$ represent probability that randomly chosen <a href="http://en.wikipedia.org/wiki/Graph_coloring">proper</a> $q$-coloring of an $L\times L$ <a href="http://en.wikipedia.org/wiki/Lattice_graph#Square_grid_graph">square grid</a> contains color $x$ at position $i$. How do you efficiently compute $P(X_{i}=X_{j})$ for every pair $(i,j)$?

Fastest known <a href="http://arxiv.org/abs/1003.4847">method</a> for counting $q$-proper colorings on grids uses tree decomposition. To extend it to this problem, one needs a set of tree decompositions so that every pair of vertices is contained in some bag. Is anything known about this problem? 

Motivation: this is essentially two-point correlation function of Potts model, but also correlation function of self-avoiding walks and few other "all-pairs" problems face the same issue