= Coordinate revealment
{title2=$\delta_i(T,\mu)$}
The <coordinate revealment> of coordinate $i$ for a <decision tree> $T$ under <input> <probability distribution> $\mu$ is
$$
\delta_i(T,\mu)=\Pr_{X\sim\mu}(T\text{ queries coordinate }i).
$$
It depends on the chosen <decision tree> and the <probability distribution>, not just on the <Boolean function>. Since no coordinate is queried twice on a <graph path>, <indicator functions> give
$$
q_T(X)=\sum_{i=1}^n\mathbf 1_{\{T\text{ queries }i\}},\qquad \mathbb E_\mu[q_T(X)]=\sum_{i=1}^n\delta_i(T,\mu).
$$
The second equality uses <linearity of expectation>; it does not require <independence of random variables> or a <product measure>. The cited paper defines these inspection <probabilities> and their sum for <product measures>; the displayed <indicator function> argument extends the identity to any <input> <probability distribution>.<Every decision tree has an influential variable by Ryan O'Donnell and others>[O'Donnell, Saks, Schramm and Servedio, Every decision tree has an influential variable, section 1.2, p. 2: δ_i(T) and Δ(T); section 3.1, p. 6: distinct coordinates along each root–leaf path]{ref}
For the <three-bit majority decision tree> under the <discrete uniform distribution>, $(\delta_1,\delta_2,\delta_3)=(1,1,1/2)$, whose sum is $2.5$. Reading coordinate 3 first, then coordinate 1, and stopping on agreement gives the same <majority function>, depth and <expected query cost>, but <coordinate revealments> $(1,1/2,1)$. The asymmetry belongs to the chosen query order. <Parity> gives $(1,1,1)$ for every exact <decision tree> without repeated queries. If repeated queries were charged, inspection <probabilities> would count distinct coordinates; total query count would instead require expected multiplicities.
Back to article page
