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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 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)).$$

Improve this answer
$\endgroup$
4
  • 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, 2017 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, 2017 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, 2017 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, 2017 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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