GPT 6 Astra Ultra attempt on Econ-58
economicsEconomics cataloguecontributionexplorationClaim: exploration
Reported by the author as unresolved.
Manuscript
Contents
- Multiple mediator mechanisms over time without cross-world substitutions: Finite-graph estimation, permutation error, and a rare-path obstruction
- Allocation target
- A finite-state submodel with estimable local kernels
- When the calculation is polynomial
- A statistical lower bound even for a thin graph
- Remaining gap
- References
- Completion Estimate
Multiple mediator mechanisms over time without cross-world substitutions: Finite-graph estimation, permutation error, and a rare-path obstruction
Allocation target
There are $K=JT$ ordered mediator mechanisms. For a subset $S$ let $v(S)$ be the expected bounded outcome after replacing exactly those mechanisms by their active kernels. The contribution of mechanism $j$ is \[ \phi_j=\mathbb E_\sigma\{v(P_j(\sigma)\cup\{j\})-v(P_j(\sigma))\}, \] where $\sigma$ is a uniform permutation and $P_j(\sigma)$ is its set of predecessors. The longitudinal multiple-mediator agenda is described in [agenda, Section 3.4.3]. This allocation convention is the familiar permutation allocation; the results below explicitly account for estimation and permutation approximation. They give sufficient polynomial conditions and a statistical exponential lower bound, not sharp general bounds for every sparse outcome graph.A finite-state submodel with estimable local kernels
Assume the intervention graph has $L$ non-outcome random nodes, alphabets of size at most $B$, and at most $r$ parents per node. Treatments are fixed by the intervention. For this section impose the extra restriction that the terminal conditional mean is a single bounded function of at most $r$ parents. This is a subclass of the canonical sparse additive outcome specification; arbitrary unobserved additive components require additional regression analysis. Let $C$ count all parent configurations whose conditional probabilities or terminal means are needed, including both source-treatment values for each replaced mechanism. Suppose each has observational probability at least $\beta>0$. All variables needed to form these configurations are observed. For example, $C\le(L+1)B^r$ if this count includes all relevant parent values. Observations are $n$ independent complete trajectories. Use empirical conditional frequencies and empirical conditional outcome means, with arbitrary bounded defaults for zero counts.Lemma: For $0<\xi<1$, suppose $n\beta\ge8\log(4C/\xi)$ and put \[
t_n=\sqrt{\frac{4\log(4BC/\xi)}{n\beta}},\quad
d_n=\min\{1,Bt_n/2\},\quad E_n=2Ld_n+t_n.
\] With probability at least $1-\xi$, every hybrid subset satisfies \[
|\widehat v(S)-v(S)|\le E_n. \tag{1}
\]
Proof: For each parent configuration its sample count is binomial with mean at least $n\beta$. The elementary Chernoff lower-tail bound gives probability at most $e^{-n\beta/8}$ that it is less than $n\beta/2$; union bound makes all counts large with failure probability at most $\xi/4$. Given a configuration count, its responses are iid from its conditional law. For each of its at most $B$ categories, Hoeffding's inequality bounds frequency error exceeding $t_n$ by $2e^{-n\beta t_n^2}$. For an outcome in $[-1,1]$, its mean error exceeds $t_n$ with probability at most $2e^{-n\beta t_n^2/4}$. Union over configurations bounds these failures by at most $3\xi/4$ with the displayed constants. Coordinate error $t_n$ implies total variation error at most $d_n$ for every local kernel. Couple the true and estimated hybrid laws in topological order, using maximal coupling whenever all parents agree. At any node the conditional chance of their first disagreement is at most $d_n$. Thus the probability of any disagreement is at most $Ld_n$, independently of which active/reference kernels were chosen. A bounded terminal mean changes expectation by at most twice that probability; its direct estimation error is at most $t_n$. This proves (1) simultaneously for all $2^K$ subsets, without a union bound over those subsets. ∎
Theorem: Independently of the data, draw $M$ uniform permutations and compute \[
\widehat\phi_j=\frac1M\sum_{b=1}^M
[\widehat v(P_j(\sigma_b)\cup\{j\})-\widehat v(P_j(\sigma_b))].
\] With probability at least $1-2\xi$, simultaneously for all $K$ mechanisms, \[
|\widehat\phi_j-\phi_j|
\le2E_n+\sqrt{\frac{8\log(2K/\xi)}{M}}. \tag{2}
\] For every realized set of permutations, $\sum_j\widehat\phi_j=\widehat v(\mathcal J)-\widehat v(\varnothing)$.
Proof: On the event in the lemma, replacing true values by estimated values changes each permutation increment by at most $2E_n$. True increments lie in $[-2,2]$. Across permutations they are iid for each fixed $j$, so Hoeffding gives failure probability at most $2\exp(-Mx^2/8)$ at deviation $x$. Union over $K$ mechanisms gives the second term of (2); independence is required across permutations, not across mechanisms. Intersect this event with the lemma's event. Along each permutation the successive estimated increments telescope from $\widehat v(\varnothing)$ to $\widehat v(\mathcal J)$. Averaging proves the exact sum identity. ∎
The intervals given by (2), intersected with $[-2,2]$, are finite-sample simultaneous confidence intervals under the declared submodel. Their width is informative when $L B\sqrt{\log(BC)/(n\beta)}$ and $\sqrt{\log K/M}$ vanish.When the calculation is polynomial
Suppose the moralized intervention graph, including the outcome factor, has an explicitly supplied elimination ordering of width $w$. For fixed $S$, sum-product elimination computes $\widehat v(S)$ using $O(L B^{w+1})$ arithmetic operations up to the length of the factor list. Indeed eliminating one variable forms a table on it and its remaining neighbors, with at most $w+1$ variables; summing that table removes the variable. Induction over the ordering proves the claimed operation bound. Each permutation needs only $K+1$ consecutive subset values, so the total cost is $O(M(K+1)L B^{w+1})$, in addition to counting observations. For rational input entries, each monomial in this sum-product calculation uses an original factor at most once. A common denominator formed from all input-entry denominators therefore bounds intermediate reduced denominator length by their total input length. The at most $B^L$ monomials add only $O(L\log B)$ further bits beyond the input numerator lengths. Hence rational arithmetic has polynomial bit cost in this bounded-width regime; approximate input arithmetic can also be controlled by the coupling bound. Thus bounded $B,r,w$, polynomial $L,K,\beta^{-1}$, and polynomial $n,M$ give a polynomial sufficient regime. Bounded indegree alone does not imply bounded elimination width. This note does not assert a computational lower bound for every graph with large width.A statistical lower bound even for a thin graph
Proposition: There is a bounded-indegree longitudinal graph with one nonzero mechanism contribution for which, under independent treatment probabilities $\varepsilon$, estimating that contribution has minimax squared risk at least \[
c\min\{1,(n\varepsilon^T)^{-1}\}. \tag{3}
\] The outcome mean has interaction order two, and all hybrid mediator replacements have positive conditional support.
Proof: Take $J=1$ and independent $A_t\sim\operatorname{Ber}(\varepsilon)$. Let $H_t=\prod_{s\le t}A_s$, updated from $H_{t-1},A_t$, so its indegree is two. Earlier mediators have equal active and reference Bernoulli$(1/2)$ kernels and no effects. The final mediator has $P(M_T=1\mid A_T=1)=3/4$ and $P(M_T=1\mid A_T=0)=1/4$, independent of earlier history given $A_T$. Its active and reference kernels are these two probabilities. The intervention fixes all treatments to one. Both mediator values have positive probability at every relevant source history, so mixed-history replacement is supported. Let the terminal Bernoulli mean be $1/2+\theta H_T M_T$, with $|\theta|\le1/4$. This is a bounded sum with interaction order two and indegree two. Under the intervention $H_T=1$, and changing the final mediator kernel changes value by $(3/4-1/4)\theta=\theta/2$. Every other contribution is zero; the final contribution equals $\theta/2$ for every permutation. The laws $\theta=\pm\Delta$ differ only on $H_T=1,M_T=1$, an observational event of probability $(3/4)\varepsilon^T$. Their one-sample KL is at most $C\varepsilon^T\Delta^2$. Take $\Delta=b\min\{1,(n\varepsilon^T)^{-1/2}\}$; small $b$ bounds sample total variation away from one. The two-point squared-error testing argument gives (3). ∎
Remaining gap
The upper bound uses a uniform lower bound on probabilities of parent configurations, and the lower bound explains why such a quantity can be exponentially small even in a simple graph. It does not characterize the optimal risk when only local intervention ratios, rather than configuration probabilities, are controlled. General sparse additive outcomes, weaker overlap, sharp simultaneous widths, and computational necessity conditions remain unresolved. The finite-state proof avoids cross-world substitutions throughout: every value is defined by replacement of observable kernels.References
- [agenda] C. Cinelli, A. Feller, G. Imbens, E. Kennedy, S. Magliacane and J. Zubizarreta. Challenges in Statistics: A Dozen Challenges in Causality and Causal Inference (2025), arXiv:2508.17099v1. https://arxiv.org/html/2508.17099v1.