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

<p>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$.</p>

CC BY-SA 3.0
2014-04-13T18:20:31.170Z
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
CC BY-SA 4.0
2020-03-05T12:49:26.090Z
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.
Thomas Ahle
CC BY-SA 4.0
2020-04-16T17:35:21.570Z
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.
Amir
CC BY-SA 3.0
2014-04-13T17:25:44.063Z
2014-04-15T21:30:46.457Z
2014-04-15T21:30:46.457Z
Amir
<p>I'll answer the second part of the question.</p>

<p><strong>I. Eigenvalues and Eigenfunctions</strong></p>

<p>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, &amp;\text{ if } x =0,\\
p_2, &amp;\text{ if } x =1.
\end{cases}$$
with eigenvalues $1$ and $1-p_1 - p_2$, respectively.</p>

<p>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)) &amp;= 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)) \\
&amp;= \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*}</p>

<p>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)$).</p>

<p><strong>II. Multiplicative Property</strong></p>

<p>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' &amp;= 1 - p_1\cdot (2- (p_1+p_2)) - p_2\cdot (2- (p_1+p_2)) \\
&amp;= 1 - (p_1+p+2) (2- (p_1+p_2)) \\
&amp;= 1 - 2(p_1 +p_2) + (p_1 + p_2)^2 = (1-p_1-p_2)^2.
\end{align*}</p>

<p><strong>III. Relation to the Bonami—Beckner operator</strong></p>

<p>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.</p>

CC BY-SA 3.0
2012-12-29T08:26:05.790Z
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
CC BY-SA 3.0
2013-09-11T04:45:19.767Z
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
CC BY-SA 3.0
2013-09-11T05:56:51.820Z
(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
CC BY-SA 3.0
2012-12-29T00:01:47.407Z
2012-12-29T08:32:14.450Z
2012-12-29T08:32:14.450Z
Yury
<p>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)]$</p>

<p>$\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).</p>

<p>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.)</p>

<p>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.</p>

<boolean-functions><fourier-analysis>
An extension of the noise operator
Amir
# An extension of the noise operator

(Asked by: username_0 on 2012-12-28)

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.

**Tags:** boolean-functions, fourier-analysis

---

## 2 answers

### Answer by username_3 on 2012-12-29. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  
> **username_3**: (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$.  

---

### Answer by username_0 on 2014-04-13. Score: 4

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$.

> **Comments:**
> **username_1**: 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)  
> **username_2**: 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.  
> **username_0**: 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.  

---

