4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Samuel Schlesinger Oct 24 '17 at 22:09
  • $\begingroup$ I'm basically going to go through various distance measures and see which ones give me the theorems I want and then use those. $\endgroup$ – Samuel Schlesinger Oct 25 '17 at 3:44
  • $\begingroup$ 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? $\endgroup$ – Clement C. Oct 25 '17 at 5:46
  • $\begingroup$ 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. $\endgroup$ – usul Oct 25 '17 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Clement C. Oct 25 '17 at 15:39
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Samuel Schlesinger Oct 24 '17 at 18:57
  • $\begingroup$ @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? $\endgroup$ – Bjørn Kjos-Hanssen Oct 24 '17 at 19:44
  • $\begingroup$ 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. $\endgroup$ – Bjørn Kjos-Hanssen Oct 24 '17 at 19:45
  • $\begingroup$ 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. $\endgroup$ – Samuel Schlesinger Oct 25 '17 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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