# 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.

• You have to marginalize over $x_{i+2},\ldots,x_n$, and you can drop the factors involving $x_1,\ldots,x_{i-1}$ because of conditional independence. – ziggystar Jul 31 '15 at 15:03
• I understand that. However, when I marginalize over $x_{i+2},\cdots$, I can't seem to get rid of an expression that grows exponentially with the size of $n-i$. I guess what I was really trying to ask is if there is a form of $P(x_i|x_{i-1})$ that does not involve later terms. (I.e. $P(x_i|X_{i-1})=\psi(x_{i-1},x_i)\phi(x_i)$. Which would get what I need, but, unfortunately, is not a valid distribution) – maksay Jul 31 '15 at 15:14

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.