1 Introduction↩︎

A major limitation of many results in causal inference is that they assume, implicitly or explicitly, IID (independent and identically distributed) observations over a causal system. This limitation is shared by [1], where we derive prediction sets in situations covered by the back-door and front-door criteria [2] (one section of [1] goes beyond the IID picture but only slightly). It was noted in [3] that the limitation can be easily overcome by applying limit theorems of probability theory, but the results there (such as [3]) are asymptotic. In this paper we derive finite-sample confidence intervals in natural non-IID settings.

We start in Sect. 2 by giving definitions of the causal effect adapted to the back-door and front-door criteria. In Sect. 3 we consider the simplest IID setting giving the narrowest confidence intervals. Limitations of this setting are pointed out in, e.g., [3] and [2].

In Sect. 4 we drop the assumption of IID data, which leads to the appearance of an iterated logarithm term in our confidence intervals. This is developed further in Sect. 5; there we make our confidence intervals anytime-valid, which leads to further iterated logarithm terms.

This paper was motivated by the difficulty of applying the methods developed in [1] to the most natural setting of sequential causal inference (which we called the “strong interpretation” of causal diagrams). The methods of this paper are completely different, and we are targeting confidence intervals rather than prediction sets, which were targeted in [1]. In Sect. 6 we briefly discuss derivation of prediction sets from our confidence intervals, but this is likely to lead to much more conservative prediction sets in the IID setting as compared with [1].

Finally, Sect. 7 concludes and lists some directions of further research.

2 Causal effect↩︎

Our running example will be the causal diagram in Figure 1, which we now use to explain our notation (in which we follow mainly Pearl [2]). The variables, such as \(X\), \(Y\), and \(Z\), in our causal diagrams will always range over finite sets denoted by the corresponding boldface letters, such as \(\mathbf{X}\), \(\mathbf{Y}\), and \(\mathbf{Z}\), and called their domains (equipped with the discrete \(\sigma\)-algebras). However, when talking specifically about the example in Figure 1, we will usually assume that \(\mathbf{X}=\mathbf{Y}=\mathbf{Z}=\{0,1\}\), so that \(X,Y,Z\) are the indicator functions of events.

Let \(P\) be a positive probability measure on \(\mathbf{X}\times\mathbf{Y}\times\mathbf{Z}\) (generating the random variables \(X\), \(Y\), and \(Z\)). Suppose it factorizes according to Figure 1: \[\begin{gather} \label{eq:factor} P(X=x,Y=y,Z=z)\\ = P(Z=z) P(X=x\mid Z=z) P(Y=y\mid X=x,Z=z) \end{gather}\tag{1}\] for all \(x\in\mathbf{X}\), \(y\in\mathbf{Y}\), and \(z\in\mathbf{Z}\). It will be very convenient to use Pearl’s [2] convention and abbreviate \(P(X=x)\) to \(P(x)\), \(P(Y=y)\) to \(P(y)\), etc.; such abbreviated notation will also be used when we have, say, \(\tilde{x}\) or \(x'\) in place of \(x\). We will also often omit mentioning that \(x\in\mathbf{X}\), \(y\in\mathbf{Y}\), etc. With this convention, we can rewrite 1 as \[P(x,y,z) = P(z) P(x\mid z) P(y\mid x,z).\]

Let \(\tilde{x}\in\mathbf{X}\). We use Pearl’s [2] notation \(\mathop{\mathrm{do}}(X=\tilde{x})\), usually abbreviated to \(\mathop{\mathrm{do}}(\tilde{x})\), to signify setting \(X\) to \(\tilde{x}\) (we will define what this means formally only in specific contexts). Let us define, in the context of Figure 1, the causal effect of \(X\) on \(Y\) as \[\label{eq:back} P(y\mid\mathop{\mathrm{do}}(\tilde{x})) := \sum_{z} P(y\mid\tilde{x},z) P(z).\tag{2}\] (The definition in [2] is more general, but it is not our focus in this paper and we will use simpler ad hoc definitions.) The interpretation of 2 (and of causal effects in general) is that it is the probability of \(Y=y\) in the mutilated causal model in which the arrow from \(Z\) to \(X\) in Figure 1 has been removed and \(X\) has been set to \(\tilde{x}\).

The decomposition 1 and these notational conventions generalize to any directed acyclic graph (dag), and Figure 1 can be generalized to the following back-door criterion, which is stated in terms of “blocking”, as defined in [2]. If \(X\), \(Y\), and \(Z\) are disjoint non-empty sets of variables in a dag, \(Z\) is said to satisfy the back-door criterion relative to \((X,Y)\) if, for any \(X'\in X\) and \(Y'\in Y\),

• no vertex in \(Z\) is a descendant of \(X'\), and

• \(Z\) blocks every backdoor path from \(X'\) to \(Y'\), i.e., every path between \(X'\) and \(Y'\) that contains an arrow into \(X'\)

[2]. If the back-door criterion is satisfied, the causal effect can still be defined as 2. However, now the summing \(\sum_z\) over \(z\) in 2 means summing over all possible values of the variables in \(Z\): \[\sum_z := \sum_{z_1\in\mathbf{Z}^1} \dots \sum_{z_k\in\mathbf{Z}^k},\] where \(\mathbf{Z}^i\) is the domain of \(Z^i\), \(i=1,\dots,k\), and \(Z^1,\dots,Z^k\) are the elements of \(Z\), \(Z=\{Z^1,\dots,Z^k\}\). Moreover, \(\tilde{x}\) should specify the values for all variables in \(X\). In the theorems below we will use the notation \[\label{eq:Z} \left|\mathbf{Z}\right| := \left|\mathbf{Z}^1\right| \dots \left|\mathbf{Z}^k\right|.\tag{3}\]

Another set of conditions that allows a natural definition of causal effects is known as the front-door criterion. Now let \(X\) and \(Y\) be variables and \(Z\) be a non-empty set of variables not containing \(X\) and \(Y\). Then we say that \(Z\) satisfies the front-door criterion relative to \((X,Y)\) if

• \(Z\) intercepts all directed paths from \(X\) to \(Y\), and

• there is no unblocked backdoor path from \(X\) to \(Z\), and

• all back-door paths from \(Z\) to \(Y\) are blocked by \(X\)

[2]. In this case the causal effect is defined by \[\label{eq:front} P(y\mid\mathop{\mathrm{do}}(\tilde{x})) := \sum_z P(z\mid\tilde{x}) \sum_x P(y\mid x,z) P(x)\tag{4}\] [2].

It is very important (but does not concern us in this paper) that some of the variables in the causal dag may be unobservable; it’s fine as long as these variables do not enter expressions for causal effects, such as 2 or 4 .

3 The IID setting↩︎

We start from the most standard setting where the observations before intervention are IID; see, e.g., [2]. Informally, Nature possesses stable causal mechanisms that are organized in the form of a graphical structure. In causal calculus, the structure is a known dag, and the stable causal mechanisms are unknown probability distributions of the variables in the vertices of the dag given their parents. The available observations are generated in the IID fashion. (The IID nature of the observations usually stays implicit, and it appears that in Pearl’s book [2] it is made explicitly only in [2].)

Figure 2 shows \(N\) repetitions of the causal system represented in Figure 1. Let us ignore the cells labelled \(\text{past}_i\), \(i\in\{1,\dots,N-1\}\), for now (formally, we are assuming that these variables take a fixed known value). This composite causal diagram then represents \(N\) IID observations over the base diagram of Figure 1. In this section we are interested in Figure 2 with an arbitrary dag as the base diagram, not necessarily the one in Figure 1. This IID picture will give the narrowest confidence intervals out of those derived in this paper.

The following theorem treats the case of the back-door criterion, and it is proved (as all other results in this paper) in Appendix 8. A confidence interval \([m-h,m+h]\) will be represented in terms of its midpoint \(m\) and half-width \(h\). The number \(N\) of repetitions is fixed, and we set \[\label{eq:number} \# x y := \left|\{n\in[N]:(X_n,Y_n)=(x,y)\}\right|\tag{5}\] (i.e., \(\# x y\) is the number of times \((X_n,Y_n)=(x,y)\)); the analogous notation will be used for sequences other than \(x y\), such as \(x y z\) and \(z\). See 3 for the definition of \(\left|\mathbf{Z}\right|\).

In the case of Figure 1 with binary variables, we can replace 7 by \[\label{eq:IID-back-2-toy} 2\sqrt{\frac{\ln\frac{6}{\delta}}{2N}} + \sum_{z\in\{0,1\}} \sqrt{\frac{\ln\frac{6}{\delta}}{2\#\tilde{x} z}}\tag{8}\] (although this does not quite follow from 7 ).

The following is the analogue of Theorem 1 for the front-door criterion.

For the same size \(\left|\mathbf{Z}\right|\), the accuracy 10 that we have for the front-door criterion appears much worse than the accuracy 7 for the back-door one.

4 The adaptive setting with a fixed horizon↩︎

Under the strong interpretation of Figure 2, considered in this section, each box \(\text{past}_n\) stands for the whole past, including the variables \(X_i\), \(Y_i\), and \(Z_i\), \(i\in[n]\). Now each \(X_{n+1}\), \(n\in[N-1]\), has incoming arrows (not shown explicitly in the figure) from all \(X_i\), \(Y_i\), and \(Z_i\), \(i\in[n]\). (There is also an intermediate “\(Y\)-oblivious interpretation” considered in [1].) As before, we allow repetition of any dag in Figure 2, not just the one in Figure 1.

Our interpretation of Figure 2 is that \(X\) is a decision that has \(Y\) as its result. The decision at step \(n+1\) may depend on the past decisions and past values of \(Y\) and \(Z\). In other words, the decision maker has access to all past observations. In the case of Figure 1, all \(Z_n\) are independent of the past and identically distributed; all \(Y_n\) have the same distribution given \(X_n\) and \(Z_n\), and they are conditionally independent of the past.

For an integer \(n\ge2\), let \(\llfloor n\rrfloor\) be the largest integer of the form \(2^k\), \(k\in\{1,2,\dots\}\), satisfying \(2^k\le n\) (and for \(n<2\), \(\llfloor n\rrfloor\) is defined as, say, 1). We let \(\mathop{\mathrm{lb}}\) stand for binary logarithm \(\log_2\), and we will often use it in the context of \(\mathop{\mathrm{lb}}\llfloor n\rrfloor=\lfloor\mathop{\mathrm{lb}}n\rfloor\) for a positive integer \(n\).

It will be useful to extend the notation 5 and set, e.g., \[\#_m x y := \left|\{n\in[m]:(X_n,Y_n)=(x,y)\}\right|,\] where \(m\) may be different from \(N\). Earlier we defined standard estimates such as \(\hat{p}(y\mid\tilde{x},z):=\#\tilde{x} y z / \#\tilde{x} z\) (and we will refrain from defining \(\hat{p}\) in other similar contexts in the following theorems). We will also need the modification of \(\hat{p}(y\mid\tilde{x},z)\) defined by \[\label{eq:estimate} \settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}(y\mid\tilde{x},z) := \frac{ \left|\left\{ n\in[N]: \#_n\tilde{x} z \le \llfloor\#\tilde{x} z\rrfloor, X_n=\tilde{x}, Y_n=y, Z_n=z \right\}\right| }{\llfloor\#\tilde{x} z\rrfloor}.\tag{12}\] In words, \(\settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}(y\mid\tilde{x},z)\) is the fraction of the first \(\llfloor\#\tilde{x} z\rrfloor\) observations with \(X_n=\tilde{x}\) and \(Z_n=z\) for which \(Y_n=y\). It is also an estimate of \(P(y\mid\tilde{x},z)\), but it might not use all the available data (however, it uses at least one half of the relevant observations). We will also use the notation \(\settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}\) in other contexts, such as \(\settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}(z\mid\tilde{x})\).

Now we have to replace the Hoeffding inequality used in our proofs of Theorems 1–2 in Appendix 8 by the law of the iterated logarithm, and so we will get our first iterated logarithm term.

The case \(\#\tilde{x} z\in\{0,1\}\) in 14 requires special treatment; namely, we set \(\ln\mathop{\mathrm{lb}}1:=\infty\), and so 14 is interpreted as \(\infty\) unless \(\#\tilde{x} z\ge2\) for all \(z\).

For the binary case of Figure 1, we can replace 14 by \[\label{eq:core-back-2-toy} 2\sqrt{\frac{\ln\frac{6}{\delta}}{2N}} + \sum_{z\in\{0,1\}} \sqrt{\frac{2\ln\mathop{\mathrm{lb}}\llfloor\#\tilde{x} z\rrfloor+\ln\frac{10}{\delta}}{2\llfloor\#\tilde{x} z\rrfloor}},\tag{15}\] similarly to 8 .

5 The anytime-valid adaptive setting↩︎

Theorem 3 can be easily extended to the setting in which the time horizon \(N\) is not fixed in advance. Now we would like our results to be anytime valid, with \(N\) ranging over the positive integers \(\{1,2,\dots\}\). Since \(N\) is variable, now we will write \(\settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}_N(y\mid\tilde{x},z)\) in place of \(\settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}(y\mid\tilde{x},z)\) defined by 12 and add the lower index \(N\) in other similar places; in particular, \(\settoheight{\dhatheight}{\hat{p}} \addtolength{\dhatheight}{-0.35ex} \hat{\vphantom{\rule{1pt}{\dhatheight}} \smash{\hat{p}}}_N(z):=\#_{\llfloor N\rrfloor}z/\llfloor N\rrfloor\). Remember that a \((1-\delta)\)-confidence sequence is a sequence of confidence intervals whose intersection covers the true parameter value with probability at least \(1-\delta\).

In the binary case of Figure 1, 17 can be slightly strengthened to \[2 \sqrt{ \frac{2\ln\mathop{\mathrm{lb}}\llfloor N\rrfloor+\ln\frac{10}{\delta}}{2\llfloor N\rrfloor} } + \sum_{z\in\{0,1\}} \sqrt{ \frac{2\ln\mathop{\mathrm{lb}}\llfloor\#_N\tilde{x} z\rrfloor+\ln\frac{10}{\delta}}{2\llfloor\#_N\tilde{x} z\rrfloor} }.\]

Theorems 3–6 may be considered to be finite-sample analogues of Theorem 1 in [3]. Their characteristic feature is the presence of iterated logarithm terms, which are unavoidable (details omitted) and are especially prominent under the strong interpretation.

6 Applications to prediction intervals↩︎

Theorems 1–6 provide confidence intervals for causal effects, whereas in [1] we were interested in prediction sets for \(Y\). In order to discuss connections between our results here and the strong interpretation in [1], in this section we will state a corollary of the toy version of Theorem 3 for the binary case of Figure 1, with 14 replaced by 15 , giving prediction sets; similar corollaries can be easily deduced from Theorems 1–6 as well. We consider the strong interpretation of Figure 1, as in Sect. 4, with \((X_n,Y_n,Z_n)\), \(n\in[N]\), complemented by another observation \(Y\) with the probabilities of \(Y=y\), \(y\in\mathbf{Y}\), given by the right-hand side of 2 for a fixed \(\tilde{x}\). Remember that \(\mathbf{X}=\mathbf{Y}=\mathbf{Z}=\{0,1\}\).

This procedure is sub-optimal for several reasons. One of them is that Hoeffding’s inequality applied to the Bernoulli model can be greatly improved when the probability of error is small; see, e.g., Vapnik’s [6] use of multiplicative Chernoff inequalities (in what he calls optimistic and pessimistic settings of learning problems).

Analogous corollaries of Theorems 1 and 2 become more comparable with the results that we obtain in [1]. However, the prediction sets derived in [1] are based on e-values (are “e-prediction sets”) whereas the prediction sets here are traditional ones. We expect that methods of this paper lead to much looser results, but their advantage is that they also work for the strong interpretation.

7 Conclusion↩︎

In this paper we derive confidence intervals and confidence sequences for causal effects in IID and sequential non-IID settings. These are some directions of further research:

• The results of this paper only provide upper bounds for achievable widths of confidence intervals, and they need to be complemented by lower bounds. (It is easy to check that a \(\log\log\) term is unavoidable even in the adaptive setting of Figure 1 with \(\mathbf{X}=\mathbf{Y}=\{0,1\}\) and \(\mathbf{Z}=\{0\}\).)

• This paper is based on the standard measure-theoretic probability [7]–[9]. To make our results as strong as possible, we could try and present them in the language of game-theoretic probability [10] (this was listed as direction of further research already in [3]).

8 Proofs↩︎

In the following two propositions we consider an IID Bernoulli sequence \(\xi_1,\xi_2,\dots\) with probability of success \(p\) and use the notation \(\hat{p}_n:=\frac{1}{n}\sum_{i=1}^n\xi_i\) for the standard estimate of \(p\). We start from a standard confidence interval for the probability of success given by Hoeffding’s inequality.

We will also need the following confidence sequence.

Next we need a simple result from interval arithmetic. We are only interested in subintervals of \([0,1]\). Let \(c\pm\Delta c\), where \(c\in\mathbb{R}\) and \(\Delta c\ge0\), stand for the interval \[c\pm\Delta c := [c-\Delta c, c+\Delta c] \cap [0,1].\] For a binary operation \(*\) on the reals (we are mostly interested in addition and multiplication), we define its result on intervals pointwise: \[I_1 \mathbin{*} I_2 := \{p_1\mathbin{*}p_2: p_1\in I_1, p_2\in I_2\} \cap [0,1].\]

If the expression \(E\) in Corollary 2 is written as a multivariate polynomial, then \(m\) is the sum of the degrees of the monomials in \(E\). The number of binary operations in \(E\) is \(m-1\). In this paper we limit ourselves to using multivariate polynomials in expanded form (except for Remark 10 below).

To derive 8 for Figure 1 with binary variables, notice that in the binary case we only need confidence intervals for three constituent probabilities, since an interval estimate for \(P(Z=0)\) gives one for \(P(Z=1)\) and vice versa. This allows us to replace \(\delta\) by \(\delta/3\) rather than \(\delta/4\) in ?? .

In the case of Figure 1 with binary variables, we obtain 15 if we again replace \(\delta\) by \(\delta/3\) rather than \(\delta/4\) (and round up 9.9 to 10).

References↩︎