Proving Bayesian Network must be acyclic I am struggling to prove that Bayesian Network must be acyclic. Could anyone help me in proving this? I am trying to prove by constructing a cyclic graph and showing some contradiction of probability distribution. But it's getting nowhere
 A: You're not going to find any contradictions by creating a cyclic graph. It's not that Bayes nets (or as I've heard them called, conditional independence networks since they really don't have anything to do with Bayesianism besides conditional independence rules) "have to be acyclic". We assume them to be acyclic to get certain properties and simplify calculation of probabilities. In fact, if we relax the acyclic restriction as well the directed restriction we get a more general model called a Markov network.
A: A Bayesian Network can be viewed as a data structure that provides the skeleton for representing a joint distribution compactly in a factorized way. For any valid joint distribution two restrictions should be satisfied:  
1) All probabilities in the distribution should be non negative;
2) All the probabilities should sum to one. 
Normally a graph is determined by the ordering of the factorization and the conditional independencies assumed in the independency structure of the distribution. Since we are dealing with an invalid Bayes Network we don't need to follow the procedure, and we can design many counterexamples to verify that the sum of the distribution would be not 1. For instance, assume that we have such a graph over three binary variables:

And we can obtain the joint distribution easily: in all $2^3$ possibilities at least two are 1: 
$P(a_0, b_0, c_0) = P(a_0|c_0)P(b_0|a_0)P(c_0|b_0)=1$
$P(a_1, b_1, c_1) = P(a_1|c_1)P(b_1|a_1)P(c_1|b_1)=1$
Then $\sum_{A,B,C} P(A, B, C)\ge2>1$, so the distribution is invalid(indicating the cyclic Bayes Network is invalid). 
If we remove any one of the directions in the graph and adjust the parameters in the CPTs accordingly we can find that the joint distribution will be valid.   
A: I am afraid that Nick's answer might be incomplete.
BNs must be acyclic in order to guarantee that their underlying probability distribution is normalized to 1. It is quite easy to prove that this is the case, by starting at a vertex with no parents (which must exist, otherwise the graph would contain a cycle) and marginalizing it out, then repeating the procedure until all vertices have been accounted for.
This is no longer guaranteed to be the case if the graph has a cycle and a counterexample is also readily found. Consider the cyclic graph $A \to B \to C$ where the value of each parent fully determines the value of its child, e.g., $p(B=x|A=x)=1$. If we now sum the joint distribution over all possible states $(A,B,C)$, then all states of type $(x,x,x)$ have joint probability 1, and all other states have probability 0. Clearly, the sum over multiple "ones" is larger than one.
Of course this argument only holds for stationary distributions, which I assume was the premise of the OP's question.
A: Bayesian Network is defined to be a DAG (Directed Acyclic Graph), you cannot prove a definition. Take a look at this explanation.
A: Cycles are redundant, that's all. And it is pretty easy to show if you think about the transitivity.

*

*A -> B -> C -> A implies A -> B and B -> A

So the directionality is immediately lost (for every pair in the loop).

*

*A -> B -> C -> A is also deterministic, the multiplier is one.

For example:
Say B = (1/3)A + e1 and C = (1/2)B + e2; then A = A implies that A = 6C + e3, where 0 = e3 + 6e2 + 3*e1.
So cycles like this may be solved deterministically by simultaneous equations, and all nodes are basically transformations of the same distribution. You might as well collapse the cycle to one node only, because there is no more information in the three of them than there is in any one.
For a formal proof like this it would be nice to replace the constant multipliers with functions, then using something like this simplest of cycles as the basis for an induction argument, but you get the idea.
