= Three-bit majority decision tree
{title2=$\operatorname{MAJ}_3$}
Three votes give a small but revealing <majority function>:
$$
m(x_1,x_2,x_3)=\begin{cases}1,&x_1+x_2+x_3\geq2,\\0,&x_1+x_2+x_3<2.\end{cases}
$$
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.
\Image[/majority-three-bit-adaptive-decision-tree.png]
{title=An exact three-bit majority decision tree: equal first answers stop after two queries}
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>.
|| $x_1x_2x_3$
|| <Majority function> <output>
|| Queried coordinates for the <majority function>
|| <Majority function> query count
|| <Parity> <output>
|| <Parity> query count
| 000
| 0
| $1,2$
| 2
| 0
| 3
| 001
| 0
| $1,2$
| 2
| 1
| 3
| 010
| 0
| $1,2,3$
| 3
| 1
| 3
| 011
| 1
| $1,2,3$
| 3
| 0
| 3
| 100
| 0
| $1,2,3$
| 3
| 1
| 3
| 101
| 1
| $1,2,3$
| 3
| 0
| 3
| 110
| 1
| $1,2$
| 2
| 0
| 3
| 111
| 1
| $1,2$
| 2
| 1
| 3
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.
Back to article page
