The Setting
A finite observation of independent uniform signs records only a finite amount of information about their configuration. Its score describes the conditional coordinate sum associated with the recorded value, and its cell cost bounds the Fourier degrees of the events that distinguish its values.
Let be a finite coordinate set and let be its sign cube, with the uniform distribution.✦ The coordinate sign functions on are the real-valued maps , for .
For a finite set and a function , the uniform mean is the normalized sum in (1), including its value on the empty set. (1)✦ Write for the uniform mean on .
For , the Fourier-Walsh character is the coordinate product in (2). (2)✦ For a function and a subset , the real Fourier-Walsh coefficient is the mean in (3). (3)✦ The ordinary real multilinear Fourier degree of a function is the nonnegative integer in (4), with degree zero for constants and the zero function. (4)✦
The Definition
Definition 1. Let be a finite set, let be a set, and let be a map. For , the cell indicator is the function in (5). (5)✦ The cell probability is the uniform mass in (6). (6)✦ For a map , a function and a label , the unnormalized cell moment of on the cell is the mean in (7). (7)✦ Equation (8) defines the cell conditional mean . (8)✦ The conditional average of given is the function that assigns the cell conditional mean to each point, as in (9). (9)✦
On the sign cube , the coordinate sign sum is the function in (10). (10)✦ For a map , the observation score is the conditional average in (11). (11)✦ The retained variance is the second moment of the centered score, given in (12). (12)✦ For an observation , equation (13) defines the standardized cell score . (13)✦ The standardized observation score is the function in (14). (14)✦
An observation with cell cost is a tuple , where and are finite sets, is a map and is a natural number satisfying (15). (15)✦
In the paper, the result reads: for a finite-valued observation of independent uniform signs, is their sum, and , the standardized score for is , and a positive real is a cell degree bound when every indicator has degree at most .
What Is Checked
The finite conditioning definitions are stated for maps from any finite uniform space to an arbitrary label set; observations with cell costs have finite coordinate and label sets and satisfy (15).