# An extension of the noise operator

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.

-

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.

-
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. – Amir Dec 29 '12 at 8:26
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? – Amir Sep 11 '13 at 4:45
(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$. – Yury Sep 11 '13 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$.

-
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) – Suresh Venkat Apr 13 '14 at 18:20