Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 14 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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 at 18:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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