33 Boolean Analysis — Restriction Monotonicity

33.1 Overview

This module shows that decision-tree depth can only decrease when a function is further restricted. It builds the operation of restricting a decision tree by a partial assignment, proves the resulting tree is shallower and computes the restricted function, and derives the key Bernoulli monotonicity \(\Pr _{p\cdot q}[\mathrm{dtDepth} \gt t] \le \Pr _{p}[\mathrm{dtDepth} \gt t]\).

33.2 Declarations

Definition 33.1 Restriction of a decision tree

✓

Given a decision tree \(T\) and a partial assignment \(\rho \), the restricted tree \(\mathrm{dtRestrict}\, T\, \rho \) is obtained by collapsing every branch whose query variable is fixed by \(\rho \) into the corresponding subtree, and keeping unrestricted branches intact.

Theorem 33.2 Restriction does not increase depth

✓

For every decision tree \(T\) and restriction \(\rho \), the depth of the restricted tree satisfies \(\mathrm{depth}(\mathrm{dtRestrict}\, T\, \rho ) \le \mathrm{depth}(T)\).

Theorem 33.3 Evaluation of a restricted tree

✓

For every decision tree \(T\), restriction \(\rho \), and input \(x\), the restricted tree evaluates as \((\mathrm{dtRestrict}\, T\, \rho ).\mathrm{eval}(x) = T.\mathrm{eval}(\mathrm{extend}\, \rho \, x)\), where \(\mathrm{extend}\, \rho \, x\) fills in the unset coordinates of \(\rho \) using \(x\).

Theorem 33.4 Decision-tree depth is monotone under restriction

✓

For every Boolean function \(f\) and restriction \(\rho \), the decision-tree depth of the restricted function satisfies \(\mathrm{dtDepth}(f|_\rho ) \le \mathrm{dtDepth}(f)\).

Theorem 33.5 Composing restrictions further decreases depth

✓

For every Boolean function \(f\) and restrictions \(\rho _1, \rho _2\), restricting by the composed restriction can only decrease decision-tree depth: \(\mathrm{dtDepth}(f|_{\rho _1 \circ \rho _2}) \le \mathrm{dtDepth}(f|_{\rho _1})\).

Theorem 33.6 Bernoulli depth-tail probability monotonicity

✓

For every Boolean function \(f\), threshold \(t\), and parameters \(p_1, p_2 \in (0,1]\), the probability that the restricted depth exceeds \(t\) under the stronger Bernoulli restriction of parameter \(p_1 p_2\) is at most that under parameter \(p_1\):

\[ \Pr _{p_1 p_2}\bigl[\mathrm{dtDepth}(f|_\rho ) \gt t\bigr] \le \Pr _{p_1}\bigl[\mathrm{dtDepth}(f|_\rho ) \gt t\bigr]. \]