# Bayesian Nets & Markov Blanket

As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem.

In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to find minimum number of variable that Xi independent from other variables. at least, how many variable we need?

i think, we use Markov Blanket for this problem. any solution for this problem?

Regards.

In a Bayesian network, a variable is independent from all the variables given its Markov blanket (except of course the variables in the Markov blanket).

However, the Markov blanket is not the minimal set that renders two variables independent.

Also note that a variable may be independent of some variables in the Markov blanket, given another set of variables (think about the case of a spouse in the network).

By the way, I think that this problem has been solved already (if you refer to the problem of identifying the minimal set that renders two variables independent).

Edit: Check this out: http://www.cs.iastate.edu/~jtian/r254_min_separator.pdf They show how to find a minimal d-separating set in a given Bayesian network.

• How is it not related? Unless you are not asking for a minimal separating set, I think I exactly answer your question. If not, I would suggest you rephrase your question. Commented Jun 10, 2014 at 21:11
• P and Q are numbers? If so, not every variable can have P and Q parents/children (since it's a DAG). Assuming that this condition holds for all nodes except for roots and leafs, then the size of the Markov blanket for a non-leaf/non-root variable is at most: P + Q + Q*(P-1) = P + PQ as you wrote. I say at most, as some children may share some common parents. Commented Jun 10, 2014 at 21:28