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.

  • $\begingroup$ 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. $\endgroup$ – ziggystar Jul 31 '15 at 15:03
  • 2
    $\begingroup$ 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) $\endgroup$ – 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.

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
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.