Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits.
Continue reading §8.4: $p$biased analysis


Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits. In this section we describe a basisfree kind of “Fourier expansion” for functions on general product domains. We will refer to it as the orthogonal decomposition of $f \in L^2(\Omega^n, \pi^{\otimes n})$ though it goes by several other names in the literature: e.g., Hoeffding, Efron–Stein, or ANOVA decomposition. In this section we will revisit a number of combinatorial/probabilistic notions and show that for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$, these notions have familiar Fourier formulas which don’t depend on the Fourier basis. We will now begin to discuss functions on (finite) product probability spaces. So far we have studied functions $f : \{0,1\}^n \to {\mathbb R}$. What about, say, $f : \{0,1,2\}^n \to {\mathbb R}$? In fact, very little of what we’ve done so far depends on the domain being $\{0,1\}^n$; what it has mostly depended on is our viewing the domain as a product probability distribution. Indeed, much of analysis of boolean functions carries over to the case of functions $f : \Omega_1 \times \cdots \times \Omega_n \to {\mathbb R}$ where the domain has a product probability distribution $\pi_1 \otimes \cdots \otimes \pi_n$. There are two main exceptions: the “derivative” operator $\mathrm{D}_i$ does not generalize to the case when $\Omega_i > 2$ (though the Laplacian operator $\mathrm{L}_i$ does); and, the important notion of hypercontractivity (introduced in the next chapter) depends strongly on the probability distributions $\pi_i$. In this chapter we focus on the case where all the $\Omega_i$’s are the same, as are the $\pi_i$’s. (This is just to save on notation; it will be clear that everything we do holds in the more general setting.) Important classic cases include functions on the $p$biased hypercube (Section 4) and functions on abelian groups (Section 5). For the issue of generalizing the range of functions — e.g., studying functions $f : \{0,1,2\}^n \to \{0,1,2\}$ — see the exercises. The last video lecture for my CMU course on Analysis of Boolean Functions has just been posted. Except for responding to comments, the blog will be going on hiatus for a little while. Next semester I’ll post the final chapters of the book; there will be between 4 and 7 of them, depending on how much energy I have. Happy holidays…….. The video for Lecture 23 of the online course is available on the course web page. The video for Lecture 22 of the online course is available on the course web page. The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of errorcorrecting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as in Exercise 8); it was later rediscovered by Parnas, Ron, and Samorodnitsky [PRS01,PRS02]. The relevance of Arrow’s Theorem to testing dictatorship was pointed out by Kalai [Kal02]. The video for Lecture 21 of the online course is available on the course web page. 

Copyright © 2017 Ryan O'Donnell  All Rights Reserved 
Recent comments