TAOCP 7.1.1 Exercise 111

Let $f:\{0,1\}^n\to\{0,1\}$ be monotone and self-dual, and define the product measure A(f)=\sum_{x} f(x)\,w(x), \qquad w(x)=\prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i}, with $1 \ge p_1 \ge \cdots \ge p_n \...

taocpmathematicsalgorithmsvolume-4math-project

Section 7.1.1: Boolean Basics

Exercise 111. [M36] [M36] A Boolean function is called a coterie that corresponds to a monotone self-dual function with maximum availability, among all monotone self-dual functions with $n$ variables and with working probabilities $(p_1, p_2, \ldots, p_n)$. (See exercises 14 and 66.)

a) Prove that if $1 \ge p_1 \ge p_2 \ge \cdots \ge p_n \ge \frac{1}{2}$, then every self-dual function with maximum availability is a regular function. Describe such a function.

b) Furthermore, it suffices to test the optimality of a regular self-dual function $f$ at points $y$ of the binary majorization lattice for which $f(y) = 1$ but $f(x) = 0$ for all $x$ covered by $y$.

c) What coterie is optimum when some probabilities are $< \frac{1}{2}$?

Verified: no
Solve time: 6m07s

Let $f:{0,1}^n\to{0,1}$ be monotone and self-dual, and define the product measure

$$ A(f)=\sum_{x} f(x),w(x), \qquad w(x)=\prod_{i=1}^n p_i^{x_i}(1-p_i)^{1-x_i}, $$

with $1 \ge p_1 \ge \cdots \ge p_n \ge \tfrac12$.

Self-duality means $f(x)+f(\bar x)=1$, so exactly one element of each complementary pair contributes to $A(f)$. Hence

$$ A(f)=\sum_{{x,\bar x}} f(x),w(x) + (1-f(x)),w(\bar x), $$

and maximizing $A(f)$ is equivalent to choosing, from each pair ${x,\bar x}$, the element with larger effective contribution, subject to monotonicity.

The key obstruction is that these choices cannot be made independently because $f$ must be an upper set.

(a) Optimal functions are regular

Step 1. A coordinate exchange principle

Fix $i<j$. Since $p_i \ge p_j$,

$$ \frac{p_i}{1-p_i} \ge \frac{p_j}{1-p_j}. $$

Hence, whenever a configuration $x$ has $x_i=0, x_j=1$, swapping these bits increases its weight:

$$ w(x^{(i\leftarrow 1, j\leftarrow 0)}) ;\ge; w(x). $$

This is the only structural inequality needed.

Step 2. Compression that preserves feasibility

Define the standard compression $C_{ij}$: for each $x$ with $x_i=0, x_j=1$, replace $x$ by $x' = x^{(i\leftarrow 1, j\leftarrow 0)}$ whenever $x'\notin F$, otherwise leave it unchanged.

Classical facts:

  1. If $F$ is monotone, then $C_{ij}(F)$ is monotone.
  2. If $F$ is self-dual, then applying the same compression simultaneously to complements preserves self-duality:

$$ x \mapsto x' \quad \text{implies} \quad \bar x \mapsto \overline{x'}. $$

Hence complement pairing is preserved. 3. The measure does not decrease under compression because each replacement moves weight from a lower-probability coordinate to a higher one.

Therefore we may transform any optimal $F$ into a fully compressed optimal family, satisfying

$$ i<j,; x_i=0,x_j=1 \implies x \notin F \text{ is impossible unless forced by monotonicity}. $$

So in an optimal solution we may assume all such compressions have been applied.

Step 3. Structure of fully compressed monotone sets

A monotone set closed under all compressions $C_{ij}$ has the following property:

If $x\in F$ and $y$ is obtained from $x$ by moving 1s from later coordinates to earlier coordinates, then $y\in F$.

Thus membership depends only on the sorted vector of coordinates. Equivalently, all vectors with the same nonincreasing rearrangement behave identically.

So $F$ is determined by a threshold in the dominance (majorization) order restricted to sorted bitstrings, i.e., by a threshold on the vector

$$ (x_1,\dots,x_n) \quad \text{after sorting coordinates by importance}. $$

This is exactly what TAOCP calls a regular function: a monotone self-dual function invariant under all such compressions, hence determined only by the “shape” (rank vector) of $x$, not by its specific coordinate positions.

Thus every optimal function is regular.

Step 4. Description of the optimal regular function

Order points by the likelihood ratio

$$ L(x)=\prod_{i=1}^n \left(\frac{p_i}{1-p_i}\right)^{x_i}. $$

Since $p_1 \ge \cdots \ge p_n$, this ordering is consistent with compressions: moving a 1 to a smaller index increases $L(x)$.

Among all monotone self-dual sets, an optimal set must select, from each pair ${x,\bar x}$, the element with larger $L$-value, while respecting upward closure. This forces a single threshold cut:

$$ f(x)=1 \iff L(x)\ge T, $$

with $T$ chosen so that self-duality implies

$$ T = \prod_{i=1}^n \left(\frac{p_i}{1-p_i}\right)^{1/2}. $$

Thus the optimal coterie is a weighted threshold system (a halfspace in log-odds coordinates), and this structure is regular.

(b) Minimal true points suffice

Let $f$ be regular and monotone, and let $M$ be the set of minimal true points in the dominance order:

$$ M={y : f(y)=1,\ \forall x<y,\ f(x)=0}. $$

Because $f$ is monotone,

$$ f(x)=1 \iff \exists y\in M \text{ such that } y\le x. $$

Thus $f$ is completely determined by $M$.

Now consider optimality. Any modification of $f$ that preserves monotonicity must change its value on an upward-closed region, and such a region is determined by which minimal elements are included.

Hence it suffices to test optimality only at points $y\in M$, and only those $y$ for which all covered points are zero. Any improvement must originate at such a boundary point, since interior points are forced by monotonicity.

(c) Case $p_i<\tfrac12$

Let

$$ I={i : p_i<\tfrac12}. $$

Flip coordinates in $I$:

$$ x_i' = \begin{cases} x_i, & i\notin I,\ 1-x_i, & i\in I. \end{cases} $$

Then $p_i' = 1-p_i \ge \tfrac12$, and

$$ w(x)=w'(x'). $$

This transformation preserves:

  • product structure,
  • monotonicity (after relabeling),
  • self-duality (complementation commutes with flips).

Therefore the problem reduces exactly to the case $p_i\ge \tfrac12$, solved above.

The optimal coterie in the original variables is obtained by:

  1. flipping all variables with $p_i<\tfrac12$,
  2. taking the weighted-threshold (regular) self-dual function in the transformed space,
  3. mapping back.

Equivalently, variables with $p_i<\tfrac12$ appear negated in the optimal threshold function.

Final conclusion

  • Compression arguments (not majorization) force any optimal solution to be fully regular.
  • Regular self-dual monotone functions are exactly weighted threshold (halfspace) coteries in log-odds coordinates.
  • Minimal true points determine the function, so optimality can be tested only at boundary generators.
  • Variables with $p_i<1/2$ are handled by complementation.