In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator $T_{\varepsilon}$ on real-valued Boolean functions. Given a function $f: \{0,1\}^n \to \mathbb{R}$ and $\varepsilon$, $p$ s.t $0 \leq \varepsilon \leq 1$, $\varepsilon = 1 - 2p$, we define $T_{\varepsilon} \to \mathbb{R}$ as $T_{\varepsilon} f(x) = E_{y \sim \mu_p} [f(x+y)]$

$\mu_p$ is the distribution on $y$ obtained by setting each bit of a $n$-bit vector to be $1$ independently with probability $p$ and $0$ otherwise. Equivalently, we can think of this process as flipping each bit of $x$ with independent probability $p$. Now this noise operator has many useful properties, including being multiplicative $T_{\varepsilon_1} T_{\varepsilon_2} = T_{\varepsilon_1 \varepsilon_2}$ and having nice eigenvalues and eigenvectors($T_{\varepsilon}(\chi_S) = \varepsilon^{|S|} \chi_S$ where $\chi_S$ belongs to the parity basis).

Let me now define my extension of $T_\varepsilon$, which I denote as $R_{(p_1,p_2)}$. $R_{(p_1,p_2)} \to \mathbb{R}$ is given by $R_{(p_1,p_2)} f(x) = E_{y \sim \mu_{p,x}} [f(x+y)]$. But here our distribution $\mu_{p,x}$ is such that we flip the $1$ bits of $x$ to $0$ with probability $p_1$ and $0$ bits of $x$ to $1$ with probability $p_2$. ( $\mu_{p,x}$ is now clearly a distribution dependent on the $x$ where the function is evaluated, and if $p_1 = p_2$ then $R_{(p_1,p_2)}$ reduces to the 'regular' noise operator.)

I was wondering, has this operator $R_{(p_1,p_2)}$ already been well-studied somewhere in the literature? Or are the basic properties of it obvious? I am just starting with Boolean analysis, so this might be straightforward to someone more familiar with the theory than I am. In particular I am interested in if the eigenvectors and eigenvalues have some nice characterization, or whether there is any multiplicative property.


2 Answers 2


I'll answer the second part of the question.

I. Eigenvalues and Eigenfunctions

Let's first consider the one dimensional case $n=1$. It is easy to check that the operator $R_{p_1,p_2}$ has two eigenfunctions: $1$ and $$\xi(x) = (p_1+p_2)x - p_1 = \begin{cases} -p_1, &\text{ if } x =0,\\ p_2, &\text{ if } x =1. \end{cases}$$ with eigenvalues $1$ and $1-p_1 - p_2$, respectively.

Now consider the general case. For $S\subset \{1,\dots,n\}$, let $\xi_S(x) = \prod_{i\in S} \xi(x_i)$. Observe that $\xi_S$ is an eigenfunction of $R_{p_1,p_2}$. Indeed since all variables $x_i$ are independent, we have \begin{align*} R_{p_1,p_2}(\xi(x)) &= R_{p_1,p_2}\left(\prod_{i\in S} \xi(x_i)\right) = \prod_{i\in S} R_{p_1,p_2}(\xi(x_i)) \\ &= \prod_{i\in S}\left((1-p_1 - p_2)\xi(x_i)\right) = (1-p_1 - p_2)^{|S|} \xi_S(x). \end{align*}

We get that $\xi_S(x)$ is an eigenfunction of $R_{p_1,p_2}$ with eigenvalue $(1-p_1-p_2)^{|S|}$ for every $S\subset \{1,\dots,n\}$. Since functions $\xi_S(x)$ span the whole space, $R_{p_1,p_2}$ has no other eigenfunctions (that are not linear combinations of $\xi_S(x)$).

II. Multiplicative Property

In general, the “multiplicative property” doesn't hold for $R_{p_1,p_2}$ since the eigenbasis of $R_{p_1,p_2}$ depends on $p_1$ and $p_2$. However, we have $$R_{p_1,p_2}^2 = R_{p_1',p_2'},$$ where $p_1' = 2p_1- (p_1+p_2)p_1$ and $p_2' = 2p_2- (p_1+p_2)p_2$. To verify that, first note that $R_{p_1,p_2}$ and $R_{p_1',p_2'}$ have the same set of eigenfunctions $\{\xi_S\}$. We have, $$R_{p_1,p_2}^2(\xi_S) = (1-p_1-p_2)^{2|S|} \xi_S=(1-p_1'-p_2')^{|S|}\xi_S = R_{p_1',p_2'} (\xi_S) $$ since \begin{align*} 1-p_1'-p_2' &= 1 - p_1\cdot (2- (p_1+p_2)) - p_2\cdot (2- (p_1+p_2)) \\ &= 1 - (p_1+p+2) (2- (p_1+p_2)) \\ &= 1 - 2(p_1 +p_2) + (p_1 + p_2)^2 = (1-p_1-p_2)^2. \end{align*}

III. Relation to the Bonami—Beckner operator

Let us think of functions from $\{0,1\}^n$ to ${\mathbb R}$ as polylinear polynomials. Let $\delta = \frac{1}{2}\cdot \frac{p_1-p_2}{p_1+p_2}$. Consider the operator $$A_{\delta}(f) = f(x_1 + \delta, \dots, x_n + \delta).$$ It maps every multilinear polynomial $f$ to a multilinear polynomial $A[f]$. We have, $$R_{p_1,p_2}(f) = A_{\delta}^{-1} T_{\varepsilon}A_{\delta}(f),$$ where $\varepsilon = 1 - p_1 - p_2$. Note that parts I and II follow from this formula and properties of the Bonami—Beckner operator.

  • $\begingroup$ Yury, thank you for the answer! That's a good starting point for me to work with; I should now be able to work out if there are analogues of the hyper contractive inequality. Will post back here if I get any more interesting analysis. $\endgroup$
    – Amir
    Dec 29, 2012 at 8:26
  • $\begingroup$ This is very long after the fact, but I am curious how you derived the third part and the relation to the Becker Bonami operator? $\endgroup$
    – Amir
    Sep 11, 2013 at 4:45
  • $\begingroup$ (a) It is sufficient to check the identity for $f=1$ and $f=x_i$. If it holds for $1$ and $x_i$, then it's easy to see that it holds for all characters. By linearity, it holds for all functions. (b) Alternatively, from I, $T_\varepsilon$ and $R_{p_1,p_2}$ have the same set of eigenvalues; eigenvector $\prod_{i\in S} x_i$ of $T$ “corresponds” to eigenvector $\prod_{i\in S} \xi(x_i)$ of $R$. Thus $R(f) = A^{-1} T A(f)$ where A is a linear map that maps $\xi(x)$ to $x$. $\endgroup$
    – Yury
    Sep 11, 2013 at 5:56

We were eventually able to analyze hypercontractive properties of $R_{p_1, p_2}$ (http://arxiv.org/abs/1404.1191), building off of the main Fourier analysis of $R_{p,0}$ by Ahlberg, Broman, Griffiths and Morris (http://arxiv.org/abs/1108.0310).

To summarize, the effect of a biased operator $R_{p,0}$ on a function $f$ can be analyzed as a symmetric noise operator in a biased measure space. This gives a weak form of hypercontractivity, which depends on how the $\ell_2$ norm of $f$ varies when switching to a choice of biased measure $\mu$ dependent on $p$.

  • $\begingroup$ You might want to 'accept' this answer so that the question doesn't keep popping up (disclaimer: I am an author on the linked paper) $\endgroup$ Apr 13, 2014 at 18:20
  • $\begingroup$ This is a nice approach. Do you think it's possible to bound $\|R_{p_1,p_2}f\|_{s,\frac12}$ rather than just $\|R_{p_1,p_2}f\|_{2,\frac12}$? It seems hardere to go over Parseval's then. $\endgroup$ Mar 5, 2020 at 12:49
  • $\begingroup$ Hi Thomas. I do believe one should be able to bound it, I haven't had the chance to sit down and do the math on pen and paper. But any techniques that work for bounding the $p$-norm of the symmetric operator should be applicable here as well. $\endgroup$
    – Amir
    Apr 16, 2020 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.