Closed form of conditional probability for a specific joint 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.
 A: 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

