Expected query cost (${\mathbb{E}}_{\mu }[q_T(X)]$)

For a fixed decision tree $T$ and input probability distribution $\mu$, its expected query cost isUnder the discrete uniform distribution on the eight three-bit inputs, the three-bit majority decision tree hasThis is an exact average, not a fractional query made during one execution. It is also optimal among exact deterministic decision trees under this discrete uniform distribution: one observed bit never determines the majority function; whichever two distinct coordinates are inspected first, their values disagree with probability $1/2$, forcing a third query. In comparison, querying all three bits unconditionally has the same actual depth three but expected query cost three.

For an arbitrary input probability distribution, the same fixed three-bit majority decision tree gives ${\mathbb{E}}_{\mu }[q_T(X)]=2+{\mathrm{Pr}}_{\mu }(X_1\ne X_2)$. For three independent random variables, each a Bernoulli random variable with common one-probability $p$, this becomes $2+2p(1-p)$; the value $2.5$ depends on $p=1/2$. Averaging over inputs should also be distinguished from averaging over an algorithm's internal random choices at a fixed input.^[ref]