<p>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]$,</p>

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

<p>where $D_{TV}$ is total variation distance.</p>

CC BY-SA 3.0
2017-10-24T22:09:51.520Z
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
CC BY-SA 3.0
2017-10-25T03:44:26.593Z
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
CC BY-SA 3.0
2017-10-25T05:46:53.453Z
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.
CC BY-SA 3.0
2017-10-25T15:36:11.787Z
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
CC BY-SA 3.0
2017-10-25T15:39:06.917Z
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.
CC BY-SA 3.0
2017-10-25T15:56:45.903Z
Yep - good point.
usul
CC BY-SA 3.0
2017-10-24T20:55:48.977Z
2017-10-24T20:55:48.977Z
usul
<p>This should work fine inasmuch as if $f$ is now a random function, then you just get the <em>expected sensitivity</em>:
$$\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)).$$</p>

CC BY-SA 3.0
2017-10-24T18:57:52.667Z
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
CC BY-SA 3.0
2017-10-24T19:44:40.010Z
@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
CC BY-SA 3.0
2017-10-24T19:45:28.343Z
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
CC BY-SA 3.0
2017-10-25T03:42:04.213Z
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
CC BY-SA 3.0
2017-10-24T07:49:07.280Z
2017-10-24T07:49:07.280Z
Bjørn Kjos-Hanssen
<p>Sensitivity is defined <a href="https://arxiv.org/pdf/1508.02420.pdf" rel="nofollow noreferrer">here</a>. 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.</p>

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

<circuits><probabilistic-circuits>
Is there any notion of sensitivity for probabilistic Boolean functions?
Samuel Schlesinger
# Is there any notion of sensitivity for probabilistic Boolean functions?

(Asked by: username_0 on 2017-10-21)

Sensitivity is defined [here](https://arxiv.org/pdf/1508.02420.pdf). 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.

**Tags:** circuits, probabilistic-circuits

---

## 2 answers

### Answer by username_1 on 2017-10-24. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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)$.  
> **username_0**: I'm basically going to go through various distance measures and see which ones give me the theorems I want and then use those.  
> **username_2**: 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?  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_1**: Yep - good point.  

---

### Answer by username_3 on 2017-10-24. Score: 2

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

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

---

