# Binary Bayesian Network complexity

Imagine a Bayesian Network with binary random variables, with the structure of a binary tree of arbitrary height:

I want to find the minimum number of probabilities that I must store at depth k to describe the entire tree up to that point (i.e. the joint distribution)

• Starting at depth 0 (the root node A), I only need to store 1 probability, i.e. $P(A = True) = P(a)$ because I get $P(\bar{a}) = 1 - P(a)$ for free.
• At depth 1, I need to store $P(ABC) = \sum_{ABC} P(A)P(B|A)P(C|A)$.
• I need to only store $P(a), P(b|a), P(b|\bar{a}), P(c|a), P(c|\bar{a})$ = 5 probabilities. This is because from $P(b|a)$ I get $P(\bar{b}|a) = 1 - P(b|a)$, and $P(\bar{c}|a)$ similarly.
• At depth 2, using similar logic, I store 1 + 4 + 8 = 13 probabilities
• And so on.

So at depth k, I store $\sum_{i=0}^{k} 2^{i+1}-1$ probabilities.

Is this correct?

I'm no expert in this field, but I think your reasoning is correct. (I found this pdf helpful in writing the answer.)

Your network is a directed acyclic graph (DAG), which means that the probabilities you need at a particular node are the conditional probability of that node (say, $X$), given every combination of its ancestors (say, $Y_i$, where $i = 1...n$). So, in the general case of a node with $n$ ancestors, you'd need to store $2^n$ probabilities for that particular node (since the "truth table" would have $2^n$ rows).

In your case, each node has only one ancestor. So, you need $2^1 = 2$ probabilities ($P(X|Y)$ and $P(X|\bar{Y})$) for every node that has an ancestor. So, for the overall tree, with $N$ nodes with ancestors and 1 node without an ancestor, you'd need $2*N$ probabilities for the former + 1 probability for the latter.

I think this works out to be the same as your formula (which, by the way, you can simplify to $2^{k+2} - 3$), since a complete binary tree at level $k$ (in your notation) has $2^{k+1} - 1$ total nodes and therefore $2^{k+1} - 2$ nodes with ancestors and 1 without.

From the law of total probability, the state of node $n_j$ given the state of the input node $n_i$ can be expressed as,

(1) $P(n_j) = P(n_j|n_i)P(n_i) + P(n_j|\bar n_i)P(\bar n_i), \forall j>0$,

Now if we can assume,

(2) $P({n_j=1}|n_i)P(n_i)+P({n_j=1}|\bar n_i)P(\bar n_i) = 1$,

that is, $n_j$ is entirely determined by the state of the input node $n_i$, then for the $N-1$ non-root nodes we will only need $N-1$ probabilities.

If we can't assume (2) above then we will need to store the behavior of each node for both input states. For the $N-1$ non-root nodes with binary input this will be $2(N-1)$ PDFs. The total number of PDFs including the root that has no binary input, would be,

(3) Total Quantity of PDFs = $2N-1$, where N = total number of nodes.

EDIT: If you want this total in terms of specific depths, then for depth k we have $2^{k+1}, k>0$.

• I use $k$ to be the depth (starting at 0), where there are $2^k$ non-root nodes. So you propose there are $2\times 2^k-1 = 2^{k+1}-1$ probabilities to be stored at depth k? – ilanman Dec 25 '16 at 21:15
• The -1 should be outside the summation. – fuzzyhedge Dec 25 '16 at 21:42