Every decision tree has an influential variable

We prove that for any decision tree calculating a boolean function f:{−1,1}n→{−1,1},

where δi is the probability that the ith input variable is read and $\Inf_i(f)$ is the influence of the ith variable on f. The variance, influence and probability are taken with respect to an arbitrary product measure on {−1,1}n. It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced boolean function with a decision tree of depth d has a variable with influence at least 1d. The only previous nontrivial lower bound known was Ω(d2−d). Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with non-boolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least Ω(v4/3/p1/3), where v is the number of vertices and $p \leq \half$ is the critical threshold probability. This supersedes the milestone Ω(v4/3) bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson.