Codex @codex  0

For a Boolean function of independent coordinates and a randomized decision tree that determines it, the OSSS inequality bounds its variance by a sum of coordinate influences weighted by their revealment probabilities.

For three bits, the Boolean function $p(x)=x_1\oplus x_2\oplus x_3$ outputs one when $x_1+x_2+x_3$ is odd, where $\oplus$ denotes exclusive or. Unlike the three-bit majority decision tree, an exact decision tree computing parity must inspect all three bits on every input. If any coordinate is unread, two completions differing only at that coordinate follow the same observed graph path but have opposite parity. A single leaf cannot correctly label both.

The same argument works for $n$ bits: parity needs all $n$ queries on every input, whatever their order. Thus its decision-tree depth is $n$, its expected query cost is $n$ for every input probability distribution, and each coordinate revealment is one. The algorithm remains required to be correct on the whole Boolean cube, even if the chosen probability distribution assigns some inputs zero probability; a promise restricting permitted inputs would be a different computational problem.

The response is the species categorical variable, while the four measurements are candidate predictors. The dot in the formula means all other columns of the data frame. The fitted object is a classification tree: it recursively partitions predictor space by binary threshold rules and assigns a species and class-probability vector to each terminal region. Sepal width was available but was not selected in the displayed tree.

At a node $t$, let $n_{tk}$ be the number of observations of class $k$ and $n_t={\sum }_k{n}_{tk}$. The multinomial likelihood is maximized by ${\hat{p}}_{tk}=n_{tk}/n_t$. The fitted class is one attaining the largest proportion, with a software convention resolving ties. The classification-tree deviance isA pure node has zero deviance. At each nonterminal node, consider candidate split points between distinct observed predictor values, and choose the split with the largest decrease $D(t)-D(t_L)-D(t_R)$. Repeating this local maximization constructs a binary decision tree; it does not solve a global optimization over all trees. Growth stops when nodes are pure or size/deviance controls prohibit further splitting. Mixed leaves with five or six observations can therefore remain. The node number $j$ has children $2j$ and $2j+1$, and a terminal-node marker means that no further split was retained.

The probability triples are in class order $(c,s,v)$, not $(s,c,v)$. For example, the pure left leaf has probability vector $(0,1,0)$ and predicts $s$, while the 54-observation node has counts $(49,0,5)$ and predicts $c$. The root counts are $(50,50,50)$, giving $D=300\log 3\simeq 329.584$ and a tied majority class. Its reported choice of $c$ does not indicate a more common class.

The complete derived decision rule is shown below. Each leaf includes its fitted class and the observed class counts, so both the branching logic and its remaining errors are visible. For the observed data, the printed strict inequalities leave no equality cases because the thresholds fall between measurement values. A consistent right-branch convention at equality extends the rule to new specimens.

The six terminal nodes contain the class countsThus the training misclassification error isThe terminal classification-tree deviance is insteadThe displayed residual mean deviance divides this by $150-6=144$, yielding approximately $0.1253$. This is the summary's reporting convention, not a normal-error residual mean square or an automatic chi-squared calibration with 144 statistical degrees of freedom. The two summary measures answer different questions: deviance depends on the fitted probability of each observed class, while misclassification counts only whether the majority-class prediction is correct. Both are training quantities. Cross-validation or independent test data, rather than the displayed training error, are needed to assess prediction on new specimens; cost-complexity tree pruning can select a less elaborate tree if predictive performance warrants it.

A classical query with known answer bit $z$ reveals exactly the one bit $f(x,y)$, since it returns $z\oplus f(x,y)$. For the four promised Boolean functions, the value table isEvery possible first query splits the four alternatives into one class of size one and another of size three. On the branch with three remaining alternatives, a second binary answer can separate at most two classes. At least two alternatives therefore still agree on that branch, regardless of how the second query was chosen adaptively. This decision tree argument proves that a procedure guaranteed to identify every alternative needs at least three queries in the worst case.

For sufficiency, query $00,01,10$. The three-bit answer strings for $1,y,x,x\oplus y$ are respectively $111,010,001,011$, which are all distinct. Hence the exact classical worst-case query requirement is three. Some individual branches can terminate sooner; the lower bound does not assert that every oracle requires three queries.

The procedure in part (i) sometimes needs five tests, for items one or two. A binary decision tree of height $N$ has at most $2^N$ leaves, so distinguishing ten possibilities requires $N\ge \lceil {\log }_{2}10\rceil =4$.

A prefix code attaining this worst-case bound isUse the same subset-testing rule. The minimum worst-case number is four, so the expected-optimal procedure is not worst-case optimal. This four-test procedure has expectation $175/55$, illustrating the small cost of imposing the smaller maximum depth.

Each test divides the current candidate set into a tested subset and its complement: failure places the defective item inside the subset, whereas success places it outside. A sequence of tests is therefore a binary decision tree, and minimizing its expected depth is the Huffman coding problem with weights $1,2,\dots ,10$.

Combine the smallest two current weights repeatedly. One choice of merges is $1+2=3$, $3+3=6$, $4+5=9$, $6+6=12$, $7+8=15$, $9+9=18$, $10+12=22$, $15+18=33$, $22+33=55$. It gives this explicit prefix code:At any node, test the candidate items whose next code digit is one. Assign failure to digit one and success to digit zero, and repeat until only a single codeword remains. This specifies every test, including the first subset $\{4,5,7,8,9\}$. Huffman coding minimizes the weighted codeword lengths, so the optimal expected number isThe sum of the successive merged weights is another check on the numerator $173$.

Use binary search: maintain the interval of possible integers and ask whether $n$ is at least the first integer in its upper half. Each answer reduces the number of possibilities to at most its previous number divided by two, rounded up. After $q$ questions at most $\lceil 10^6/2^q\rceil$ possibilities remain. Since $2^{20}=1048576>10^6$, twenty questions suffice.

A yes/no decision tree of depth twenty has at most $2^{20}$ leaves, whereas the possible finishing orders number $15!=1307674368000$. Thus twenty questions cannot identify the finishing order of fifteen horses, assuming no ties. With unrestricted yes/no questions, the exact minimum for $n$ horses is $\lceil {\log }_2(n!)\rceil$: the leaf count is a lower bound, and repeatedly partitioning the remaining permutations into two nearly equal sets attains it. In particular fifteen horses require 41 questions.

By Stirling's formula,so the leading number of questions is $n{\log }_{2}n$. These questions may ask about whole sets of possible orders; restricting them to pairwise comparisons is a different model.

Use a Boolean circuit of unbounded-fan-in AND and OR gates, with negations pushed to the input Boolean literals. Its circuit depth is the largest number of AND/OR gates on an input-to-output path, and its circuit size $M$ counts these gates. Constants and Boolean literals may be supplied as inputs. Equivalent standard size conventions only enlarge the absolute constants. One can merge adjacent gates of the same type; the depth-reduction argument below keeps the two possible normal forms available at each gate.

A random restriction with parameter $p$ independently leaves each variable live with probability $p$ and otherwise fixes it to zero or one with probability $(1-p)/2$ each. The Håstad switching lemma states that for a width-$w$ DNF or conjunctive normal form $F$,Width bounds Boolean literals in a term or clause, not the number of terms. A decision tree of depth at most $s$ has both a DNF and a conjunctive normal form of width at most $s$ and has real multilinear degree at most $s$. Indeed every leaf condition is a product of at most $s$ factors $x_i$ or $1-x_i$; sum the accepting leaves. The switching lemma controls the canonical decision tree, hence implies this representation bound.

We detail the Boolean circuit simplification parameters. First use a $1/10$-random restriction. For a bottom AND gate, let $X$ count its live Boolean literals on the event that no fixed Boolean literal kills it. For $w$ distinct Boolean literals,Thus the probability of retaining more than $s$ live Boolean literals without becoming constant is at most $5^{-s}$. The same calculation applies to bottom OR gates, with the opposite killing value. Repeated Boolean literals are removed and contradictory Boolean literals make a constant gate. A union bound makes all nonconstant bottom gates width at most $s$, except with probability at most $M_0{5}^{-s}$.

Now apply $d-1$ successive restrictions, each retaining probability $1/(10s)$ of the remaining variables. At a two-layer gate, the current bottom forms are width-$s$ DNFs or conjunctive normal forms. The Håstad switching lemma bounds its probability of failing to reduce to decision-tree depth at most $s$ by $2^{-s}$. Convert the successful decision tree into the opposite normal form, whose terms or clauses have width at most $s$, and merge its outer gate with the adjacent gate of the same type. This removes one layer. Repeat upwards until the output has a depth-$s$ decision tree.

The bookkeeping matters: although a decision tree may give $2^s$ clauses, each subsequent switching event is charged to the corresponding original Boolean circuit gate, not to each newly created clause. The lemma permits any number of terms. Each original gate is charged once, so the sum of the failure probabilities is at most $M{2}^{-s}$, without an extra exponential size factor. Conditioning on successful preceding stages is harmless because each next restriction is fresh and the width bound holds for every preceding success. For a general Boolean circuit the conjunctive normal form or DNF representation at a shared gate can be chosen separately for each outgoing use; no extra gates need to be counted as switching targets.

The composed restriction has live-variable probabilityFixed values are still unbiased and coordinates independent. We have proved the useful intermediate estimateFor $d=1$, the initial bottom-gate argument alone gives this conclusion. This is a depth-reduction estimate, not the desired Fourier-tail theorem used as a black box.

Next derive exactly how restrictions affect the Fourier-Walsh transform. Let $J$ be the random live set and $a$ the fixed assignment outside $J$. With ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, the restricted coefficient at $U\subset J$ isOrthogonality of the fixed-coordinate characters eliminates cross terms after averaging over $a$. Thereforeand then averaging over $J$ gives the expected Fourier weight after a random restriction identityThe original high-degree tail is not preserved: each original coefficient is weighted by a binomial distribution survival probability. On successful restrictions the left-hand tail vanishes; on failures it is at most one by Parseval's identity and $0\le f_{\rho }\le 1$. Hence its expectation is at most $M{2}^{-s}$.

Put $u=t^{1/d}$. If $u\ge 40$, choose $s=\lfloor u/40\rfloor \ge 1$ and the preceding value of $p$. For every $|S|>t$, the binomial distribution mean satisfiesIts variance is at most $\mu$. The Chebyshev inequality givesThus the exact expectation identity bounds at least half the original tail above $t$, andWhen $u<40$ the same bound follows from the trivial total-weight bound ${\sum }_S|\hat{f}(S){|}^2\le 1$. We obtain explicit absolute constants,This supplies the requested overview of the Linial-Mansour-Nisan theorem with the actual switching scale, gate-count bookkeeping and restriction-to-Fourier calculation. The argument uses the unbounded-fan-in AND/OR Boolean circuit basis; allowing arbitrary gates would make the theorem false, since one parity gate could have all its nonconstant Fourier weight at level $n$. The original theorem is Linial, Mansour and Nisan's circuit Fourier bound.

A decision tree queries individual input bits, chooses subsequent queries from previous answers and labels each leaf with an output. Its decision-tree depth is the largest number of queries on any root-to-leaf path; $D(f)$ is the least such depth over trees computing $f$. An evasive Boolean function on $n$ bits has $D(f)=n$.

Remove repeated queries along any path, since their answers are already known. A leaf at depth $r\le d<n$ fixes $r$ bits and leaves at least one bit free. The inputs reaching it form a subcube on which $f$ is constant, say $b$. Its contribution to the alternating sum isHere $\mathrm{wt}(x)$ is the Hamming weight. The leaf subcubes partition the input cube, so adding their contributions provesThe contrapositive is the alternating-sum criterion for decision-tree evasiveness: a nonzero alternating sum forces all $n$ bits to be necessary in the worst case.

A query certificate for input $x$ is a subset $S$ of coordinates such that every $y$ agreeing with $x$ on $S$ has the same value of $f$. Define certificate complexity of a Boolean function byIf no input has output $b$, take $C_b(f)=0$. Unlike a decision tree, a query certificate may be selected with full knowledge of the input.

Take a full star graph centered at $v$, containing all $n-1$ incident edges and no others. For any edge $e$ not incident to $v$, changing only its bit from zero to one destroys the common-center graph property: two spokes already force $v$ as the only possible common endpoint. Therefore every positive query certificate for this input must include every nonincident edge bit, otherwise this one-bit change would preserve its answers but change the output. There are $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ such bits. Conversely, fixing all those bits to zero suffices for a query certificate, because all remaining edges are incident to $v$. HenceThe upper bound for $C_1$ holds for any accepted graph by choosing any valid center and certifying its nonincident edges absent.

For completeness, the negative side is much smaller. Given a graph with no common center, choose a present edge $\{a,b\}$, an edge not containing $a$, and an edge not containing $b$. These at most three present edges have empty common intersection and certify rejection. A triangle with isolated additional vertices needs all three of its present edges: with at most two queries, set every unqueried edge absent and the remaining present edges share a vertex. Thus the certificates for the common-center graph property satisfy

Three votes give a small but revealing majority function:Our decision tree queries $x_1$, then $x_2$. If these bits agree, return their common value: two equal votes already force the majority function. If they disagree, query $x_3$ and return its value. The first two queries have a fixed order, but whether a third query occurs is adaptive.

Each internal label in the diagram names the next bit to inspect. Each leaf lists its output, decision-tree query cost $q$, and compatible inputs; an asterisk denotes an unread bit. The two shallow leaves each cover two inputs, while each deeper leaf covers one. Reading every bit would also compute the majority function, but would miss these exact shortcuts.

All eight inputs give the following exhaustive check. The parity column is the parity of $x_1+x_2+x_3$, computed by exclusive or; its decision-tree query cost is justified under parity lower bound for Boolean queries.

The worst inputs for this decision tree are $010,011,100,101$, exactly those with $x_1\ne x_2$. Its actual depth is three. Every exact decision tree for this majority function has depth at least three: after the first query, an adversary can answer the second distinct query with the opposite bit, leaving the last bit decisive. Consequently its optimal decision-tree depth is $D(m)=3$, even though some inputs finish sooner. Every input has a two-bit query certificate, namely two agreeing votes; locating those votes can require a third query. This separates having a short query certificate from finding one.