A very important quantity in the analysis of a boolean function is the sum of its influences.
Definition 26 The total influence of $f : \{-1,1\}^n \to {\mathbb R}$ is defined to be \[ \mathbf{I}[f] = \sum_{i=1}^n \mathbf{Inf}_i[f]. \]
[...]
|
||||||
|
Given a voting rule $f : \{-1,1\}^n \to \{-1,1\}$ it’s natural to try to measure the “influence” or “power” of the $i$th voter. One can define this to be the “probability that the $i$th vote affects the outcome”. [...] In linear algebra there are two equivalent definitions of what it means for a function to be linear: Definition 29 A function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ is linear if either of the following equivalent conditions hold: $f(x+y) = f(x) + f(y)$ for all $x, y \in {\mathbb [...] For variety’s sake, in this section we write the Hamming cube as ${\mathbb F}_2^n$ rather than $\{-1,1\}^n$. In developing the Fourier expansion, we have generalized from boolean-valued boolean functions $f : {\mathbb F}_2^n \to \{-1,1\}$ to real-valued boolean functions $f : {\mathbb F}_2^n \to {\mathbb R}$. Boolean-valued functions arise more often in [...] As we have seen, the Fourier expansion of $f : \{-1,1\}^n \to {\mathbb R}$ can be thought of as the representation of $f$ over the orthonormal basis of parity functions $(\chi_S)_{S \subseteq [n]}$. In this basis, $f$ has $2^n$ “coordinates”, and these are precisely the Fourier coefficients of $f$. The “coordinate” of $f$ [...] For $x \in \{-1,1\}^n$, the number $\chi_S(x) = \prod_{i \in S} x_i$ is in $\{-1,1\}$. Thus $\chi_S : \{-1,1\}^n \to \{-1,1\}$ is a boolean function; it computes the logical parity, or exclusive-or (XOR), of the bits $(x_i)_{i \in S}$. The parity functions play a special role in the analysis of boolean functions: [...] The Fourier expansion of a boolean function $f : \{-1,1\}^n \to \{-1,1\}$ is simply its representation as a real, multilinear polynomial. (Multilinear means that no variable $x_i$ appears squared, cubed, etc.) For example, suppose $n = 2$ and $f = {\textstyle \min_2}$, the “minimum” function on $2$ bits: [...] This is a book about boolean functions, \begin{equation*} f : \{0,1\}^n \to \{0,1\}. \end{equation*} Here $f$ maps each length-$n$ binary vector, or string, into a single binary value, or bit. Boolean functions arise in many areas of computer science and mathematics. Here are some examples: [...] |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments