TAOCP 7.1.4 Exercise 116

Exercise 116. [M21] [M21] What is the (a) worst case (b) average case of a random quasi-profile?

Verified: no
Solve time: 4m27s

Solution

Let the quasi-profile of a BDD for a Boolean function $f(x_1,\dots,x_n)$ be the sequence $Q_k(f)$, where $Q_k(f)$ counts the number of distinct nodes (equivalently distinct subfunctions) at level $k$, corresponding to restrictions $f(x_1,\dots,x_k,;x_{k+1},\dots,x_n)$ as in the bead construction of Section 7.1.4. Each node at level $k$ represents a Boolean function of the remaining $n-k$ variables, and reduction identifies identical subfunctions.

For fixed $k$, the number of syntactically possible subfunctions on variables $x_{k+1},\dots,x_n$ equals $2^{2^{,n-k}}$, since a truth table of order $n-k$ has length $2^{n-k}$. The total number of nodes before reduction at level $k$ is at most $2^k$, since there are $2^k$ assignments to $(x_1,\dots,x_k)$.

Worst case

A worst-case Boolean function is one in which no two distinct assignments to $(x_1,\dots,x_k)$ yield identical subfunctions on $(x_{k+1},\dots,x_n)$ for any $k$. This can be achieved by a function whose restriction map is injective at every level, for example by ensuring all $2^{2^{n-k}}$ possible subfunctions are not exhausted before level $k$ and all $2^k$ prefixes produce distinct truth tables.

Under this condition no merging occurs in the reduced ordered BDD, so every node generated by branching remains distinct. Hence every level $k$ contains exactly one node per prefix of length $k$, giving

$$ Q_k^{\max}(f) = 2^k. $$

No larger value is possible because level $k$ contains at most one node per assignment of $(x_1,\dots,x_k)$, and there are exactly $2^k$ such assignments. Therefore $2^k$ is both attainable and maximal.

Thus the worst-case quasi-profile is

$$ Q_k^{\max} = 2^k. $$

Average case

Let $f$ be a uniformly random Boolean function on $n$ variables. Fix $k$ and consider the $2^k$ subfunctions induced by assignments to $(x_1,\dots,x_k)$. Each such subfunction is a random truth table of order $n-k$, hence a uniformly distributed element of a set of size $2^{2^{n-k}}$.

Two distinct prefixes collide only if they induce identical truth tables on $n-k$ variables. For any fixed pair of prefixes, the probability of collision equals

$$ 2^{-2^{n-k}}. $$

The expected number of colliding pairs at level $k$ is therefore

$$ \binom{2^k}{2} 2^{-2^{n-k}}. $$

Since $2^{2^{n-k}}$ dominates $2^{2k}$ for all $k \le n-1$, this expectation is exponentially small in $2^{n-k}$. Hence the expected number of distinct subfunctions satisfies

$$ \mathbb{E}[Q_k(f)] = 2^k - \mathbb{E}[\text{collisions at level }k] = 2^k - o(1). $$

The correction term becomes non-negligible only when $n-k$ is so small that $2^{n-k}$ is comparable to $k$, that is, within a constant distance of the bottom levels. For all levels bounded away from $n$, the collision term vanishes asymptotically.

Thus for a random Boolean function,

$$ \mathbb{E}[Q_k(f)] = 2^k \cdot (1 + o(1)) $$

uniformly for levels $k$ not extremely close to $n$.

Conclusion

The quasi-profile attains its maximal growth when no merging occurs, yielding $2^k$ nodes at level $k$. For a random Boolean function, distinct subfunctions dominate overwhelmingly because the space of possible truth tables of order $n-k$ is vastly larger than the number of available prefixes, so the expected quasi-profile coincides with the maximal profile up to a vanishing collision correction.

$$ \boxed{\text{Worst case: } Q_k = 2^k \quad\text{Average case: } \mathbb{E}[Q_k] = 2^k - \binom{2^k}{2}2^{-2^{n-k}} \approx 2^k} $$

This completes the proof. ∎