Let \(n\) and \(k\) be natural numbers with \(k \le n\). Among all restrictions on \(n\) variables — maps assigning each variable either a fixed Boolean value or leaving it free — those whose set of free variables has cardinality exactly \(k\) number precisely \(\binom {n}{k}\, 2^{\, n-k}\).

Let \(f\) be a Boolean function on \(n\) variables and fix natural numbers \(d\) and \(k\). For a restriction \(\rho \) on these variables, write \(f|_\rho \) for the restricted function that sends a point \(x\) to the value of \(f\) obtained by fixing each assigned coordinate as \(\rho \) prescribes and reading each free coordinate off \(x\), and call \(\rho \) bad for \(f\) at depth \(d\) when the decision-tree depth of \(f|_\rho \) is strictly greater than \(d\). Then the number of restrictions that have exactly \(k\) free variables and are bad for \(f\) at depth \(d\) is the same whether these are counted within the collection of all restrictions with exactly \(k\) free variables or within the collection of all restrictions on the \(n\) variables that both have exactly \(k\) free variables and are bad for \(f\) at depth \(d\).

Let \(f\) be a DNF formula on \(n\) Boolean variables with \(n \ge 1\), and suppose every term of \(f\) has width at most \(w\), so that \(f\) is a disjunction of conjunctions of at most \(w\) literals. Assume that no variable occurs more than once within any single term, that is, each term consists of literals with pairwise distinct variables (and hence has no repeated literal). Fix natural numbers \(k\) and \(d\) with \(5k \le n\), and draw a restriction \(\rho \) uniformly at random from the fixed-size model \(R_k\), which is uniform over all restrictions of the \(n\) variables that leave exactly \(k\) variables free. Then the probability that the restricted function \(x \mapsto f(\rho .\mathrm{extend}\, x)\) has decision-tree depth greater than \(d\) satisfies

where \(\mathrm{depth}(g)\) denotes the least depth of a decision tree computing \(g\).

Let \(f\) be a DNF formula on \(n \ge 1\) variables in which every term has width at most \(w\), where \(w \ge 1\), and in which each term is reduced: no literal is repeated, and any two literals of a term sharing the same variable are equal (so a variable occurs at most once, and never with both polarities, within a term). For a Boolean function \(g\) on some set of inputs, write \(D(g)\) for its decision-tree depth, the least depth of a decision tree computing \(g\). Fix a natural number \(d\) and an integer \(k\) with \(k \le n\), and draw a restriction \(\rho \) uniformly at random among all restrictions of the \(n\) variables that leave exactly \(k\) variables free (the fixed-size restriction model \(R_k\)). Writing \(f|_\rho \) for the function obtained by fixing each set variable to the value assigned by \(\rho \) and keeping the \(k\) free variables as inputs, one has

Let \(f\) be a DNF formula on \(n \ge 1\) Boolean variables whose width is at most \(w\), with \(w \ge 1\), and suppose that within each term of \(f\) no variable occurs more than once — that is, every term is a repetition-free list of literals in which any two literals sharing a variable are identical. Fix an integer \(k\) with \(0 \le k \le n\), and let \(R_k\) denote the fixed-size restriction model, uniform over all restrictions of the \(n\) variables that leave exactly \(k\) of them free. Then for every \(d\), the probability under \(R_k\) that the restricted function \(f_\rho \) (with the assigned coordinates fixed according to \(\rho \) and the \(k\) free coordinates left as inputs) has decision-tree depth greater than \(d\) satisfies