= Decision-tree query cost
{title2=$q_T(x)$}
For a particular <decision tree> $T$, its <decision-tree query cost> $q_T(x)$ is the number of queries along the <graph path> followed by <input> $x$. Its actual tree depth is
$$
h(T)=\max_{x\in\{0,1\}^n}q_T(x).
$$
The query <vertices> count as operations; each is followed by one answer <edge>. Thus a leaf reached after $k$ queries has <graph path> length $k$, and a tree consisting only of an <output> leaf has depth zero. With no repeated coordinates, $0\leq q_T(x)\leq n$. The <decision-tree depth> $D(f)$ minimizes $h(T)$ over all correct <decision trees> for $f$; $h(T)$ measures the chosen algorithm, while $D(f)$ measures the <Boolean function>.
Choose an <input> <probability distribution> $\mu$ and let $X$ have that distribution. Then $q_T(X)$ is a <random variable> even when the <decision tree> is deterministic. Its <probability mass function> describes how often each path length occurs, and its <expected value> is the <expected query cost>. None of these quantities changes the actual maximum depth of $T$.
\Image[/majority-parity-query-cost-distributions.png]
{title=Uniform three-bit inputs: query-count distributions and coordinate revealment for majority and parity}
The left panel aggregates the eight <inputs> from the <three-bit majority decision tree>: four cost two queries and four cost three. <Parity> always costs three. The right panel asks a different question, which coordinates are inspected: the <majority function> algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are <probabilities> of inspection, not <probabilities> that a <bit> equals one.
Back to article page
