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?
 A: 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.
A: 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$.
