Global sensitivity anova and sobol estimation

Let $m=\mathbb{E}[g(U)]$ and $h(x)=g(a+Lx)-m$ for $0\le x\le 1$. Define $H(t)=h(2t)$ for $0\le t\le 1\mathrm{/}2$ and $H(t)=h(2-2t)$ for $1\mathrm{/}2\le t\le 1$, then extend $H$ periodically to $\mathbb{T}$. The two absolutely continuous pieces match at $t=1\mathrm{/}2$, and $H(0)=H(1)$. A finite paste of absolutely continuous pieces with matching endpoint values is absolutely continuous: split every interval crossing the junction into its at most two pieces and apply [F1] on each piece with half the error tolerance. Thus $H$ is absolutely continuous on the period interval. Its mean is zero, $\mathrm{\parallel }H{\mathrm{\parallel }}_{L^2(\mathbb{T})}^2=\mathrm{Var}(g(U))$, and affine changes of variables give $\mathrm{\parallel }{H}^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(\mathbb{T})}^2=4L^2\mathbb{E}\mathrm{\mid }{g}^{\mathrm{\prime }}(U){\mathrm{\mid }}^2$.

For each integer $n$, apply integration by parts [F2] to $H(t)e^{-2\pi int}$ on $[0,1]$, taking real and imaginary parts. The boundary term vanishes since $H(0)=H(1)$ and $e^{-2\pi in}=1$, giving $\widehat{H^{\mathrm{\prime }}}(n)=2\pi in\widehat{H}(n)$. Parseval [F4] and the zero mean in step 1.1 yield $\mathrm{\parallel }{H}^{\mathrm{\prime }}{\mathrm{\parallel }}_2^2={\sum }_{n\mathrm{\ne }0}4{\pi }^2{n}^2\mathrm{\mid }\widehat{H}(n){\mathrm{\mid }}^2\ge 4{\pi }^2{\sum }_{n\mathrm{\ne }0}\mathrm{\mid }\widehat{H}(n){\mathrm{\mid }}^2=4{\pi }^2\mathrm{\parallel }H{\mathrm{\parallel }}_2^2\mathrm{.}$ Substituting the two norm identities from step 1.1 and dividing by $4{\pi }^2$ proves the claimed bound. Equality holds for $g(x)=\cos (\pi (x-a)\mathrm{/}L)$: its mean is zero, its variance is $1\mathrm{/}2$, and its derivative second moment is ${\pi }^2\mathrm{/}(2L^2)$. Hence the constant $L^2\mathrm{/}{\pi }^2$ is sharp.

Let $f\in L^2(\mu )$. Tonelli applied to $\mathrm{\mid }f{\mathrm{\mid }}^2$ shows that for almost every $x_J$, the section $z\mapsto f(x_J,z)$ is square-integrable on the complementary probability space. Cauchy–Schwarz with the constant function $1$ makes that section integrable, so [F1] defines its average there. If representatives $f$ and $\tilde{f}$ agree almost everywhere, Tonelli applied to $\mathrm{\mid }f-\tilde{f}{\mathrm{\mid }}^2$ shows their sections agree almost everywhere for almost every $x_J$; their averages therefore define the same almost-sure class. Fubini gives measurability of the section-average function.

On almost every section, Cauchy–Schwarz gives $\mathrm{\mid }{P}_{J}f(x_J){\mathrm{\mid }}^2\le \int \mathrm{\mid }f(x_J,z){\mathrm{\mid }}^{2}d{\mu }_{-J}(z)$ because ${\mu }_{-J}$ has mass one. Integrating in $x_J$ and using Tonelli yields $\mathrm{\parallel }{P}_{J}f{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }f{\mathrm{\parallel }}_2^2$, so $P_J$ is a contraction. Averaging a function already independent of $z_{-J}$ leaves it unchanged, hence $P_J^2=P_J$.

For $f,g\in L^2$, Cauchy–Schwarz makes $fg$ integrable. Fubini in the two groups of coordinates gives $⟨P_{J}f,g⟩={\int }_{E_J}(P_{J}f)(P_{J}g)d{\mu }_J=⟨f,P_{J}g⟩$. Thus $P_J$ is self-adjoint.

Applying $P_K$ and then $P_J$ integrates over the coordinates outside $K$, then over the coordinates in $K\setminus J$. Repeated finite-product Fubini permits this order and identifies the iterated integral with integration over the complement of $J\cap K$. The equality holds almost everywhere by [F3], including when either set is empty or full, so $P_J{P}_{K}f=P_{J\cap K}f$ in $L^2$.

Fix $S\subseteq T\subseteq [d]$, and write $m_S=\mathbb{E}[Y\mid {\mathcal{G}}_S]$ and $m_T=\mathbb{E}[Y\mid {\mathcal{G}}_T]$. The subspaces of ${\mathcal{G}}_S$- and ${\mathcal{G}}_T$-measurable $L^2$ functions are nested. For every $h$ in the smaller subspace, $⟨m_T-Y,h⟩=0$ because $h$ also belongs to the larger subspace. Thus $m_T$ and $Y$ have the same orthogonal projection onto the smaller subspace, namely $m_S$, so $m_T-m_S\perp m_S-\mathbb{E}Y$. Pythagoras gives $v(T)-v(S)=\mathrm{\parallel }{m}_T-m_S{\mathrm{\parallel }}_2^2\ge 0$.

For any permutation $\pi$, sum the successive increments $v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi })$ in the order of that permutation. Every intermediate coalition value appears once positively and once negatively, leaving $v([d])-v(\mathrm{\varnothing })$. The projection in [F1] fixes $Y$, so $v([d])=V$; the empty-set projection is constant $\mathbb{E}Y$, so $v(\mathrm{\varnothing })=0$. Step 1.1 gives monotonicity, so these endpoint values imply $0\le v(S)\le V$ for every coalition. Thus the increments sum to $V$.

Each increment in step 2.1 is nonnegative by step 1.1. Average over the finite set of $d!$ permutations and divide by $V>0$. The resulting effects are nonnegative and their sum is $V\mathrm{/}V=1$.

In the procedure [F3], before each entry $i$ of a permutation $\pi$, the current set $S$ is exactly $P_i^{\pi }$: it starts empty and each preceding entry is added once. Thus the increment added to $A_i$ is $v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi })$. There are $d!$ permutations with $d$ entries each, so the loops perform finitely many iterations and at most $2dd!$ exact coalition-value calls; every queried value is available by the stated oracle input. Summing the increments gives $A_i={\sum }_{\pi \in {\mathfrak{S}}_d}(v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi }))$, and division by $d!V$ returns exactly ${\varphi }_i$ by [F2].

Fix $i$ and $S\subseteq [d]\setminus \{i\}$. Exactly $\mathrm{\mid }S\mathrm{\mid }!(d-\mathrm{\mid }S\mathrm{\mid }-1)!$ permutations place precisely $S$ before $i$: order $S$ first, place $i$, and order the remaining coordinates last. Dividing by $d!$ gives the coefficient of $v(S\cup \{i\})-v(S)$ in the expectation of ${\mathrm{\Delta }}_i$. This is exactly the Shapley weight in [F1], so $\mathbb{E}{\mathrm{\Delta }}_i=V{\varphi }_i$ and the estimator is unbiased.

The range and monotonicity of $v$ in [F3] give $0\le {\mathrm{\Delta }}_i\le V$ for every permutation. Thus the increment vector is bounded and has finite covariance. Each increment coordinate and each pairwise product is the same measurable function of each sampled permutation; [F5] gives independence, and the common input law gives identical distributions. Apply [F4] to their coordinate and product sequences; the sample mean and covariance converge almost surely to their population values.

The bounded increment vector satisfies the finite second-moment hypothesis of [F6]. The multivariate CLT gives $\sqrt{n}(\bar{\mathrm{\Delta }}-\mathbb{E}\mathrm{\Delta })\Rightarrow N(0,\mathrm{Cov}(\mathrm{\Delta }))$. Scaling by the fixed positive $V$ and using step 1.1 gives the stated joint limit for $\widehat{\varphi }$. Step 1.2 gives consistency of the covariance and standard-error estimates.

For each of the $n$ rows, the procedure traverses $d$ entries and requests two coalition values per entry. The loops are finite, so it terminates after $n$ rows and makes at most $2nd$ oracle calls. Computing the $d$ sample means and the $d\times d$ sample covariance from these rows takes $O(n{d}^2)$ arithmetic operations; this excludes permutation generation and oracle costs.

Interchange the two finite sums in ${\sum }_{u\subseteq [d]}{f}_u$. The coefficient of $P_{v}f$ is ${\sum }_{u\supseteq v}(-1{)}^{\mathrm{\mid }u\mathrm{\mid }-\mathrm{\mid }v\mathrm{\mid }}=(1-1{)}^{d-\mathrm{\mid }v\mathrm{\mid }}$, which is zero unless $v=[d]$, when it is one. Since $P_{[d]}f=f$, this proves reconstruction.

Fix nonempty $u$ and $i\in u$. Apply $P_{u\setminus \{i\}}$ to the finite sum defining $f_u$. For each $w\subseteq u\setminus \{i\}$, exactly the terms $v=w$ and $v=w\cup \{i\}$ both become $P_{w}f$ by [F2]; their signs are opposite. All terms cancel, so $P_{u\setminus \{i\}}{f}_u=0$. Also $P_u{f}_u=f_u$, since every $v\subseteq u$ satisfies $P_u{P}_v=P_v$. Thus $f_u$ depends only on $u$, and for nonempty $u$ its mean $P_{\mathrm{\varnothing }}{f}_u$ is zero by applying [F2] to the preceding identity.

Let $u\mathrm{\ne }w$. Choose $i$ in their symmetric difference; after interchanging their names if needed, take $i\in u\setminus w$, and put $Q=P_{[d]\setminus \{i\}}$. Since $P_u{f}_u=f_u$, the projection composition rule [F2] and step 2.1 give $Q{f}_u=Q{P}_u{f}_u=P_{u\setminus \{i\}}{f}_u=0$. Since $P_w{f}_w=f_w$ and $i\mathrm{\notin }w$, the same rule gives $Q{f}_w=Q{P}_w{f}_w=P_w{f}_w=f_w$. Self-adjointness of $Q$ therefore gives $⟨f_u,f_w⟩=⟨f_u,Q{f}_w⟩=⟨Q{f}_u,f_w⟩=0$.

By step 1.1, $f-\mathbb{E}f={\sum }_{u\mathrm{\ne }\mathrm{\varnothing }}{f}_u$. Step 3.1 makes this a finite orthogonal sum, so its squared $L^2$ norm is the sum of the squared component norms. Apply [F4] to identify that norm with $\mathrm{Var}(f(X))$.

For a tensor ${\psi }_{\alpha }$ and $J\subseteq [d]$, the product integral defining $P_J{\psi }_{\alpha }$ factors by [F5]. If every nonconstant coordinate of $\alpha$ lies in $J$, every integrated factor is ${\varphi }_{j,0}=1$, so $P_J{\psi }_{\alpha }={\psi }_{\alpha }$. If some $j\mathrm{\notin }J$ has ${\alpha }_j\mathrm{\ne }0$, its factor has mean zero, so $P_J{\psi }_{\alpha }=0$.

Let $F$ be a finite set of multi-indices and $f_F={\sum }_{\alpha \in F}{c}_{\alpha }{\psi }_{\alpha }$. By [F1] and step 1.1, the coefficient of $c_{\alpha }{\psi }_{\alpha }$ in $(f_F{)}_u$ is zero when $\mathrm{supp}(\alpha )\subseteq ̸u$; otherwise it is ${\sum }_{\mathrm{supp}(\alpha )\subseteq v\subseteq u}(-1{)}^{\mathrm{\mid }u\mathrm{\mid }-\mathrm{\mid }v\mathrm{\mid }}=(1-1{)}^{\mathrm{\mid }u\mathrm{\mid }-\mathrm{\mid }\mathrm{supp}(\alpha )\mathrm{\mid }}$. This equals one exactly when $\mathrm{supp}(\alpha )=u$ and zero otherwise. Hence $(f_F{)}_u={\sum }_{\alpha \in F:\mathrm{supp}(\alpha )=u}{c}_{\alpha }{\psi }_{\alpha }$.

By [F4], completeness means the tensor family's closed span is all of $L^2(\mu )$. With [A1], Parseval [F3] gives $f_F\to f$ in $L^2$ as the finite-subset net increases through the tensor family. Each $Q_u:f\mapsto f_u$ is a finite signed sum of contractions $P_v$ by [F2], so $Q_u{f}_F\to Q_{u}f=f_u$ in $L^2$. Orthonormality and step 2.1 give $\mathrm{\parallel }{Q}_u{f}_F{\mathrm{\parallel }}_2^2={\sum }_{\alpha \in F:\mathrm{supp}(\alpha )=u}{c}_{\alpha }^2$. These nondecreasing finite subsums converge to the nonnegative sum over all indices with support $u$; continuity of the norm then yields $V_u={\sum }_{\mathrm{supp}(\alpha )=u}{c}_{\alpha }^2$.

The constant tensor is ${\psi }_0=1$, so the real $L^2$ pairing [F6] gives $c_0=⟨f,1⟩=\mathbb{E}f$. Parseval [F3] applied to $f-c_0$ gives $\mathrm{Var}(f)={\sum }_{\alpha \mathrm{\ne }0}{c}_{\alpha }^2$. Grouping these nonnegative terms by support and substituting the component identities from step 3.1 into [F7] proves both normalized formulas when $V>0$.

Fix $i$. For fixed $x_i$, integrate $f(x_i,x_{-i})f(x_i,x_{-i}^{\mathrm{\prime }})$ over two independent copies of the other coordinates. Fubini [F5] factors this integral as $(P_{\{i\}}f(x_i){)}^2$. Averaging over $x_i$ gives $\mathbb{E}[f(X)f(X^{[i]})]=\mathrm{\parallel }{P}_{\{i\}}f{\mathrm{\parallel }}_2^2$. For a nonconstant ANOVA component with support $u≠\{i\}$, choose $j\in u\setminus \{i\}$ if $i\in u$, or any $j\in u$ otherwise. Dependence gives $P_u{f}_u=f_u$. Hence [F7] gives $P_{\{i\}}{f}_u=P_{\{i\}}{P}_u{f}_u=P_{\{i\}\cap u}{f}_u$ and $P_{\{i\}}{P}_{u\setminus \{j\}}{f}_u=P_{\{i\}\cap (u\setminus \{j\})}{f}_u$. The two index sets are equal by the choice of $j$, so these averages agree; the latter is zero by the coordinate-centering property [F1]. Thus only the constant and singleton components remain, and $P_{\{i\}}f={\mu }_f+f_{\{i\}}$. Orthogonality [F1] gives $\mathrm{\parallel }{P}_{\{i\}}f{\mathrm{\parallel }}_2^2={\mu }_f^2+V_{\{i\}}$, the first-order numerator by [F2]. Subtracting ${\mu }_f^2$ proves the first identity.

Fix $x_{-i}$. The two values $f(X_i,x_{-i})$ and $f(X_i^{\mathrm{\prime }},x_{-i})$ are independent with the same conditional product integral over coordinate $i$. Expanding their squared difference gives half its conditional expectation equal to the variance of that one-coordinate section. Integrating over $x_{-i}$ by Fubini yields $\frac{1}{2}\mathbb{E}[(f(X)-f({\tilde{X}}^{[i]}){)}^2]=\mathrm{\parallel }f-P_{-i}f{\mathrm{\parallel }}_2^2$.

If $i\mathrm{\notin }u$, then $P_{-i}{f}_u=f_u$ because $f_u$ depends only on $X_u$. If $i\in u$, dependence gives $P_u{f}_u=f_u$, and [F7] gives $P_{-i}{f}_u=P_{-i}{P}_u{f}_u=P_{u\setminus \{i\}}{f}_u=0$ by [F1]. Thus $f-P_{-i}f={\sum }_{u\ni i}{f}_u$. Orthogonality [F1] makes its squared norm ${\sum }_{u\ni i}{V}_u$, which is the total-effect numerator by [F2] and proves the second identity.

For $i\mathrm{\notin }u$, [F5] and dependence only on $X_u$ give $P_{-i}{f}_u=f_u$. For $i\in u$, dependence gives $P_u{f}_u=f_u$, so [F6] yields $P_{-i}{f}_u=P_{-i}{P}_u{f}_u=P_{u\setminus \{i\}}{f}_u=0$ by the coordinate-centering property in [F1]. Linearity and reconstruction in [F1] therefore give $f-P_{-i}f={\sum }_{u\ni i}{f}_u$. Orthogonality [F1] and the index definition [F2] give $\mathrm{\parallel }f-P_{-i}f{\mathrm{\parallel }}_2^2={\sum }_{u\ni i}{V}_u=V{S}_{T_i}$.

For almost every $x_{-i}$, apply [F3] to the section of the chosen representative $F$. Its variance is $\int \mathrm{\mid }F-P_{-i}F{\mathrm{\mid }}^{2}d{\mu }_i$, and its derivative moment is $\int \mathrm{\mid }{\mathrm{\partial }}_{i}F{\mathrm{\mid }}^{2}d{\mu }_i$. Integrate the inequality over $x_{-i}$; [F4] justifies the iterated integrals and gives $\mathrm{\parallel }f-P_{-i}f{\mathrm{\parallel }}_2^2\le (L_i^2\mathrm{/}{\pi }^2)\mathbb{E}\mathrm{\mid }{\mathrm{\partial }}_{i}F(X){\mathrm{\mid }}^2$.

Substitute the identity from step 1.1 into step 2.1 and divide by $V>0$. This proves the displayed bound. The same calculation with any valid coordinate constant $C_i$ proves the stated general form.