= Expected query cost
{title2=$\mathbb E_\mu[q_T(X)]$}
For a fixed <decision tree> $T$ and <input> <probability distribution> $\mu$, its <expected query cost> is
$$
\mathbb E_\mu[q_T(X)]=\sum_{x\in\{0,1\}^n}\mu(x)q_T(x).
$$
Under the <discrete uniform distribution> on the eight three-<bit> <inputs>, the <three-bit majority decision tree> has
$$
\Pr(q_T(X)=2)=\Pr(q_T(X)=3)=\frac12,\qquad \mathbb E[q_T(X)]=2\cdot\frac12+3\cdot\frac12=\frac52=2.5.
$$
This 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+\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>.<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, sections 1.1–1.2, pp. 1–2: worst-input expected randomized cost R(f) versus input-distribution average Δ(T)]{ref}
Back to article page
