# Is there any notion of sensitivity for probabilistic Boolean functions?

Sensitivity is defined here. Denoting the neighbors of $x$ in the Boolean cube as $N(x)$, we define the sensitivity to be $s(f, x) = \sum_{y \in N(x)} I(f(x) \neq f(y))$, where $I$ is $1$ if the statement inside is true, $0$ otherwise. I'd imagine that you could do the same thing but instead of the indicator function use the probability and a lot of the results from that paper could still go through but in a probabilistic way.

I'm mostly just curious if anyone has looked at this before, as I think the notion I stated works just fine, but if anybody has an alternative notion or a problem with my candidate I'd be interested in that.

I'm not sure if this is the generalization you have in mind, but a natural one is, if $p_x := \Pr[f(x) = 1]$,

\begin{align} s(f,x) &= \sum_{y\in N(x)} D_{TV}(p_x,p_y) \\ &= \sum_{y\in N(x)} |p_x - p_y| \end{align}

where $D_{TV}$ is total variation distance.

• Yes, so glad you wrote this. My friends and I were just discussing this and basically came to the conclusion that you can use any natural distance measure on the distributions defined by $f(x), f(y)$. – Samuel Schlesinger Oct 24 '17 at 22:09
• I'm basically going to go through various distance measures and see which ones give me the theorems I want and then use those. – Samuel Schlesinger Oct 25 '17 at 3:44
• OK, that's going to sound stupid, but what is the meaning of $d_{\rm TV}(p_x,p_y)$ here? I must be missing a key point about how $p_x$ is defined, but if that's what I think ($x$ being fixed, the probability is over $f$, and $p_x\in[0,1]$ is a real number), then $p_x,p_y$ are not probability distributions. They are real numbers in $[0,1]$. Aren't they? – Clement C. Oct 25 '17 at 5:46
• Hi @ClementC., you're right of course, I was just being sloppy and overloading notation. I'm thinking of the real number $p_x$ as the Bernoulli($p_x$) distribution, and taking the distance between the two Bernoullis. Sorry about that. – usul Oct 25 '17 at 15:36
• Well, in that case, for what it's worth: for Bernoulli's TV, L2, and a lot of others are all the same up to an (exact) constant factor. – Clement C. Oct 25 '17 at 15:39

This should work fine inasmuch as if $f$ is now a random function, then you just get the expected sensitivity: $$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \Pr(f(x) \neq f(y)).$$

• I agree. The one unintuitive thing is that the definition of sensitivity is generally supposed to model the way in which the function changes on x via some random perturbation of x's bits, but the sensitivity of a random function f which ignores its input x and returns a 1 with probability one half and 0 with probability one half is actually nonzero, though this doesn't reflect the perturbation thing at all. – Samuel Schlesinger Oct 24 '17 at 18:57
• @SamuelSchlesinger If the random variables $f(x)$ are independent Bernoulli($1/2$) then the sensitivity is very large, which I think "reflects the perturbation thing" okay, right? – Bjørn Kjos-Hanssen Oct 24 '17 at 19:44
• On the other hand if $f$ ignores its input in an even stronger sense (i.e. with probability 1, $f$ is a constant function of $x$) then the sensitivity is zero. – Bjørn Kjos-Hanssen Oct 24 '17 at 19:45
• It actually doesn't in the way that I'd like, I don't think. The other answer reflects the conclusion I came to today after attending a talk on distribution identity testing which jogged my memory on probability distance measures. – Samuel Schlesinger Oct 25 '17 at 3:42