Closed form of conditional probability for a specific joint

Question

I have a joint probability of a very specific form: $P(x_1,\cdots,x_n)=\phi(x_1)\psi(x_1,x_2)\phi(x_2)\cdots\psi(x_{n-1},x_n)\phi(x_n)=\prod_{i=1}^n \phi(x_i) \prod_{i=1}^{n-1} \psi(x_i,x_{i+1})$

I wonder if there is a closed form expression for $P(x_{i+1}|x_i)$, under Markov assumption that $P(x_1,\cdots,x_n)=P(x_1)P(x_2|x_1)\cdots P(x_n|x_{n-1}) = P(x_1)\prod_{i-1}^{n-1}P(x_{i+1}|x_i)$. I was unable to express it for now. Although the joint looks like something that should have been used by many people before. Is there a closed form expression? Any kinds of links are also very appreciated.

Thank you.

Answer 1

Your distribution is basically an undirected graphical model (Markov random field, Markov network, factor graph).

To compute the conditional probability $P(x_i \vert x_{i-1})$, you have to marginalize over the variables $x_{i+1},\ldots,x_n$. You can ignore factors over variables $x_1,\ldots,x_{i-1}$, because of conditional independence.

To efficiently evaluate your exponentially large sum you can use

• the distributive law, and
• dynamic programming,

because the dependency structure of your problem is a tree (it's even a chain).

Algorithms for efficient computation of marginals

Some related, and more or less equivalent, algorithms for computing all single variable marginals at once are:

• Pearl's Belief Propagation (for arbitrary trees)
• sum-product algorithm
• the forward-backward algorithm for HMMs.

If you are only interested in the marginal distribution of a single variable, you can also apply

• variable elimination.

Some reading

• Aji, Srinivas M., and Robert J. McEliece. "The generalized distributive law." Information Theory, IEEE Transactions on 46.2 (2000): 325-343.
• Kschischang, Frank R., Brendan J. Frey, and Hans-Andrea Loeliger. "Factor graphs and the sum-product algorithm." Information Theory, IEEE Transactions on 47.2 (2001): 498-519.
• Book: Koller, D. & Friedman, N. Probabilistic Graphical Models: Principles and Techniques MIT Press, 2009