0
$\begingroup$

Let $f: \{-1,1\}^n \rightarrow \mathbb{R}$

Then the influence function of $x_i$ is defined by $$ \text{Inf}_i(f) = \mathbb{E}_{(x_1,...,x_{i-1},x_{i+1},...,x_n)}[\text{Var}_{x_i}[f]]$$

What does the subscript on the expectation mean? And what does the subscript on the Var mean? The probability space in question is the uniform distrubtion on $\{-1, 1\}^n$

$\endgroup$
1
$\begingroup$

Assume that the product space $\Omega=X\times Y$ is endowed with the product probability $P=\mu\otimes\nu$ for some probability $\mu$ on $X$ and some probability $\nu$ on $Y$. For every (integrable) random variable $Z$ on $\Omega$, $E_x(Z)$ is the random variable $T$ on $Y$ defined, for every $y$ in $Y$, by $$T(y)=\int_XZ(x,y)\mathrm d\mu(x),$$ and $$E_y(T)=\int_YT(y)\mathrm d\nu(y).$$ Likewise, $\mathrm{Var}_x(Z)=E_x(Z^2)-(E_x(Z))^2$, where $E_x(Z^2)$ is the random variable $S$ on $Y$ defined, for every $y$ in $Y$, by $$S(y)=\int_XZ(x,y)^2\mathrm d\mu(x),$$ and $$E_y(S)=\int_YS(y)\mathrm d\nu(y).$$ Note that, in general, $$E_y(\mathrm{Var}_x(Z))\ne\mathrm{Var}(Z),$$ since $$E_y(\mathrm{Var}_x(Z))=\int_\Omega Z^2\mathrm dP-\int_Y\left(\int_XZ(x,y)\mathrm d\mu(x)\right)^2\mathrm d\nu(y),$$ while $$\mathrm{Var}(Z)=\int_\Omega Z^2\mathrm dP-\left(\int_\Omega Z\mathrm dP\right)^2=\int_\Omega Z^2\mathrm dP-\left(\int_Y\int_XZ(x,y)\mathrm d\mu(x)\mathrm d\nu(y)\right)^2.$$ This shows the general inequality $$E_y(\mathrm{Var}_x(Z))\leqslant\mathrm{Var}(Z).$$

$\endgroup$
  • $\begingroup$ I can't reconcile this with the expression from my question. The inner variance would be only a random variable on $\{x_1,...,x_{i-1}, x_{i+1}, ... x_{n}\}$ since we have integrated out the randomness in $x_i$. Then taking the outer expectiation would have no effect, leaving the final expression as a random variable on $\{x_1,...,x_{i-1}, x_{i+1}, ... x_{n}\}$ when in fact it should be some deterministic constant $\in \mathbb{R}$ $\endgroup$ – Mark Sep 16 '14 at 16:39
  • 1
    $\begingroup$ The inner variance is indeed a random variable depending on $(x_1,...,x_{i-1},x_{i+1},...,x_n)$. The outer expectation integrates this with respect to the distribution of $(x_1,...,x_{i-1},x_{i+1},...,x_n)$ hence the result is deterministic. Exactly what my post describes with $x=x_i$ and $y=(x_1,...,x_{i-1},x_{i+1},...,x_n)$. $\endgroup$ – Did Sep 16 '14 at 16:52
  • $\begingroup$ Ah yes I swapped the domains thanks $\endgroup$ – Mark Sep 16 '14 at 17:16

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.