Name
Abstract | ||
|---|---|---|
A Boolean function $f : \{0, 1\}^{n} \rightarrow \{0, 1\}$ is called trivial if it depends on only one coordinate. We show that nontrivial Boolean functions of positively correlated random variables are strictly less correlated than the variables themselves. This improves on a correlation inequality of Witsenhausen. Over the last decade, several people in computer science and computer chess have investigated the problem of quality and reliability in game-tree searching, where the heuristic evaluation function is not free of errors. In random models with independent leaf values and independently occuring errors, a phenomenon of pathology was observed: the deeper the search in the tree, the worse the final estimate of the root value. The main result of this note implies that pathology is not only a feature of game trees, but appears in any sequence of increasing bivalued recursion trees with independent leaf values, independently occuring errors, and nontrivial recursion rules. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1137/S0895480192240470 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
boolean function,recursion trees,nontrivial boolean function,boolean functions,nontrivial recursion rule,random model,computer chess,occuring error,heuristic evaluation function,computer science,bivalued recursion tree,independent leaf value,game trees | Boolean function,Discrete mathematics,Combinatorics,Random variable,Correlation inequality,Evaluation function,Game tree,Mathematics,Pathology,Recursion,Theory of computation,Search tree | Journal |
Volume | Issue | ISSN |
8 | 4 | 0895-4801 |
Citations | PageRank | References |
2 | 0.41 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ingo Althofer | 1 | 2 | 1.08 |
| Imre Leader | 2 | 266 | 49.79 |