Paper deep dive
General Probabilities of Causation with Causal Knowledge
Xin Shu, Zhen Lei, Ang Li
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/14/2026, 4:53:10 AM
Summary
This paper extends the theory of Probabilities of Causation (PoCs) from binary to multivalued settings. It derives tighter theoretical bounds for multivalued PoCs (PNS, PSub, PRep, PN) by incorporating causal knowledge encoded in covariates and mediators. The authors show that using causal graphs to impose structural constraints on joint counterfactual distributions yields narrower bounds than existing non-binary methods, demonstrated through theoretical derivations and simulation studies.
Entities (15)
Relation Signals (12)
Probabilities of Causation → includes → PN
confidence 95% · The three basic probabilities of causation are defined below... PN
Probabilities of Causation → includes → PS
confidence 95% · The three basic probabilities of causation are defined below... PS
Probabilities of Causation → includes → PNS
confidence 95% · The three basic probabilities of causation are defined below... PNS
Mediators → usedtotighten → bounds
confidence 95% · incorporating causal information encoded in covariates and mediators... yielding narrower bounds
Covariates → usedtotighten → bounds
confidence 95% · incorporating causal information encoded in covariates and mediators... yielding narrower bounds
Tian and Pearl → derived → bounds for binary PoCs
confidence 90% · Tian and Pearl first derived theoretically sharp bounds for binary PoCs
Back-door criterion → enables → observational data usage
confidence 90% · the back-door adjustment formula gives... yields four new theorems that require only observational data
Shu et al. → extended → PoCs
confidence 90% · Li and Pearl, as well as Shu et al., extended PoCs to multivalued settings
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Probabilities of causation (PoCs) characterize individual causal responses that cannot be directly observed and therefore generally require partial identification. Tian and Pearl first derived theoretically sharp bounds for binary PoCs, including the probability of necessity (PN), the probability of sufficiency (PS), and the probability of necessity and sufficiency (PNS). Mueller et al. subsequently tightened the bounds for binary PNS by incorporating causal information encoded in covariates and mediators. More recently, Li and Pearl, as well as Shu et al., extended PoCs to multivalued settings and derived corresponding theoretical bounds. These developments naturally raise the question of whether additional causal knowledge can further tighten the bounds in multivalued settings. This paper addresses this question by deriving tighter bounds for multivalued PoCs through the incorporation of causal information encoded in covariates and mediators. We illustrate the theoretical results with toy examples, while simulation studies further demonstrate that the proposed bounds are tighter than existing nonbinary bounds.
Tags
Links
- Source: https://arxiv.org/abs/2608.12657v1
- Canonical: https://arxiv.org/abs/2608.12657v1
Trouble viewing inline? Open PDF directly →
Full Text
160,032 characters extracted from source content.
Expand or collapse full text
General Probabilities of Causation with Causal Knowledge Xin Shu Zhen Lei Ang Li Abstract Probabilities of causation (PoCs) characterize individual causal responses that cannot be directly observed and therefore generally require partial identification. Tian and Pearl first derived theoretically sharp bounds for binary PoCs, including the probability of necessity (PN), the probability of sufficiency (PS), and the probability of necessity and sufficiency (PNS). Mueller et al. subsequently tightened the bounds for binary PNS by incorporating causal information encoded in covariates and mediators. More recently, Li and Pearl, as well as Shu et al., extended PoCs to multivalued settings and derived corresponding theoretical bounds. These developments naturally raise the question of whether additional causal knowledge can further tighten the bounds in multivalued settings. This paper addresses this question by deriving tighter bounds for multivalued PoCs through the incorporation of causal information encoded in covariates and mediators. We illustrate the theoretical results with toy examples, while simulation studies further demonstrate that the proposed bounds are tighter than existing nonbinary bounds. Introduction The modern study of probabilities of causation (PoCs) began with 13, who introduced three counterfactual measures of causation for binary treatments and outcomes within the Structural Causal Model (SCM) framework (3; 4): PNPN, PSPS, and PNSPNS. 15 subsequently derived theoretically sharp bounds for these quantities by combining experimental and observational data using Balke’s linear programming framework (1). 6; 8 later applied them to unit-level utility analysis. Although the bounds derived by Tian and Pearl are sharp given the available distributional information, subsequent research has shown that incorporating covariates, mediators, and structural restrictions encoded by causal graphs can yield narrower bounds on probabilities of causation (5; 2; 10). Recent research has extended probabilities of causation to settings with nonbinary treatments and outcomes. 16 and 7 developed numerical methods based on nonlinear programming for computing bounds on nonbinary probabilities of causation. 9 subsequently derived recursive theoretical bounds. More recently, 14 derived closed form bounds by combining experimental and observational data. Despite these advances, whether causal graph information can further tighten the bounds of PoCs in nonbinary settings remains an open question. The answer does not follow immediately from the binary case, because a multivalued PoC involves a joint probability of several potential outcomes and therefore introduces a substantially more complex counterfactual structure. Moreover, the information contributed by an auxiliary variable depends on whether it is a pretreatment covariate, a partial mediator, or a pure mediator. Consider a pharmaceutical company developing a new drug to prevent diabetes, which is increasingly common among younger populations. Its effectiveness can be evaluated using drug-use frequency and diabetes status, both of which may take multiple values. The probability of necessity and sufficiency (PNSPNS) characterizes such individual response patterns by jointly considering the individual’s potential diabetes outcomes under different frequencies of taking the drug. However, such bounds may remain wide (e.g., [0.1,0.9][0.1,0.9]) and therefore be of limited use for decision making if they do not incorporate the causal structure underlying an individual’s response. In practice, additional variables often encode information about this causal structure. For example, lifestyle regularity may influence both the frequency of taking the drug and diabetes status, appetite may partially mediate the effect of the drug, and blood glucose regulation may fully mediate this effect. A causal graph distinguishes these roles and imposes corresponding restrictions on feasible counterfactual response patterns. By incorporating these restrictions together with the available experimental and observational distributions, causal graph information can rule out response patterns that are mathematically possible but structurally incompatible, thereby yielding narrower and more informative PNSPNS bounds. Building on the nonbinary bounds of 14, this paper develops bounds with multivalued treatments and outcomes by incorporating causal graph information. We exploit causal graphs involving non-descendant covariates, including confounders and backdoor adjustment sets (11; 12), as well as partial and pure mediators, to impose structural constraints on the feasible joint counterfactual distributions. For each causal structure, we derive bounds by integrating the available experimental and observational distributions with graph-based constraints on the feasible joint counterfactual distributions. These results extend the use of causal structure from binary to multivalued settings and show when auxiliary variables can exclude structurally incompatible response patterns, thereby tightening existing bounds on individual causal responses. Key Contributions • We extend existing bounds on PoCs that incorporate causal knowledge from the binary to the multivalued setting. Specifically, we derive bounds not only for PNSPNS but also for PSubPSub, PRepPRep, and PNPN for general treatment and outcome settings. Unlike the binary case, the multivalued setting requires characterizing joint counterfactual probabilities across multiple treatment levels, introducing substantial new technical challenges while naturally including the binary setting as a special case. • We derive results for the four representative forms of multivalued PoCs introduced by 14, which are sufficient to represent any discrete PoC. Consequently, the proposed framework immediately applies to a broad class of multivalued PoCs, substantially extending the scope and theoretical impact of incorporating causal knowledge. • We consider multiple causal structures involving covariates that are not descendants of the treatment, covariates satisfying the back-door criterion, partial mediators, and pure mediators. Preliminaries In this section, we review the basic concepts of probabilities of causation (PoC) and the relevant notation used in Structural Causal Models (SCMs) (3; 4). Yx=yY_x=y denotes the counterfactual statement that “variable Y would have the value y had X been set to x.” Here, X denotes the treatment variable, while Y denotes the outcome or effect. For simplicity, we use yxy_x as shorthand for Yx=yY_x=y. Since this paper considers nonbinary settings, we use yjxjy_j_x_j to denote Yxj=yjY_x_j=y_j throughout. In general, P(yjxj)P(y_j_x_j) refers to a probability obtained from experimental data, whereas P(xj,yj)P(x_j,y_j) refers to a probability obtained from observational data. Let X and Y be binary variables in a causal model M. Let x and y denote the events X=trueX=true and Y=trueY=true, respectively, and let x′x and y′y denote the events X=falseX=false and Y=falseY=false, respectively. The three basic probabilities of causation are defined below (13): Definition 1 (Probabilities of Causation). (13) PNS =Δ P(yx,yx′)PN =Δ P(yx′|x,y),PS =Δ P(yx|y′,x′), 3.8889pt -3.8889pt $=$ -3.8889pt -3.28473pt 4.66875pt $ $ -3.28473pt 3.8889ptP(y_x,y _x )PN 3.8889pt -3.8889pt $=$ -3.8889pt -3.28473pt 4.66875pt $ $ -3.28473pt 3.8889ptP(y _x |x,y),PS 3.8889pt -3.8889pt $=$ -3.8889pt -3.28473pt 4.66875pt $ $ -3.28473pt 3.8889ptP(y_x|y ,x ), In the multivalued setting, let the treatment variable X and the outcome variable Y each take n values. PNS(k)=P(y1x1,…,ykxk)PNS(k)=P(y_1_x_1,…,y_k_x_k), where k≤nk≤ n, was first introduced by 9, represents the probability that the same individual would exhibit outcome yjy_j if the treatment were set to xjx_j for every j∈1,…,kj∈\1,…,k\. It therefore characterizes a joint individual causal response across multiple treatment levels. Probability of necessity and sufficiency(k): PNS(k)=P(y1x1,…,ykxk) (k)=P(y_1_x_1,...,y_k_x_k) Probability of substitute(k, p): p≠j for 1≤j≤k of substitute(k, p): p≠ j for 1≤ j≤ k PSub(k,p)=P(y1x1,…,ykxk,xp) (k,p)=P(y_1_x_1,...,y_k_x_k,x_p) Probability of replacement(k, q): PRep(k,q)=P(y1x1,…,ykxk,yq) (k,q)=P(y_1_x_1,...,y_k_x_k,y_q) Probability of necessity(k, p, q): p≠j for 1≤j≤k of necessity(k, p, q): p≠ j for 1≤ j≤ k PN(k,p,q)=P(y1x1,…,ykxk,xp,yq) (k,p,q)=P(y_1_x_1,...,y_k_x_k,x_p,y_q) Later, 14 derived closed-form bounds for nonbinary probabilities of causation. The four main theorems are presented above. Further details, together with the equivalence and replaceability theorems, are omitted here because of space limitations and can be found in 14. In this paper, we derive narrower bounds for these four PoCs by incorporating information from causal graphs involving covariates and mediators. Under the specified graphical conditions, the proposed nonbinary bounds tighten existing bounds. We establish this improvement mathematically and use simulations to demonstrate and quantify the extent of the tightening. Bounds with Causal Diagram In this section, we assume that variables X and Y each take n values, so that |X|=|Y|=n|X|=|Y|=n, with k≤nk≤ n. The generalization was formally established by 14. Proofs of the following theorems are provided in the appendix. For each graphical structure, we derive improved versions of all four existing bounds for multivalued probabilities of causation (PNS(k)PNS(k), PSub(k,p)PSub(k,p), PRep(k,q)PRep(k,q), PN(k,p,q)PN(k,p,q)). Non-descendant Covariates ZZWWXXYY(a) CovariatesZZ and WWZZXXYY(b) Confounder ZZZZXXYY(c) Outcome-affecting Z Figure 1: In all three graphs, Z contains no descendants of X. In graphs (b) and (c), Z additionally satisfies the back-door criterion. Given a causal diagram G, we restrict Z to be a set of variables containing no descendants of X in G. Fig. 1 (a) illustrates such a causal structure. This assumption ensures that Z is not affected by interventions on X and allows the conditional quantity P(yjxj∣z)P(y_j_x_j z) to be measured. Here, unless otherwise specified, j∈1,…,nj∈\1,…,n\ throughout the rest of the paper. Theorem 2. ∑zmax0,∑j=1kP(yjxj∣z)−k+1,For i∈1,…,k:∑1≤j≤kj≠i[P(yjxj∣z)++P(xj∣z)−P(xj,yj∣z)]++P(xi,yi∣z)−k+1×P(z) _z \ array[]c0,\\ \\ _j=1^kP(y_j_x_j z)-k+1,\\ \\ For i∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ i subarray [P(y_j_x_j z)+\\ +P(x_j z)-P(x_j,y_j z) ]+\\ +P(x_i,y_i z)-k+1 array \× P(z) ≤PNS(k) (k) ∑zmin∑j=1kP(xj,yj∣z)++∑j=k+1nP(xj∣z),For j∈1,…,k:P(yjxj∣z),For m∈1,…,k−1,tj∈1,…,k:1m[∑j=0mP(ytjxtj∣z)−P(xtj,ytj∣z)]×P(z) _z \ array[]c _j=1^kP(x_j,y_j z)+\\ + _j=k+1^nP(x_j z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z),\\ \\ For m∈\1,...,k-1\,\\ t_j∈\1,...,k\:\\ 1m [ _j=0^mP(y_t_j_x_t_j z)-\\ -P(x_t_j,y_t_j z) ] array \× P(z) ≥PNS(k) (k) Here, we derive bounds on the conditional z-specific PNS(k)PNS(k) for each possible value z and then take a weighted sum of these stratum-specific bounds to obtain tighter bounds on the PNS(k)PNS(k). Bounds on PSub(k),PRep(k),PN(k)PSub(k),PRep(k),PN(k) can be derived similarly. Theorem 3. p≠jp≠ j for 1≤j≤k1≤ j≤ k, ∑zmax0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xp∣z)−k×P(z) _z \ array[]c0,\\ \\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_p z)-k array \× P(z) ≤PSub(k,p) (k,p) ∑zminP(xp∣z),For j∈1,…,k:P(yjxj∣z)−P(xj,yj∣z)×P(z) _z \ array[]cP(x_p z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z)-P(x_j,y_j z)\\ array \× P(z) ≥PSub(k,p) (k,p) Theorem 4. ∑zmax0,∑j=1k[P(yjxj∣z)++P(xj∣z)−P(xj,yj∣z)]++∑k+1≤j≤nj≠qP(xj,yq∣z)++P(xq,yq∣z)−k,If q∈1,…,k:∑1≤j≤kj≠q[P(yjxj∣z)++P(xj∣z)−P(xj,yj∣z)]++P(xq,yq∣z)−(k−1)×P(z) _z \ array[]c0,\\ \\ _j=1^k [P(y_j_x_j z)+\\ +P(x_j z)-P(x_j,y_j z) ]+\\ + _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z)+\\ +P(x_q,y_q z)-k,\\ \\ If q∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ q subarray [P(y_j_x_j z)+\\ +P(x_j z)-P(x_j,y_j z) ]+\\ +P(x_q,y_q z)-(k-1) array \× P(z) ≤PRep(k,q) (k,q) ∑zminIf q∈1,…,k:P(yqxq∣z),P(xq,yq∣z)++∑k+1≤j≤nj≠qP(xj,yq∣z),For j∈1,…,k, and j≠qP(yjxj∣z)−P(xj,yj∣z),×P(z) _z \ array[]cIf q∈\1,...,k\:\\ P(y_q_x_q z),\\ \\ P(x_q,y_q z)+\\ + _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z),\\ \\ For j∈\1,...,k\, and j≠ q\\ P(y_j_x_j z)-P(x_j,y_j z),\\ array \× P(z) ≥PRep(k,q) (k,q) Theorem 5. p≠jp≠ j for 1≤j≤k1≤ j≤ k, ∑zmax0,∑j=1k[P(yjxj∣z)++P(xj∣z)−P(xj,yj∣z)]++P(xp,yq∣z)−k×P(z) _z \ array[]c0,\\ \\ _j=1^k [P(y_j_x_j z)+\\ +P(x_j z)-P(x_j,y_j z) ]+\\ +P(x_p,y_q z)-k\\ array \× P(z) ≤PN(k,p,q) (k,p,q) ∑zminP(xp,yq∣z),For j∈1,…,k:P(yjxj∣z)−P(xj,yj∣z)×P(z) _z \ array[]cP(x_p,y_q z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z)-P(x_j,y_j z)\\ array \× P(z) ≥PN(k,p,q) (k,p,q) When Z not only contains no descendants of X in G but also satisfies the back-door criterion (11; 12) (Figures 1(b) and 1(c) illustrate two examples of this setting), the back-door adjustment formula gives P(yjxj∣z)=P(yj∣xj,z). P(y_j_x_j z)=P(y_j x_j,z). Substituting this equality into Theorems 2–5 yields four new theorems that require only observational data, without the need for experimental data. For instance, the upper bound of PN(k,p,q) becomes ∑zminP(xp,yq∣z),For j∈1,…,k:P(yj∣xj,z)−P(xj,yj∣z)×P(z) _z \ array[]cP(x_p,y_q z),\\ \\ For j∈\1,...,k\:\\ P(y_j x_j,z)-P(x_j,y_j z)\\ array \× P(z) ≥PN(k,p,q) (k,p,q) Mediation When Z is a descendant of X, the previous results no longer apply. However, under certain mediation structures, information about Z can still tighten the upper bound. UUZZXXYY(a) With direct effectZZXXYY(b) With no direct effect Figure 2: In both graphs, Z is a mediator: (a) with a direct effect and (b) with no direct effect. Partial Mediator In Fig. 2(a), when Z is a mediator and X also has a direct effect on Y, let Z be a set of variables such that ∀xj,xi∈X:xj≠xi,(Yxj⟂X∪Zxi∣Zxj)∀ x_j,x_i∈ X:\ x_j≠ x_i, (Y_x_j \!\!\! X∪ Z_x_i Z_x_j), the lower bound remains unchanged from that of 14, while the upper bound includes an additional term. The proof of the additional term can be found in the appendix. Theorem 6. Let the bounds on PNS(k)PNS(k) given in 14 be denoted by PNSLB≤PNS(k)≤PNSUB. PNS_LB (k)≤PNS_UB. By treating Z as a partial mediator, we can derive a new upper bound on PNS(k)PNS(k) as follows: minPNSUB,For j∈1,…,k:∑z1,…,zk∈1,…,nk[minjP(yj∣xj,zj)×minjP(zjxj)]≥PNS(k) \ array[]cPNS_UB,\\ \\ For j∈\1,…,k\:\\ _ subarraycz_1,...,z_k\\ ∈\1,…,n\^k subarray [ _j\P(y_j x_j,z_j)\×\\ × _j\P(z_j_x_j)\ ] array \ (k) Theorem 7. Given p≠jp≠ j for 1≤j≤k1≤ j≤ k. Let the bounds on PSub(k,p)PSub(k,p) given in 14 be denoted by PSubLB≤PSub(k,p)≤PSubUB. PSub_LB (k,p)≤PSub_UB. By treating Z as a partial mediator, we can derive a new upper bound on PSub(k,p)PSub(k,p) as follows: minPSubUB,For j∈1,…,k:∑z1,…,zk∈1,…,nk[minjP(yj∣xj,zj)×minjP(zjxj),P(xp)] \ array[]cPSub_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1,…,z_k\\ ∈\1,…,n\^k subarray [ _j\P(y_j x_j,z_j)\×\\ × _j\P(z_j_x_j),P(x_p)\ ] array \ ≥PSub(k,p) (k,p) Theorem 8. Let the bounds on PRep(k,q)PRep(k,q) given in 14 be denoted by PRepLB≤PRep(k,q)≤PRepUB. PRep_LB (k,q)≤PRep_UB. By treating Z as a partial mediator, we can derive a new upper bound on PRep(k,q)PRep(k,q) as follows: minPRepUB,For j∈1,…,k:∑z1,…,zk∈1,…,nk[minjP(yj∣xj,zj)×minjP(zjxj)] \ array[]cPRep_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray [ _j\P(y_j x_j,z_j)\×\\ × _j\P(z_j_x_j)\ ] array \ ≥PRep(k,q) (k,q) Theorem 9. Given p≠jp≠ j for 1≤j≤k1≤ j≤ k. Let the bounds on PN(k,p,q)PN(k,p,q) given in 14 be denoted by PNLB≤PN(k,p,q)≤PNUB. PN_LB (k,p,q)≤PN_UB. By treating Z as a partial mediator, we can derive a new upper bound on PN(k,p,q)PN(k,p,q) as follows: minPNUB,For j∈1,…,k:∑z1,…,zk,zp∈1,…,nk+1[minjP(yj∣xj,zj),P(yq∣xp,zp)×minjP(zjxj),P(zpxp),P(xp)] \ array[]cPN_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarray [ _j \ array[]cP(y_j x_j,z_j),\\ P(y_q x_p,z_p) array \×\\ × _j\P(z_j_x_j),P(z_p_x_p),P(x_p)\ ] array \ ≥PN(k,p,q) (k,p,q) Pure Mediator In Figure 2(b), X has no direct effect on Y and affects Y only through the mediator Z. The lower bound remains unchanged from that of 14, while the upper bound includes an additional term using observational quantities involving Z. Theorem 10. Let the bounds on PNS(k)PNS(k) given in 14 be denoted by PNSLB≤PNS(k)≤PNSUB. PNS_LB (k)≤PNS_UB. By treating Z as a pure mediator, we can derive a new upper bound on PNS(k)PNS(k) as follows: minPNSUB,For j∈1,…,k:∑z1≠…≠zk∈1,…,nk[minjP(yj∣zj)×minjP(zj∣xj)]≥PNS(k) \ array[]cPNS_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray [ _j\P(y_j z_j)\×\\ × _j\P(z_j x_j)\ ] array \ (k) Theorem 11. Given p≠jp≠ j for 1≤j≤k1≤ j≤ k. Let the bounds on PSub(k,p)PSub(k,p) given in 14 be denoted by PSubLB≤PSub(k,p)≤PSubUB. PSub_LB (k,p)≤PSub_UB. By treating Z as a pure mediator, we can derive a new upper bound on PSub(k,p)PSub(k,p) as follows: minPSubUB,For j∈1,…,k:∑z1≠…≠zk∈1,…,nk[minjP(yj∣zj)×minjP(zj∣xj)]×P(xp)≥PSub(k,p) \ array[]cPSub_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray [ _j\P(y_j z_j)\×\\ × _j\P(z_j x_j)\ ]× P(x_p) array \ (k,p) Theorem 12. Let the bounds on PRep(k,q)PRep(k,q) given in 14 be denoted by PRepLB≤PRep(k,q)≤PRepUB. PRep_LB (k,q)≤PRep_UB. By treating Z as a pure mediator, we can derive a new upper bound on PRep(k,q)PRep(k,q) as follows: minPRepUB,For j∈1,…,k:∑z1≠…≠zk∈1,…,nk[minjP(yj∣zj)×minjP(zj∣xj)]≥PRep(k,q) \ array[]cPRep_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray [ _j\P(y_j z_j)\×\\ × _j\P(z_j x_j)\ ] array \ (k,q) Theorem 13. Given p≠jp≠ j for 1≤j≤k1≤ j≤ k. Let the bounds on PN(k,p,q)PN(k,p,q) given in 14 be denoted by PNLB≤PN(k,p,q)≤PNUB. PN_LB (k,p,q)≤PN_UB. By treating Z as a pure mediator, we can derive a new upper bound on PN(k,p,q)PN(k,p,q) as follows: minPNUB,For j∈1,…,k:∑z1≠…≠zk≠zp∈1,…,nk+1[minjP(yj∣zj),P(yq∣zp)×minjP(zj∣xj),P(zp∣xp)]×P(xp) \ array[]cPN_UB,\\ \\ For j∈\1,...,k\:\\ _ subarraycz_1≠...≠z_k≠z_p\\ ∈\1,...,n\^k+1 subarray [ _j\P(y_j z_j),P(y_q z_p)\×\\ × _j\P(z_j x_j),P(z_p x_p)\ ]× P(x_p) array \ ≥PN(k,p,q) (k,p,q) Examples In this section, for simplicity, we illustrate only the proposed PNSPNS bounds under different causal structures and focus on three-dimensional cases. Returning to the motivating example introduced in the Introduction, consider the pharmaceutical company that has developed a new drug claimed to help prevent diabetes. To illustrate the proposed bounds under different causal structures, we construct synthetic studies based on this setting. Let X denote how frequently an individual takes the drug, where x1x_1 indicates that the person takes the drug regularly and on time, x2x_2 indicates the person takes the drug occasionally, and x3x_3 indicates the person never takes the drug. Let Y denote the individual’s diabetes status,where y1y_1, y2y_2, and y3y_3 correspond to the person not developing diabetes, developing prediabetes, and developing diabetes, respectively. The target quantity is PNS(3)=P(y1x1,y2x2,y3x3)PNS(3)=P (y_1x_1,y_2x_2,y_3x_3 ), which represents the proportion of individuals who would not develop diabetes if they took the drug regularly and on time, would develop prediabetes if they took it occasionally, and would develop diabetes if they never took it. This target quantity is chosen solely for ease of presentation; any joint counterfactual probability can be analyzed in the same manner using the proposed framework. Family History as a Covariate We now incorporate family history as an observed covariate in the diabetes example. Let Z denote an individual’s family history of diabetes, where z1z_1, z2z_2, and z3z_3 correspond to no known family history of diabetes, diabetes only in a second-degree relative, and diabetes in a first-degree relative, respectively. Individuals with a family history of diabetes may be more likely to develop the disease and may also be more likely to take preventive medication regularly, giving Z→YZ→ Y and Z→XZ→ X. The corresponding causal structure is shown in Figure 1(b). In this setting, Z also satisfies the back-door criterion. Therefore, in Theorem 2, all terms requiring experimental data can be replaced by their corresponding expressions based on observational data, yielding a modified version of the theorem that requires only observational data. The modified theorem is provided in the appendix. To illustrate the calculation, we construct a synthetic study of 900 individuals. The sample was divided into three strata according to the levels of Z. The results are shown in Table 1. Z=z1Z=z_1: No known family history Y X Regular use Occasional use No use Diabetes-free 4646 44 5454 Prediabetes 1212 112112 120120 Diabetes 22 44 66 Z=z2Z=z_2: Second-degree family history only Y X Regular use Occasional use No use Diabetes-free 33 33 22 Prediabetes 7575 2525 22 Diabetes 1212 22 5656 Z=z3Z=z_3: First-degree family history Y X Regular use Occasional use No use Diabetes-free 192192 4444 44 Prediabetes 2424 22 22 Diabetes 2424 1414 5454 Table 1: Results of a drug study stratified by family history. Since Z also satisfies back-door criterion, for j∈1,2,3j∈\1,2,3\, we can compute P(yjxj)=∑zP(yj∣xj,z)×P(z)P(y_j_x_j)= _zP(y_j x_j,z)× P(z). So we can derive P(y1x1)=190/300,P(y2x2)=166/300,P(y3x3)=168/300P(y_1_x_1)=190/300,P(y_2_x_2)=166/300,P(y_3_x_3)=168/300. The company emphasizes that the three interventional probabilities appearing in the target probability of causation, P(y1x1)P(y_1_x_1), P(y2x2)P(y_2_x_2), and P(y3x3)P(y_3_x_3), are all greater than 0.50.5. Based on these marginal probabilities, the company claims that the drug is effective. Applying the bounds on PNS(3)PNS(3) derived by 14 gives 0≤PNS(3)≤0.551.0 (3)≤ 0.551. This interval is too wide to determine whether the drug produces the target response pattern. By additionally incorporating information about family history, we obtain the tighter bounds (the detailed derivation is provided in the appendix): 0≤PNS(3)≤0.033. 0 (3)≤ 0.033. The substantially smaller upper bound indicates that at most 3.3%3.3\% of the population would exhibit the target response pattern. Thus, the company’s marginal comparisons provide limited evidence that the drug has the claimed effect. Blood glucose as a pure mediator As in the previous example, let X and Y denote how frequently an individual takes the drug and the individual’s diabetes status, respectively. A new investigation finds that the drug may affect an individual’s blood glucose level and thereby help prevent the individual from developing diabetes. Accordingly, Let Z denote the individual’s intermediate blood glucose status measured after treatment but before the final diabetes assessment, where z1z_1, z2z_2, and z3z_3 correspond to normal, prediabetic, and diabetic blood glucose levels, respectively. This setting corresponds to the causal structure shown in Figure 2(b). To illustrate the calculation under the pure-mediator structure, we construct a synthetic study of 2,7002,700 individuals. The synthetic observations are grouped according to the three levels of Z, as shown in Table 2. Z=z1Z=z_1: normal blood glucose Y X Regular use Occasional use No use Diabetes-free 448448 304304 1616 Prediabetes 364364 247247 1313 Diabetes 2828 1919 11 Z=z2Z=z_2: prediabetic blood glucose Y X Regular use Occasional use No use Diabetes-free 22 1616 1414 Prediabetes 2727 216216 189189 Diabetes 11 88 77 Z=z3Z=z_3: diabetic blood glucose Y X Regular use Occasional use No use Diabetes-free 66 1818 132132 Prediabetes 33 99 6666 Diabetes 2121 6363 462462 Table 2: Results of a drug study with blood glucose status. Applying the bounds on PNS(3)PNS(3) given by 14, we obtain 0≤PNS(3)≤0.507.0 (3)≤ 0.507. This interval is too wide to provide informative conclusions about the target response pattern. By additionally incorporating information on blood glucose, we obtain the following tighter upper bound using Thm. 10 (details are provided in the appendix): 0≤PNS(3)≤0.151. 0 (3)\ ≤ 0.151. The substantially smaller mediator-improved upper bound provides a substantially more informative characterization of the target response pattern. Simulated Results In this section, we empirically demonstrate that the proposed bounds, which incorporate information from the corresponding causal graphs, are tighter than the bounds derived by 14. In the figures and tables that follow, “Shu et al.” refers to the bounds derived in that work. For simplicity, we focus on PNSPNS to provide a clear visual illustration of the improvement achieved in practice. Figure 3: PNS(3)PNS(3) bounds under the non-descendant structure shown in Fig. 1(a). Figure 4: PNS(3)PNS(3) bounds under the partial mediator structure shown in Fig. 2(a). Figure 5: PNS(3)PNS(3) bounds under the pure mediator structure shown in Fig. 2(b). To illustrate the improvement for individual instances, we consider representative settings with n,k∈3,4,5n,k∈\3,4,5\, chosen for ease of presentation. For each setting, we generate 100,000100,000 sample distributions compatible with the causal diagrams shown in Figures 1(a), 2(a), and 2(b), corresponding to Theorems 2, 6, and 10, respectively, and compute the bounds using both methods. For sample i, let [ai,bi][a_i,b_i] denote the bounds obtained from our theorem and [ci,di][c_i,d_i] those obtained from 14. For each causal diagram, we summarize the following quantities: • Average improvement in the lower bound: ∑(ai−ci)100,000 Σ(a_i-c_i)100,000. • Average improvement in the upper bound: ∑(di−bi)100,000 Σ(d_i-b_i)100,000. • Average width of Shu et al. PNS bounds: ∑(di−ci)100,000 Σ(d_i-c_i)100,000. • Average width of the Theorems 2, 6, and 10: ∑(bi−ai)100,000 Σ(b_i-a_i)100,000. • Count of sample distributions benefiting from tighter bounds: ∑fiΣ f_i, where fi=1f_i=1 if ai>cia_i>c_i or bi<dib_i<d_i, and fi=0f_i=0 otherwise. Avg. LB gain Avg. UB gain Shu et al. width Thms width Improved (%) n=k=3n=k=3 Non-desc. 0.0014 0.0532 0.1953 0.1407 89.08% Part. med. 0 6.52e-06 0.2038 0.2038 0.04% Pure med. 0 0.0583 0.1776 0.1193 83.66% n=k=4n=k=4 Non-desc. 3.78e-07 0.0577 0.1346 0.0769 98.44% Part. med. 0 0 0.1406 0.1406 0% Pure med. 0 0.0137 0.1245 0.1108 36.58% n=k=5n=k=5 Non-desc. 0 0.0557 0.1033 0.0477 99.85% Part. med. 0 0 0.1082 0.1082 0% Pure med. 0 0.0003 0.0973 0.0970 1.26% Table 3: Performance metrics for Theorems 2 (Non-desc.), 6 (Part. med.), and 10 (Pure med.). Here, LB and UB denote the lower and upper bounds, respectively. Table 3 reports these summary statistics across different theorems and dimensions. The partial-mediator structure yields only a small improvement because, as the dimension increases, the proposed bound is tighter than the existing bound in fewer and fewer simulation draws: n=2,k=2 n=2,\ k=2 :8.2% of the bounds are tightened, : 8.2\% of the bounds are tightened, n=3,k=2 n=3,\ k=2 :1.97% of the bounds are tightened, : 1.97\% of the bounds are tightened, n=3,k=3 n=3,\ k=3 :0.035% of the bounds are tightened, : 0.035\% of the bounds are tightened, n=4,k=4 n=4,\ k=4 :0 bounds are tightened in 20M draws. : 0 bounds are tightened in 20M draws. Thus, although the partial-mediator bound remains theoretically valid in higher-dimensional settings, it becomes increasingly unlikely to improve the existing bound in our simulations. Among the causal structures considered, the non-descendant covariate structure provides the most substantial tightening as the dimension increases. In Figures 3 and 5, we randomly select 100100 of the 100,000100,000 sample distributions, plot the bounds obtained with and without incorporating causal graph information, and order the samples according to the upper bounds on PNS(3)PNS(3) given by 14. For Figure 4, because Table 3 shows that Theorem 6 yields narrower bounds less frequently, we continue generating samples until obtaining 100,000100,000 instances for which the bounds are narrowed and then randomly select 100100 of them for visualization. Conclusion In this paper, we extend bounds on probabilities of causation (PoCs) that incorporate causal graph information from binary to multivalued settings. Specifically, we derive new bounds under additional causal graph information for the four representative PoCs, PNSPNS, PSubPSub, PRepPRep, and PNPN, which together could represent any discrete PoC. We consider several causal graph structures, including non-descendant covariates, backdoor adjustment sets, partial mediators, and pure mediators. Toy examples and simulation studies validate the proposed theorems and demonstrate that incorporating causal graph information consistently yields tighter bounds than approaches based solely on experimental and observational distributions. References Balke (1995) A. A. Balke Probabilistic counterfactuals: semantics, computation, and applications. University of California, Los Angeles. Cited by: Introduction. Dawid et al. (2017) A. P. Dawid, M. Musio, and R. Murtas The probability of causation. Law, Probability and Risk 16 (4), p. 163–179. Cited by: Introduction. Galles and Pearl (1998) D. Galles and J. Pearl An axiomatic characterization of causal counterfactuals. Foundations of Science 3 (1), p. 151–182. Cited by: Introduction, Preliminaries. Halpern (2000) J. Y. Halpern Axiomatizing causal reasoning. Journal of Artificial Intelligence Research 12, p. 317–337. Cited by: Introduction, Preliminaries. Kuroki and Cai (2011) M. Kuroki and Z. Cai Statistical analysis of ‘probabilities of causation’using co-variate information. Scandinavian Journal of Statistics 38 (3), p. 564–577. Cited by: Introduction. Li and Pearl (2019) A. Li and J. Pearl Unit selection based on counterfactual logic. In Proceedings of the twenty-eighth international joint conference on artificial intelligence, Cited by: Introduction. Li and Pearl (2022a) A. Li and J. Pearl Bounds on causal effects and application to high dimensional data. In Proceedings of the AAAI conference on artificial intelligence, Vol. 36, p. 5773–5780. Cited by: Introduction. Li and Pearl (2022b) A. Li and J. Pearl Unit selection with causal diagram. In Proceedings of the AAAI conference on artificial intelligence, Vol. 36, p. 5765–5772. Cited by: Introduction. Li and Pearl (2024) A. Li and J. Pearl Probabilities of causation with nonbinary treatment and effect. In Proceedings of the AAAI conference on artificial intelligence, Vol. 38, p. 20465–20472. Cited by: Introduction, Preliminaries. Mueller et al. (2021) S. Mueller, A. Li, and J. Pearl Causes of effects: learning individual responses from population data. External Links: 2104.13730, Link Cited by: Appendix A, Appendix A, Appendix A, Appendix A, Appendix A, Introduction. Pearl (1993) J. Pearl Aspects of graphical models connected with causality. Proceedings of the 49th Session of the International Statistical Institute, Italy, p. 399–401. Cited by: Introduction, Non-descendant Covariates. Pearl (1995) J. Pearl Causal diagrams for empirical research. Biometrika, p. 669–688. Cited by: Introduction, Non-descendant Covariates. Pearl (1999) J. Pearl Probabilities of causation: three counterfactual interpretations and their identification. Synthese 121 (1-2), p. 93. Cited by: Introduction, Preliminaries, Definition 1. Shu et al. (2026) X. Shu, S. Wang, and A. Li Identification of probabilities of causation: from recursive to closed-form bounds. External Links: 2505.15274, Link Cited by: Appendix A, Appendix A, Appendix A, Appendix A, 2nd item, Introduction, Introduction, Preliminaries, Partial Mediator, Pure Mediator, Bounds with Causal Diagram, Family History as a Covariate, Blood glucose as a pure mediator, Simulated Results, Simulated Results, Simulated Results, Theorem 10, Theorem 11, Theorem 12, Theorem 13, Theorem 6, Theorem 7, Theorem 8, Theorem 9. Tian and Pearl (2000) J. Tian and J. Pearl Probabilities of causation: bounds and identification. Annals of Mathematics and Artificial Intelligence 28 (1), p. 287–313. Cited by: Introduction. Zhang et al. (2022) J. Zhang, J. Tian, and E. Bareinboim Partial counterfactual identification from observational and experimental data. In International conference on machine learning, p. 26548–26558. Cited by: Introduction. Appendix A Technical appendices and supplementary material Theorem proofs Proof of Theorem 2 Proof. PNS(k) PNS(k) = = P(y1x1,…,ykxk) P(y_1_x_1,...,y_k_x_k) (1) = = ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) First, we need to prove: max0,∑j=1kP(yjxj∣z)−k+1,For i∈1,…,k:∑1≤j≤kj≠i[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xi,yi∣z)−k+1 \ array[]c0,\\ \\ _j=1^kP(y_j_x_j z)-k+1,\\ \\ For i∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ i subarray [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_i,y_i z)-k+1 array \ ≤P(y1x1,…,ykxk∣z) ≤ P(y_1_x_1,...,y_k_x_k z) min∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj∣z),For j∈1,…,k:P(yjxj∣z),For m∈1,…,k−1,tj∈1,…,k:1m[∑j=0mP(ytjxtj∣z)−P(xtj,ytj∣z)] \ array[]c _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z),\\ \\ For m∈\1,...,k-1\,\\ t_j∈\1,...,k\:\\ 1m [ _j=0^mP(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) ] array \ ≥P(y1x1,…,ykxk∣z) ≥ P(y_1_x_1,...,y_k_x_k z) By the Fréchet Inequalities, for any z with P(z)>0P(z)>0, we have P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) ≥max0,∑j=1kP(yjxj∣z)−k+1 ≥ \0, _j=1^kP(y_j_x_j z)-k+1 \ P(y1x1,…,ykxk∣z)≤min1≤j≤kP(yjxj∣z) P(y_1_x_1,...,y_k_x_k z)≤ _1≤ j≤ k \P(y_j_x_j z) \ The equality of the first lower bound holds when ∃j∈[1,k],that P(yjxj∣z)=0∃ j∈[1,k],that P(y_j_x_j z)=0. The equality of the second lower bound holds when ∃i∈[1,k]∃ i∈[1,k], P(yjxj∣z)=1P(y_j_x_j z)=1 for ∀j∈[1,k],j≠i∀ j∈[1,k],j≠ i. The equality of the second upper bound holds when ∃j∈[1,k]∃ j∈[1,k], P(yixi∣z)=1P(y_i_x_i z)=1 for ∀i∈[1,k]∀ i∈[1,k], i≠ji≠ j. Also, P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) = = ∑j=1nP(y1x1,…,ykxk,xj∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) ≥ ≥ ∑j=1kP(y1x1,…,ykxk,xj∣z) _j=1^kP(y_1_x_1,...,y_k_x_k,x_j z) here, the equal sign holds when ∀xj=0 for , the equal sign holds when ∀x_j=0 for j∈[k+1,n]. j∈[k+1,n]. For ∀i,s.t.,i∈1,…,k∀ i,s.t.,i∈\1,...,k\, ∑j=1kP(y1x1,…,ykxk,xj∣z) _j=1^kP(y_1_x_1,...,y_k_x_k,x_j z) ≥ ≥ P(y1x1,…,ykxk,xi∣z) P(y_1_x_1,...,y_k_x_k,x_i z) here, the equal sign holds when ∀xj=0 for , the equal sign holds when ∀x_j=0 for j∈[1,k] and j≠i. j∈[1,k] and j≠ i. Thus, we have P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) ≥ ≥ P(y1x1,…,ykxk,xi∣z) P(y_1_x_1,...,y_k_x_k,x_i z) = = P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk,xi,yi∣z) P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k,x_i,y_i z) = = P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk,xi,yi∣z) P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k,x_i,y_i z) +∑j=1nP(xj∣z)−1 + _j=1^nP(x_j z)-1 +∑j=1n∑q=1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, + _j=1^n _q=1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxj,yq∣z) x_j,y_q z) −∑j=1n∑q=1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _j=1^n _q=1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxj,yq∣z) x_j,y_q z) = = P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk,xi,yi∣z) P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k,x_i,y_i z) +∑1≤j≤kj≠iP(xj∣z)+P(xi∣z)+∑j=k+1nP(xj∣z) + _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(x_j z)+P(x_i z)+ _j=k+1^nP(x_j z) −1+P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk∣z) -1+P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k z) −∑1≤j≤kj≠iP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) −∑q=1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk,xi, - _q=1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k,x_i, OPENyq∣z) y_q z) −∑j=k+1n∑q=1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…, - _j=k+1^n _q=1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,..., OPENykxk,xj,yq∣z) y_k_x_k,x_j,y_q z) = = P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk∣z)−1 P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k z)-1 +∑1≤j≤kj≠iP(xj∣z) + _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(x_j z) −∑1≤j≤kj≠iP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) +P(xi∣z) +P(x_i z) −∑q=1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _q=1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxi,yq∣z) x_i,y_q z) +P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk,xiCLOSE, +P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k,x_i, OPENyi∣z) y_i z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑q=1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…, - _j=k+1^n _q=1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,..., OPENykxk,xj,yq∣z) y_k_x_k,x_j,y_q z) = = P(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk∣z)−1 P(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k z)-1 +∑1≤j≤kj≠iP(xj∣z) + _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(x_j z) −∑1≤j≤kj≠iP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) +P(xi∣z) +P(x_i z) −∑1≤q≤nq≠iP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _ subarrayc1≤ q≤ n\\ q≠ i subarrayP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxi,yq∣z) x_i,y_q z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1nP(y1x1,…,yi−1xi−1,yi+1xi+1,…,ykxk, - _j=k+1^nP(y_1_x_1,...,y_i-1_x_i-1,y_i+1_x_i+1,...,y_k_x_k, OPENxj∣z) x_j z) By applying the Frechet inequalities, for any z with P(z)>0P(z)>0, we have P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) ≥ ≥ ∑1≤j≤ki≠jP(yjxj∣z)−(k−2)−1 _ subarrayc1≤ j≤ k\\ i≠ j subarrayP(y_j_x_j z)-(k-2)-1 +∑1≤j≤kj≠iP(xj∣z)−∑1≤j≤kj≠iP(xj,yj∣z) + _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(x_j z)- _ subarrayc1≤ j≤ k\\ j≠ i subarrayP(x_j,y_j z) +P(xi∣z)−∑1≤q≤nq≠iP(xi,yq∣z) +P(x_i z)- _ subarrayc1≤ q≤ n\\ q≠ i subarrayP(x_i,y_q z) +∑j=k+1nP(xj∣z)−∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z)- _j=k+1^nP(x_j z) here, the equal sign holds when ∃i∈[1,k], , the equal sign holds when ∃ i∈[1,k], and P(yjxj∣z)=1 for ∀j∈[1,k],j≠i. and P(y_j_x_j z)=1 for ∀ j∈[1,k],j≠ i. = = ∑1≤j≤ki≠j[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _ subarrayc1≤ j≤ k\\ i≠ j subarray [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +P(xi,yi∣z)−k+1 +P(x_i,y_i z)-k+1 To proof the first upper bound, P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) = = ∑j=1nP(y1x1,…,ykxk,xj∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = ∑j=1kP(y1x1,…,ykxk,xj∣z) _j=1^kP(y_1_x_1,...,y_k_x_k,x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) ≤ ≤ ∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj∣z) _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j z) The equality of the first upper bound holds when P(yjxj∣z)=1 for ∀j∈[1,k].P(y_j_x_j z)=1 for ∀ j∈[1,k]. To proof the remaining upper bound, for m∈1,…,k−1m∈\1,...,k-1\, tj∈1,…,kt_j∈\1,...,k\, we can first write P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) (2) = = ∑j=1nP(y1x1,…,ykxk,xj∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = 1m×[(m)∑j=1nP(y1x1,…,ykxk,xj∣z)] 1m× [(m) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] For m=1m=1, 1m[∑j=0mP(ytjxtj∣z)−P(xtj,ytj∣z)] 1m [ _j=0^mP(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) ] = = ∑j=01P(ytjxtj∣z)−P(xtj,ytj∣z) _j=0^1P(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) = = P(yt0xt0∣z)+P(yt1xt1∣z)−P(xt0,yt0∣z) P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z)-P(x_t_0,y_t_0 z) −P(xt1,yt1∣z) -P(x_t_1,y_t_1 z) W.L.O.G., let 1≤t0<t1≤k1≤ t_0<t_1≤ k : P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) = = ∑j=1nP(y1x1,…,ykxk,xj∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = ∑j=1kP(y1x1,…,ykxk,xj∣z) _j=1^kP(y_1_x_1,...,y_k_x_k,x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) ≤ ≤ ∑j=1t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) _j=1^t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) here, the equal sign holds when ∃1≤t0<t1≤k, , the equal sign holds when ∃ 1≤ t_0<t_1≤ k, and P(yixi∣z)=1 for ∀i∈[1,k],i≠t0, and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ t_0, i≠j+t1−t0 for j∈[1,k−t1+t0]. i≠ j+t_1-t_0 for j∈[1,k-t_1+t_0]. = = ∑j=1t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) _j=1^t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) +P(yt0xt0∣z)+P(yt1xt1∣z)−P(xt0,yt0∣z) +P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z)-P(x_t_0,y_t_0 z) −P(xt1,yt1∣z) -P(x_t_1,y_t_1 z) −∑i1,…,it0−1,it0+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit0−1xt0−1, - _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xik+1,yik+2∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) −∑i1,…,it1−1,it1+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit1−1xt1−1, - _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xik+1,yik+2∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +∑i1,…,it0−1,it0+1,…,ik∈1,…,nk−1P(yi1x1,…,yit0−1xt0−1, + _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xt0,yt0∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_t_0,y_t_0 z) +∑i1,…,it1−1,it1+1,…,ik∈1,…,nk−1P(yi1x1,…,yit1−1xt1−1, + _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xt1,yt1∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_t_1,y_t_1 z) = = P(yt0xt0∣z)+P(yt1xt1∣z)−P(xt0,yt0∣z) P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z)-P(x_t_0,y_t_0 z) −P(xt1,yt1∣z) -P(x_t_1,y_t_1 z) +∑j=1t0−1P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=1^t_0-1P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +P(yt0xt0,xt0,yt1xt1∣z) +P(y_t_0_x_t_0,x_t_0,y_t_1_x_t_1 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) −∑i1,…,it0−1,it0+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit0−1xt0−1, - _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xik+1,yik+2∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) −∑i1,…,it1−1,it1+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit1−1xt1−1, - _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xik+1,yik+2∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +∑i1,…,it0−1,it0+1,…,ik∈1,…,nk−1P(yi1x1,…,yit0−1xt0−1, + _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xt0,yt0∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_t_0,y_t_0 z) +∑i1,…,it1−1,it1+1,…,ik∈1,…,nk−1P(yi1x1,…,yit1−1xt1−1, + _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xt1,yt1∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_t_1,y_t_1 z) = = P(yt0xt0∣z)+P(yt1xt1∣z)−P(xt0,yt0∣z) P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z)-P(x_t_0,y_t_0 z) (3) −P(xt1,yt1∣z) -P(x_t_1,y_t_1 z) −∑i1,…,it0−1,it0+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit0−1xt0−1, - _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xik+1,yik+2∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[∑j=1t0−1P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + [ _j=1^t_0-1P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) +∑i1,…,it0−1,it0+1,…,ik∈1,…,nk−1P(yi1x1,…,yit0−1xt0−1, + _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, yt0xt0,yit0+1xt0+1,…,yikxk,xt0,yt0∣z)] y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_t_0,y_t_0 z) ] −∑i1,…,it1−1,it1+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit1−1xt1−1, - _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xik+1,yik+2∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[P(yt0xt0,xt0,yt1xt1∣z) + [P(y_t_0_x_t_0,x_t_0,y_t_1_x_t_1 z) +∑i1,…,it1−1,it1+1,…,ik∈1,…,nk−1P(yi1x1,…,yit1−1xt1−1, + _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, yt1xt1,yit1+1xt1+1,…,yikxk,xt1,yt1∣z)] y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_t_1,y_t_1 z) ] ≤ ≤ P(yt0xt0∣z)+P(yt1xt1∣z)−P(xt0,yt0∣z) P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z)-P(x_t_0,y_t_0 z) −P(xt1,yt1∣z) -P(x_t_1,y_t_1 z) (4) Here, the equal sign holds when ∃1≤t0<t1≤k∃ 1≤ t_0<t_1≤ k, and P(yt0xt0∣z)=0P(y_t_0_x_t_0 z)=0. For m=2m=2, by applying equation (2), we can get: P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) = = 12×[2∑j=1nP(y1x1,…,ykxk,xj∣z)] 12× [2 _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] = = 12×[∑j=1nP(y1x1,…,ykxk,xj∣z) 12× [ _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) +∑j=1nP(y1x1,…,ykxk,xj∣z)] + _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] Then W.L.O.G., let 1≤t0<t1<t2≤k1≤ t_0<t_1<t_2≤ k. By applying equation (3), we have P(y1x1,…,ykxk) P(y_1_x_1,...,y_k_x_k) ≤ ≤ 12×[P(yt0xt0∣z)+P(yt1xt1∣z) 12× \ [P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z) −P(xt0,yt0∣z)−P(xt1,yt1∣z) -P(x_t_0,y_t_0 z)-P(x_t_1,y_t_1 z) −∑i1,…,it0−1,it0+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit0−1xt0−1, - _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xik+1,yik+2∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[∑j=1t0−1P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + [ _j=1^t_0-1P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) +∑i1,…,it0−1,it0+1,…,ik∈1,…,nk−1P(yi1x1,…,yit0−1xt0−1, + _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, yt0xt0,yit0+1xt0+1,…,yikxk,xt0,yt0∣z)] y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_t_0,y_t_0 z) ] −∑i1,…,it1−1,it1+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit1−1xt1−1, - _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xik+1,yik+2∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[P(yt0xt0,xt0,yt1xt1∣z) + [P(y_t_0_x_t_0,x_t_0,y_t_1_x_t_1 z) +∑i1,…,it1−1,it1+1,…,ik∈1,…,nk−1P(yi1x1,…,yit1−1xt1−1, + _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, yt1xt1,yit1+1xt1+1,…,yikxk,xt1,yt1∣z)]] y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_t_1,y_t_1 z) ] ] +[P(yt2xt2∣z)−P(xt2,yt2∣z) + [P(y_t_2_x_t_2 z)-P(x_t_2,y_t_2 z) −∑i1,…,it2−1,it2+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit2−1xt2−1, - _ subarrayc\i_1,...,i_t_2-1,i_t_2+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_2-1_x_t_2-1, OPENyt2xt2,yit2+1xt2+1,…,yikxk,xik+1,yik+2∣z) y_t_2_x_t_2,y_i_t_2+1_x_t_2+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +∑i1,…,it2−1,it2+1,…,ik∈1,…,nk−1P(yi1x1,…,yit2−1xt2−1, + _ subarrayc\i_1,...,i_t_2-1,i_t_2+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_2-1_x_t_2-1, OPENyt2xt2,yit2+1xt2+1,…,yikxk,xt2,yt2∣z) y_t_2_x_t_2,y_i_t_2+1_x_t_2+1,...,y_i_k_x_k,x_t_2,y_t_2 z) +∑1≤j≤kj≠t2P(y1x1,…,ykxk,xj∣z) + _ subarrayc1≤ j≤ k\\ j≠ t_2 subarrayP(y_1_x_1,...,y_k_x_k,x_j z) +P(y1x1,…,yt2−1xt2+1,yt2xt2,yt2+1x+1,…,ykxkCLOSE, +P(y_1_x_1,...,y_t_2-1_x_t_2+1,y_t_2_x_t_2,y_t_2+1_x_+1,...,y_k_x_k, OPENxt2,yt2∣z) x_t_2,y_t_2 z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z)] + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] \ ≤ ≤ 12×[P(yt0xt0∣z)+P(yt1xt1∣z) 12× \ [P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z) −P(xt0,yt0∣z)−P(xt1,yt1∣z) -P(x_t_0,y_t_0 z)-P(x_t_1,y_t_1 z) −∑i1,…,it0−1,it0+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit0−1xt0−1, - _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xik+1,yik+2∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[∑j=1t0−1P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + [ _j=1^t_0-1P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) +∑i1,…,it0−1,it0+1,…,ik∈1,…,nk−1P(yi1x1,…,yit0−1xt0−1, + _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, yt0xt0,yit0+1xt0+1,…,yikxk,xt0,yt0∣z)] y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_t_0,y_t_0 z) ] −∑i1,…,it1−1,it1+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit1−1xt1−1, - _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xik+1,yik+2∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[P(yt0xt0,xt0,yt1xt1∣z) + [P(y_t_0_x_t_0,x_t_0,y_t_1_x_t_1 z) +∑i1,…,it1−1,it1+1,…,ik∈1,…,nk−1P(yi1x1,…,yit1−1xt1−1, + _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, yt1xt1,yit1+1xt1+1,…,yikxk,xt1,yt1∣z)]] y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_t_1,y_t_1 z) ] ] +[P(yt2xt2∣z)−P(xt2,yt2∣z) + [P(y_t_2_x_t_2 z)-P(x_t_2,y_t_2 z) −∑i1,…,it2−1,it2+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit2−1xt2−1, - _ subarrayc\i_1,...,i_t_2-1,i_t_2+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_2-1_x_t_2-1, OPENyt2xt2,yit2+1xt2+1,…,yikxk,xik+1,yik+2∣z) y_t_2_x_t_2,y_i_t_2+1_x_t_2+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +∑i1,…,it2−1,it2+1,…,ik∈1,…,nk−1P(yi1x1,…,yit2−1xt2−1, + _ subarrayc\i_1,...,i_t_2-1,i_t_2+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_2-1_x_t_2-1, OPENyt2xt2,yit2+1xt2+1,…,yikxk,xt2,yt2∣z) y_t_2_x_t_2,y_i_t_2+1_x_t_2+1,...,y_i_k_x_k,x_t_2,y_t_2 z) +∑1≤j≤kj≠t2P(y1x1,…,ykxk,xj∣z) + _ subarrayc1≤ j≤ k\\ j≠ t_2 subarrayP(y_1_x_1,...,y_k_x_k,x_j z) +P(yt1xt1,xt2,yt2xt2∣z) +P(y_t_1_x_t_1,x_t_2,y_t_2_x_t_2 z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z)] + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] \ here, the equal sign holds when ∃1≤t1<t2≤k, , the equal sign holds when ∃ 1≤ t_1<t_2≤ k, ∀P(yjxj∣z)=0 for j∈[1,k],j≠t1. ∀ P(y_j_x_j z)=0 for j∈[1,k],j≠ t_1. = = 12×[P(yt0xt0∣z)+P(yt1xt1∣z) 12× \ [P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z) +P(yt2xt2∣z)−P(xt0,yt0∣z) +P(y_t_2_x_t_2 z)-P(x_t_0,y_t_0 z) −P(xt1,yt1∣z)−P(xt2,yt2∣z) -P(x_t_1,y_t_1 z)-P(x_t_2,y_t_2 z) −∑i1,…,it0−1,it0+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit0−1xt0−1, - _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, OPENyt0xt0,yit0+1xt0+1,…,yikxk,xik+1,yik+2∣z) y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[∑j=1t0−1P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + [ _j=1^t_0-1P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=t0+1k−t1+t0P(yt0xt0,xj,yj+t1−t0xj+t1−t0∣z) + _j=t_0+1^k-t_1+t_0P(y_t_0_x_t_0,x_j,y_j+t_1-t_0_x_j+t_1-t_0 z) +∑j=1t1−t0P(yt0xt0,xk−t1+t0+j,yjxj∣z) + _j=1^t_1-t_0P(y_t_0_x_t_0,x_k-t_1+t_0+j,y_j_x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) +∑i1,…,it0−1,it0+1,…,ik∈1,…,nk−1P(yi1x1,…,yit0−1xt0−1, + _ subarrayc\i_1,...,i_t_0-1,i_t_0+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_0-1_x_t_0-1, yt0xt0,yit0+1xt0+1,…,yikxk,xt0,yt0∣z)] y_t_0_x_t_0,y_i_t_0+1_x_t_0+1,...,y_i_k_x_k,x_t_0,y_t_0 z) ] −∑i1,…,it1−1,it1+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit1−1xt1−1, - _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, OPENyt1xt1,yit1+1xt1+1,…,yikxk,xik+1,yik+2∣z) y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[P(yt0xt0,xt0,yt1xt1∣z) + [P(y_t_0_x_t_0,x_t_0,y_t_1_x_t_1 z) +P(yt1xt1,xt2,yt2xt2∣z) +P(y_t_1_x_t_1,x_t_2,y_t_2_x_t_2 z) +∑i1,…,it1−1,it1+1,…,ik∈1,…,nk−1P(yi1x1,…,yit1−1xt1−1, + _ subarrayc\i_1,...,i_t_1-1,i_t_1+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_1-1_x_t_1-1, yt1xt1,yit1+1xt1+1,…,yikxk,xt1,yt1∣z)]] y_t_1_x_t_1,y_i_t_1+1_x_t_1+1,...,y_i_k_x_k,x_t_1,y_t_1 z) ] ] −∑i1,…,it2−1,it2+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yit2−1xt2−1, - _ subarrayc\i_1,...,i_t_2-1,i_t_2+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_t_2-1_x_t_2-1, OPENyt2xt2,yit2+1xt2+1,…,yikxk,xik+1,yik+2∣z) y_t_2_x_t_2,y_i_t_2+1_x_t_2+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) +[∑i1,…,it2−1,it2+1,…,ik∈1,…,nk−1P(yi1x1,…,yit2−1xt2−1, + [ _ subarrayc\i_1,...,i_t_2-1,i_t_2+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_t_2-1_x_t_2-1, OPENyt2xt2,yit2+1xt2+1,…,yikxk,xt2,yt2∣z) y_t_2_x_t_2,y_i_t_2+1_x_t_2+1,...,y_i_k_x_k,x_t_2,y_t_2 z) +∑1≤j≤kj≠t2P(y1x1,…,ykxk,xj∣z) + _ subarrayc1≤ j≤ k\\ j≠ t_2 subarrayP(y_1_x_1,...,y_k_x_k,x_j z) +∑j=k+1nP(y1x1,…,ykxk,xj∣z)] + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] \ ≤ ≤ 12×[P(yt0xt0∣z)+P(yt1xt1∣z) 12× [P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z) +P(yt2xt2∣z)−P(xt0,yt0∣z) +P(y_t_2_x_t_2 z)-P(x_t_0,y_t_0 z) −P(xt1,yt1∣z)−P(xt2,yt2∣z)] -P(x_t_1,y_t_1 z)-P(x_t_2,y_t_2 z) ] Here, the equal sign holds when ∃1≤t0<t1≤k∃ 1≤ t_0<t_1≤ k, and P(yt0xt0∣z)=P(yt1xt1∣z)=0P(y_t_0_x_t_0 z)=P(y_t_1_x_t_1 z)=0. This is just a sufficient condition illustrating tightness, while the equality can also hold in other cases. For 3≤m≤k−13≤ m≤ k-1, W.L.O.G., let 1≤t0<…<tm≤k1≤ t_0<...<t_m≤ k. By applying equation (2), we can get P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) = = 1m×[∑j=1nP(y1x1,…,ykxk,xj∣z) 1m× [ _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) +(m−1)∑j=1nP(y1x1,…,ykxk,xj∣z)] +(m-1) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] By applying equation (4), we have P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) ≤ ≤ 1m×[P(yt0xt0∣z)+P(yt1xt1∣z) 1m× [P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z) −P(xt0,yt0∣z)−P(xt1,yt1∣z) -P(x_t_0,y_t_0 z)-P(x_t_1,y_t_1 z) +(m−1)∑j=1nP(y1x1,…,ykxk,xj∣z)] +(m-1) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) ] Similar to the proof when m=2m=2, we can derive results for 3≤m≤k−13≤ m≤ k-1: P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k z) ≤ ≤ 1m×[P(yt0xt0∣z)+P(yt1xt1∣z) 1m× [P(y_t_0_x_t_0 z)+P(y_t_1_x_t_1 z) −P(xt0,yt0∣z)−P(xt1,yt1∣z) -P(x_t_0,y_t_0 z)-P(x_t_1,y_t_1 z) +∑j=2m[P(ytjxtj∣z)−P(xtj,ytj∣z)]] + _j=2^m [P(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) ] ] = = 1m×∑j=0m[P(ytjxtj∣z)−P(xtj,ytj∣z)] 1m× _j=0^m [P(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) ] Overall, we have proved the third bound for m∈[1,k−1]m∈[1,k-1]. By substituting max0,∑j=1kP(yjxj∣z)−k+1,For i∈1,…,k:∑1≤j≤kj≠i[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xi,yi∣z)−k+1 \ array[]c0,\\ \\ _j=1^kP(y_j_x_j z)-k+1,\\ \\ For i∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ i subarray [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_i,y_i z)-k+1 array \ ≤P(y1x1,…,ykxk∣z) ≤ P(y_1_x_1,...,y_k_x_k z) min∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj∣z),For j∈1,…,k:P(yjxj∣z),For m∈1,…,k−1,tj∈1,…,k:1m[∑j=0mP(ytjxtj∣z)−P(xtj,ytj∣z)] \ array[]c _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j z),\\ For j∈\1,...,k\:\\ P(y_j_x_j z),\\ \\ For m∈\1,...,k-1\,\\ t_j∈\1,...,k\:\\ 1m [ _j=0^mP(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) ] array \ ≥P(y1x1,…,ykxk∣z) ≥ P(y_1_x_1,...,y_k_x_k z) into equation (1), and applying law of total probability, we have ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) ≥ ≥ ∑z0×P(z) _z0× P(z) = = 0 0 ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) ≥ ≥ ∑z[∑j=1kP(yjxj∣z)−k+1]×P(z) _z [ _j=1^kP(y_j_x_j z)-k+1 ]× P(z) = = ∑j=1kP(yjxj)−k+1 _j=1^kP(y_j_x_j)-k+1 ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) ≥ ≥ ∑z∑1≤j≤kj≠i[P(yjxj∣z)+P(xj∣z) _z \ _ subarrayc1≤ j≤ k\\ j≠ i subarray [P(y_j_x_j z)+P(x_j z) −P(xj,yj∣z)]+P(xi,yi∣z)−k+1×P(z) -P(x_j,y_j z) ]+P(x_i,y_i z)-k+1 \× P(z) = = ∑1≤j≤kj≠i[P(yjxj)+P(xj)−P(xj,yj)] _ subarrayc1≤ j≤ k\\ j≠ i subarray [P(y_j_x_j)+P(x_j)-P(x_j,y_j) ] +P(xi,yi)−k+1 +P(x_i,y_i)-k+1 ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) ≤ ≤ ∑z[∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj∣z)]×P(z) _z [ _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j z) ]× P(z) = = ∑j=1kP(xj,yj)+∑j=k+1nP(xj) _j=1^kP(x_j,y_j)+ _j=k+1^nP(x_j) ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) ≤ ≤ ∑zP(yjxj∣z)×P(z) _zP(y_j_x_j z)× P(z) = = P(yjxj) P(y_j_x_j) ∑zP(y1x1,…,ykxk∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k z)× P(z) ≤ ≤ ∑z1m[∑j=0mP(ytjxtj∣z)−P(xtj,ytj∣z)] _z \ 1m [ _j=0^mP(y_t_j_x_t_j z)-P(x_t_j,y_t_j z) ] \ ×P(z) × P(z) = = 1m[∑j=0mP(ytjxtj)−P(xtj,ytj)] 1m [ _j=0^mP(y_t_j_x_t_j)-P(x_t_j,y_t_j) ] Thus, we can guarantee that the proposed lower and upper bounds are no looser than the lower and upper bounds in 14. Following the notation in 10, P(yjxj∣z)P(y_j_x_j z) denotes experimental data within the subpopulation characterized by z. ∎ Proof of Theorem 3 Proof. PSub(k,p) PSub(k,p) = = P(y1x1,…,ykxk,xp) P(y_1_x_1,...,y_k_x_k,x_p) (5) = = ∑zP(y1x1,…,ykxk,xp∣z) _zP(y_1_x_1,...,y_k_x_k,x_p z) ×P(z) × P(z) First, we need to prove: max0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xp∣z)−k \ array[]c0,\\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_p z)-k array \ ≤P(y1x1,…,ykxk,xp∣z) ≤P(y_1_x_1,...,y_k_x_k,x_p z) minP(xp∣z),For j∈1,…,k:P(yjxj∣z)−P(xj,yj∣z) \ array[]cP(x_p z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z)-P(x_j,y_j z) array \ ≥P(y1x1,…,ykxk,xp∣z) ≥P(y_1_x_1,...,y_k_x_k,x_p z) By the Fréchet Inequalities, for any z with P(z)>0P(z)>0, we can obtain the first lower bound and the first upper bound, P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k,x_p z) ≥ ≥ 0 0 P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k,x_p z) ≤ ≤ P(xp∣z). P(x_p z). The equality of the first lower bound holds when ∃j∈[1,k],that P(yjxj∣z)=0∃ j∈[1,k],that P(y_j_x_j z)=0 or P(xp∣z)=0P(x_p z)=0, p≠jp≠ j. The equality of the first upper bound holds when P(yjxj∣z)=1P(y_j_x_j z)=1 for ∀j∈[1,k]∀ j∈[1,k], j≠pj≠ p. For the second lower bound P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k,x_p z) = = P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k,x_p z) +∑j=1nP(y1x1,…,ykxk,xj∣z) + _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) −∑j=1nP(y1x1,…,ykxk,xj∣z) - _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = P(y1x1,…,ykxk∣z)+P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k z)+P(y_1_x_1,...,y_k_x_k,x_p z) −∑j=1nP(y1x1,…,ykxk,xj∣z) - _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = P(y1x1,…,ykxk∣z)+P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k z)+P(y_1_x_1,...,y_k_x_k,x_p z) +∑j=1nP(xj∣z)−1−∑j=1nP(y1x1,…,ykxk,xj∣z) + _j=1^nP(x_j z)-1- _j=1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +P(y1x1,…,ykxk,xp∣z) +P(y_1_x_1,...,y_k_x_k,x_p z) +∑j=1kP(xj∣z)−∑j=1kP(y1x1,…,ykxk,xj∣z) + _j=1^kP(x_j z)- _j=1^kP(y_1_x_1,...,y_k_x_k,x_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1nP(y1x1,…,ykxk,xj∣z) - _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z) + _j=1^kP(x_j z) −∑j=1kP(y1x1,…,yj−1xj−1,yj+1xj+1,…,ykxk, - _j=1^kP(y_1_x_1,...,y_j-1_x_j-1,y_j+1_x_j+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1nP(y1x1,…,ykxk,xj∣z) - _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j z) +P(y1x1,…,ykxk,xp∣z) +P(y_1_x_1,...,y_k_x_k,x_p z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z) + _j=1^kP(x_j z) −∑j=1kP(y1x1,…,yj−1xj−1,yj+1xj+1,…,ykxk, - _j=1^kP(y_1_x_1,...,y_j-1_x_j-1,y_j+1_x_j+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑k+1≤j≤n,j≠pP(y1x1,…,ykxk,xj∣z) - _ subarrayck+1≤ j≤ n,\\ j≠ p subarrayP(y_1_x_1,...,y_k_x_k,x_j z) ≥ ≥ ∑j=1kP(yjxj∣z)−(k−1)−1+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-(k-1)-1+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj∣z) - _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j z) −∑k+1≤j≤n,j≠pP(xj∣z) - _ subarrayck+1≤ j≤ n,\\ j≠ p subarrayP(x_j z) here, the equal sign holds when ∃j∈[1,n], , the equal sign holds when ∃ j∈[1,n], and P(yixi∣z)=1 for ∀i∈[1,k],i≠j. and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. = = ∑j=1kP(yjxj∣z)−k+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-k+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z)+P(xp∣z) - _j=1^kP(x_j,y_j z)+P(x_p z) = = ∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _j=1^k [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +P(xp∣z)−k +P(x_p z)-k The equality of the second lower bound holds when ∃j∈[1,n],P(yixi∣z)=1 for ∀i∈[1,k],i≠j∃ j∈[1,n],P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. For the remaining upper bounds, ∀j∈[1,k]∀ j∈[1,k]: P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k,x_p z) = = P(y1x1,…,ykxk,xp∣z)+P(yjxj∣z) P(y_1_x_1,...,y_k_x_k,x_p z)+P(y_j_x_j z) −P(yjxj∣z) -P(y_j_x_j z) = = P(y1x1,…,ykxk,xp∣z)+P(yjxj∣z) P(y_1_x_1,...,y_k_x_k,x_p z)+P(y_j_x_j z) −∑i1,…,ij−1,ij+1,…,ik+1∈1,…,nkP(yi1x1,…,yij−1xj−1, - _ subarrayc\i_1,...,i_j-1,i_j+1,...,i_k+1\\\ ∈\1,...,n\^k subarrayP(y_i_1_x_1,...,y_i_j-1_x_j-1, OPENyjxj,yij+1xj+1,…,yikxk,xik+1∣z) y_j_x_j,y_i_j+1_x_j+1,...,y_i_k_x_k,x_i_k+1 z) Since p≠jp≠ j for 1≤j≤k1≤ j≤ k, P(y1x1,…,ykxk,xp∣z) P(y_1_x_1,...,y_k_x_k,x_p z) ≤ ≤ P(yjxj∣z) P(y_j_x_j z) −∑i1,…,ij−1,ij+1,…,ik∈1,…,nk−1P(yi1x1,…,yij−1xj−1,yjxj, - _ subarrayc\i_1,...,i_j-1,i_j+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_j-1_x_j-1,y_j_x_j, OPENyij+1xj+1,…,yikxk,xj∣z) y_i_j+1_x_j+1,...,y_i_k_x_k,x_j z) here, the equal sign holds when P(xj∣z)=0 , the equal sign holds when P(x_j z)=0 for ∀j∈[k+1,n]. for ∀ j∈[k+1,n]. = = P(yjxj∣z)−P(yjxj,xj∣z) P(y_j_x_j z)-P(y_j_x_j,x_j z) = = P(yjxj∣z)−P(xj,yj∣z) P(y_j_x_j z)-P(x_j,y_j z) The equality of the second upper bound holds when P(xj∣z)=0 for ∀j∈[k+1,n]P(x_j z)=0 for ∀ j∈[k+1,n]. By substituting max0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xp∣z)−k \ array[]c0,\\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_p z)-k array \ ≤P(y1x1,…,ykxk,xp∣z) ≤P(y_1_x_1,...,y_k_x_k,x_p z) minP(xp∣z),For j∈1,…,k:P(yjxj∣z)−P(xj,yj∣z) \ array[]cP(x_p z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z)-P(x_j,y_j z) array \ ≥P(y1x1,…,ykxk,xp∣z) ≥P(y_1_x_1,...,y_k_x_k,x_p z) into equation (5), and applying law of total probability, we have ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≥ ≥ ∑z0×P(z) _z0× P(z) = = 0 0 ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≥ ≥ ∑z∑j=1k[P(yjxj∣z)+P(xj∣z) _z \ _j=1^k [P(y_j_x_j z)+P(x_j z) −P(xj,yj∣z)]+P(xp∣z)−k×P(z) -P(x_j,y_j z) ]+P(x_p z)-k \× P(z) = = ∑j=1k[P(yjxj)+P(xj)−P(xj,yj)] _j=1^k [P(y_j_x_j)+P(x_j)-P(x_j,y_j) ] +P(xp)−k +P(x_p)-k ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≤ ≤ P(xp∣z)×P(z) P(x_p z)× P(z) = = P(xp) P(x_p) ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≤ ≤ [P(yjxj∣z)−P(xj,yj∣z)]×P(z) [P(y_j_x_j z)-P(x_j,y_j z) ]× P(z) = = P(yjxj)−P(xj,yj) P(y_j_x_j)-P(x_j,y_j) Thus, we can guarantee that the proposed lower and upper bounds are no looser than those of 14. Following the notation in 10, P(yjxj∣z)P(y_j_x_j z) denotes experimental data within the subpopulation characterized by z. ∎ Proof of Theorem 4 Proof. PRep(k,q) PRep(k,q) = = P(y1x1,…,ykxk,yq) P(y_1_x_1,...,y_k_x_k,y_q) (6) = = ∑zP(y1x1,…,ykxk,yq∣z) _zP(y_1_x_1,...,y_k_x_k,y_q z) ×P(z) × P(z) First, we need to prove: max0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+∑k+1≤j≤nj≠qP(xj,yq∣z)++P(xq,yq∣z)−k,If q∈1,…,k:∑1≤j≤kj≠q[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xq,yq∣z)−(k−1) \ array[]c0,\\ \\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z)+\\ +P(x_q,y_q z)-k,\\ \\ If q∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ q subarray [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_q,y_q z)-(k-1) array \ ≤P(y1x1,…,ykxk,yq∣z) ≤ P(y_1_x_1,...,y_k_x_k,y_q z) minIf q∈1,…,k:P(yqxq∣z),P(xq,yq∣z)+∑k+1≤j≤nj≠qP(xj,yq∣z),For j∈1,…,k, and j≠qP(yjxj∣z)−P(xj,yj∣z), \ array[]cIf q∈\1,...,k\:\\ P(y_q_x_q z),\\ \\ P(x_q,y_q z)+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z),\\ \\ For j∈\1,...,k\, and j≠ q\\ P(y_j_x_j z)-P(x_j,y_j z),\\ array \ ≥P(y1x1,…,ykxk,yq∣z) ≥ P(y_1_x_1,...,y_k_x_k,y_q z) By the Fréchet Inequalities, for any z with P(z)>0P(z)>0, we can obtain the first lower bound and the first upper bound, P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) ≥ ≥ 0 0 P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) ≤ ≤ P(yqxq∣z),∀1≤q≤k. P(y_q_x_q z),∀ 1≤ q≤ k. The equality of the first lower bound holds when ∃j∈[1,k],that P(yjxj∣z)=0∃ j∈[1,k],that P(y_j_x_j z)=0 or P(yq∣z)=0P(y_q z)=0. The equality of the first upper bound holds when P(yjxj∣z)=1,P(yq∣z)=1P(y_j_x_j z)=1,P(y_q z)=1 for ∀j∈[1,k],j≠q∀ j∈[1,k],j≠ q. For the second lower bound P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = P(y1x1,…,ykxk,yq∣z)+P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k,y_q z)+P(y_1_x_1,...,y_k_x_k z) −∑j=1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) = = P(y1x1,…,ykxk,yq∣z)+P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k,y_q z)+P(y_1_x_1,...,y_k_x_k z) −∑j=1kP(y1x1,…,ykxk,xj,yj∣z) - _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) = = P(y1x1,…,ykxk,yq∣z)+P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k,y_q z)+P(y_1_x_1,...,y_k_x_k z) +∑j=1nP(xj∣z)−1 + _j=1^nP(x_j z)-1 −∑j=1kP(y1x1,…,ykxk,xj,yj∣z) - _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) = = ∑j=1nP(y1x1,…,ykxk,xj,yq∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) +P(y1x1,…,ykxk∣z)−1 +P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z)−∑j=1kP(y1x1,…,ykxk,xj,yj∣z) + _j=1^kP(x_j z)- _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) If q∈[1,k]q∈[1,k], P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z)−∑j=1kP(y1x1,…,ykxk,xj,yj∣z) + _j=1^kP(x_j z)- _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +P(y1x1,…,ykxk,xq,yq∣z)+∑j=k+1nP(xj∣z) +P(y_1_x_1,...,y_k_x_k,x_q,y_q z)+ _j=k+1^nP(x_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z) + _j=1^kP(x_j z) −∑1≤j≤k,j≠qP(y1x1,…,ykxk,xj,yj∣z) - _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑1≤l≤n,l≠qP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(y_1_x_1,...,y_k_x_k,x_j,y_l z) ≥ ≥ ∑j=1kP(yjxj∣z)−(k−1)−1 _j=1^kP(y_j_x_j z)-(k-1)-1 +∑j=1kP(xj∣z)−∑1≤j≤k,j≠qP(xj,yj∣z) + _j=1^kP(x_j z)- _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(x_j,y_j z) +∑j=k+1nP(xj∣z)−∑j=k+1n∑1≤l≤n,l≠qP(xj,yl∣z) + _j=k+1^nP(x_j z)- _j=k+1^n _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(x_j,y_l z) here, the equal sign holds when ∃j∈[1,n], , the equal sign holds when ∃ j∈[1,n], and P(yixi∣z)=1 for ∀i∈[1,k],i≠j. and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. = = ∑j=1kP(yjxj∣z)−k+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-k+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z)+P(xq,yq∣z) - _j=1^kP(x_j,y_j z)+P(x_q,y_q z) +∑j=k+1nP(xj,yq∣z) + _j=k+1^nP(x_j,y_q z) = = ∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _j=1^k [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +∑k+1≤j≤n,j≠qP(xj,yq∣z)+P(xq,yq∣z)−k + _ subarrayck+1≤ j≤ n,\\ j≠ q subarrayP(x_j,y_q z)+P(x_q,y_q z)-k If q∈[k+1,n]q∈[k+1,n], P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = P(y1x1,…,ykxk∣z)−1+∑j=1kP(xj∣z) P(y_1_x_1,...,y_k_x_k z)-1+ _j=1^kP(x_j z) −∑j=1kP(y1x1,…,ykxk,xj,yj∣z) - _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) = = P(y1x1,…,ykxk∣z)−1+∑j=1kP(xj∣z) P(y_1_x_1,...,y_k_x_k z)-1+ _j=1^kP(x_j z) −∑j=1kP(y1x1,…,ykxk,xj,yj∣z) - _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑1≤l≤n,l≠qP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(y_1_x_1,...,y_k_x_k,x_j,y_l z) ≥ ≥ ∑j=1kP(yjxj∣z)−(k−1)−1+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-(k-1)-1+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z) - _j=1^kP(x_j,y_j z) +∑j=k+1nP(xj∣z)−∑j=k+1n∑1≤l≤n,l≠qP(xj,yl∣z) + _j=k+1^nP(x_j z)- _j=k+1^n _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(x_j,y_l z) here, the equal sign holds when ∃j∈[1,n], , the equal sign holds when ∃ j∈[1,n], and P(yixi∣z)=1 for ∀i∈[1,k],i≠j. and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. = = ∑j=1kP(yjxj∣z)−k+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-k+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj,yq∣z) - _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j,y_q z) = = ∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _j=1^k [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +∑k+1≤j≤n,j≠qP(xj,yq∣z)+P(xq,yq∣z)−k + _ subarrayck+1≤ j≤ n,\\ j≠ q subarrayP(x_j,y_q z)+P(x_q,y_q z)-k To summarize P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) ≥ ≥ ∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _j=1^k [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +∑k+1≤j≤nj≠qP(xj,yq∣z)+P(xq,yq∣z)−k + _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z)+P(x_q,y_q z)-k and the equality of the second lower bound holds when ∃j∈[1,n], and P(yixi∣z)=1 for ∀i∈[1,k],i≠j∃ j∈[1,n], and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. For the third lower bound, if 1≤q≤k1≤ q≤ k P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = ∑j=1nP(y1x1,…,ykxk,xj,yq∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) = = P(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk,xq,yq∣z) P(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k,x_q,y_q z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) = = P(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk,xq,yq∣z) P(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k,x_q,y_q z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) +P(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk∣z) +P(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k z) −∑j=1n∑l=1nP(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk, - _j=1^n _l=1^nP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k, OPENxj,yl∣z) x_j,y_l z) +∑j=1nP(xj∣z)−1 + _j=1^nP(x_j z)-1 = = P(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk∣z)−1 P(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z) + _j=1^kP(x_j z) −∑1≤j≤k,j≠qP(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk, - _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) −∑l=1nP(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk, - _l=1^nP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k, OPENxq,yl∣z) x_q,y_l z) +P(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk,xqCLOSE, +P(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k,x_q, OPENyq∣z) y_q z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑l=1nP(y1x1,…,yq−1xq−1,yq+1xq+1,…, - _j=k+1^n _l=1^nP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,..., OPENykxk,xj,yl∣z) y_k_x_k,x_j,y_l z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) = = P(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk∣z)−1 P(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z) + _j=1^kP(x_j z) −∑1≤j≤k,j≠qP(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk, - _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k, OPENxj,yj∣z) x_j,y_j z) −∑1≤l≤n,l≠qP(y1x1,…,yq−1xq−1,yq+1xq+1,…,ykxk, - _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,...,y_k_x_k, OPENxq,yl∣z) x_q,y_l z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑1≤l≤n,l≠qP(y1x1,…,yq−1xq−1,yq+1xq+1,…, - _j=k+1^n _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(y_1_x_1,...,y_q-1_x_q-1,y_q+1_x_q+1,..., OPENykxk,xj,yl∣z) y_k_x_k,x_j,y_l z) ≥ ≥ ∑1≤j≤k,j≠qP(yjxj∣z)−(k−2)−1 _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(y_j_x_j z)-(k-2)-1 +∑j=1kP(xj∣z)−∑1≤j≤k,j≠qP(xj,yj∣z) + _j=1^kP(x_j z)- _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(x_j,y_j z) −∑1≤l≤n,l≠qP(xq,yl∣z)+∑j=k+1nP(xj∣z) - _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(x_q,y_l z)+ _j=k+1^nP(x_j z) −∑j=k+1n∑1≤l≤n,l≠qP(xj,yl∣z) - _j=k+1^n _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(x_j,y_l z) here, the equal sign holds when ∃q∈[1,k], , the equal sign holds when ∃ q∈[1,k], and P(yixi∣z)=1 for ∀i∈[1,k],i≠q. and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ q. = = ∑1≤j≤k,j≠qP(yjxj∣z)−(k−1) _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(y_j_x_j z)-(k-1) +∑1≤j≤k,j≠qP(xj∣z)+P(xq∣z) + _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(x_j z)+P(x_q z) −∑1≤j≤k,j≠qP(xj,yj∣z)−∑1≤l≤n,l≠qP(xq,yl∣z) - _ subarrayc1≤ j≤ k,\\ j≠ q subarrayP(x_j,y_j z)- _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(x_q,y_l z) +∑j=k+1nP(xj,yq∣z) + _j=k+1^nP(x_j,y_q z) = = ∑1≤j≤k,j≠q[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _ subarrayc1≤ j≤ k,\\ j≠ q subarray [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] −(k−1)+P(xq∣z)−∑1≤l≤n,l≠qP(xq,yl∣z) -(k-1)+P(x_q z)- _ subarrayc1≤ l≤ n,\\ l≠ q subarrayP(x_q,y_l z) +∑j=k+1nP(xj,yq∣z) + _j=k+1^nP(x_j,y_q z) = = ∑1≤j≤k,j≠q[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _ subarrayc1≤ j≤ k,\\ j≠ q subarray [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] −(k−1)+P(xq,yq∣z)+∑j=k+1nP(xj,yq∣z) -(k-1)+P(x_q,y_q z)+ _j=k+1^nP(x_j,y_q z) ≥ ≥ ∑1≤j≤k,j≠q[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _ subarrayc1≤ j≤ k,\\ j≠ q subarray [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +P(xq,yq∣z)−(k−1) +P(x_q,y_q z)-(k-1) here, the equal sign holds when P(xj∣z)=0 , the equal sign holds when P(x_j z)=0 for ∀j∈[k+1,n]. for ∀ j∈[k+1,n]. The equality of the third upper bound holds when ∃q∈[1,k], and P(yixi∣z)=1,P(xj∣z)=0 for ∀i∈[1,k],j∈[k+1,n],i≠q∃ q∈[1,k], and P(y_i_x_i z)=1,P(x_j z)=0 for ∀ i∈[1,k],j∈[k+1,n],i≠ q. For the second upper bound P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = ∑j=1nP(y1x1,…,ykxk,xj,yq∣z) _j=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) = = ∑j=1kP(y1x1,…,ykxk,xj,yq∣z) _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_q z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) If q∈[1,k]q∈[1,k], P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = P(y1x1,…,ykxk,xq,yq∣z) P(y_1_x_1,...,y_k_x_k,x_q,y_q z) +∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) + _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) ≤ ≤ P(xq,yq∣z)+∑j=k+1nP(xj,yq∣z) P(x_q,y_q z)+ _j=k+1^nP(x_j,y_q z) here, the equal sign holds when P(yixi∣z)=1 , the equal sign holds when P(y_i_x_i z)=1 for ∀i∈[1,k]. for ∀ i∈[1,k]. = = P(xq,yq∣z)+∑k+1≤j≤n,j≠qP(xj,yq∣z) P(x_q,y_q z)+ _ subarrayck+1≤ j≤ n,\\ j≠ q subarrayP(x_j,y_q z) If q∈[k+1,n]q∈[k+1,n], P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = ∑j=k+1nP(y1x1,…,ykxk,xj,yq∣z) _j=k+1^nP(y_1_x_1,...,y_k_x_k,x_j,y_q z) ≤ ≤ ∑j=k+1nP(xj,yq∣z) _j=k+1^nP(x_j,y_q z) here, the equal sign holds when P(yixi∣z)=1 , the equal sign holds when P(y_i_x_i z)=1 for ∀i∈[1,k]. for ∀ i∈[1,k]. = = P(xq,yq∣z)+∑k+1≤j≤n,j≠qP(xj,yq∣z) P(x_q,y_q z)+ _ subarrayck+1≤ j≤ n,\\ j≠ q subarrayP(x_j,y_q z) To summarize P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) ≤ ≤ P(xq,yq∣z)+∑k+1≤j≤nj≠qP(xj,yq∣z) P(x_q,y_q z)+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z) and the equality of the second upper bound holds when P(yixi∣z)=1 for ∀i∈[1,k]P(y_i_x_i z)=1 for ∀ i∈[1,k]. For the remaining upper bounds, ∀j∈[1,k]∀ j∈[1,k]: P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) = = ∑i=1nP(y1x1,…,ykxk,xi,yq∣z)+P(yjxj∣z) _i=1^nP(y_1_x_1,...,y_k_x_k,x_i,y_q z)+P(y_j_x_j z) −P(yjxj∣z) -P(y_j_x_j z) = = ∑i=1nP(y1x1,…,ykxk,xi,yq∣z)+P(yjxj∣z) _i=1^nP(y_1_x_1,...,y_k_x_k,x_i,y_q z)+P(y_j_x_j z) −∑i1,…,ij−1,ij+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yij−1xj−1, - _ subarrayc\i_1,...,i_j-1,i_j+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_j-1_x_j-1, OPENyjxj,yij+1xj+1,…,yikxk,xik+1,yik+2∣z) y_j_x_j,y_i_j+1_x_j+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) Since q≠jq≠ j for 1≤j≤k1≤ j≤ k, P(y1x1,…,ykxk,yq∣z) P(y_1_x_1,...,y_k_x_k,y_q z) ≤ ≤ P(yjxj∣z) P(y_j_x_j z) −∑i1,…,ij−1,ij+1,…,ik∈1,…,nk−1P(yi1x1,…,yij−1xj−1,yjxj, - _ subarrayc\i_1,...,i_j-1,i_j+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,...,y_i_j-1_x_j-1,y_j_x_j, OPENyij+1xj+1,…,yikxk,xj,yj∣z) y_i_j+1_x_j+1,...,y_i_k_x_k,x_j,y_j z) here, the equal sign holds when P(xj∣z)=0, , the equal sign holds when P(x_j z)=0, P(yj∣z)=0 and P(xt1,yt2∣z)=0 P(y_j z)=0 and P(x_t_1,y_t_2 z)=0 for ∀j∈[k+1,n],∀t1,t2∈[1,k] and t1≠t2. for ∀ j∈[k+1,n],∀ t_1,t_2∈[1,k] and t_1≠ t_2. = = P(yjxj∣z)−P(yjxj,xj,yj∣z) P(y_j_x_j z)-P(y_j_x_j,x_j,y_j z) = = P(yjxj∣z)−P(xj,yj∣z) P(y_j_x_j z)-P(x_j,y_j z) The equality of the third upper bound holds when P(xj∣z)=0,P(yj∣z)=0 and P(xt1,yt2∣z)=0 for ∀j∈[k+1,n],t1,t2∈[1,k] and t1≠t2P(x_j z)=0,P(y_j z)=0 and P(x_t_1,y_t_2 z)=0 for ∀ j∈[k+1,n],t_1,t_2∈[1,k] and t_1≠ t_2. By substituting max0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+∑k+1≤j≤nj≠qP(xj,yq∣z)++P(xq,yq∣z)−k,If q∈1,…,k:∑1≤j≤kj≠q[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xq,yq∣z)−(k−1) \ array[]c0,\\ \\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z)+\\ +P(x_q,y_q z)-k,\\ \\ If q∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ q subarray [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_q,y_q z)-(k-1) array \ ≤P(y1x1,…,ykxk,yq∣z) ≤ P(y_1_x_1,...,y_k_x_k,y_q z) minIf q∈1,…,k:P(yqxq∣z),P(xq,yq∣z)+∑k+1≤j≤nj≠qP(xj,yq∣z),For j∈1,…,k, and j≠qP(yjxj∣z)−P(xj,yj∣z), \ array[]cIf q∈\1,...,k\:\\ P(y_q_x_q z),\\ \\ P(x_q,y_q z)+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z),\\ \\ For j∈\1,...,k\, and j≠ q\\ P(y_j_x_j z)-P(x_j,y_j z),\\ array \ ≥P(y1x1,…,ykxk,yq∣z) ≥ P(y_1_x_1,...,y_k_x_k,y_q z) into equation (6), and applying law of total probability, we have ∑zP(y1x1,…,ykxk,yq∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,y_q z)× P(z) ≥ ≥ ∑z0×P(z) _z0× P(z) = = 0 0 ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≥ ≥ ∑z∑j=1k[P(yjxj∣z)+P(xj∣z) _z \ _j=1^k [P(y_j_x_j z)+P(x_j z) −P(xj,yj∣z)]+∑k+1≤j≤nj≠qP(xj,yq∣z) -P(x_j,y_j z) ]+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z) +P(xq,yq∣z)−k×P(z) +P(x_q,y_q z)-k \× P(z) = = ∑j=1k[P(yjxj)+P(xj)−P(xj,yj)] _j=1^k [P(y_j_x_j)+P(x_j)-P(x_j,y_j) ] +∑k+1≤j≤nj≠qP(xj,yq)+P(xq,yq)−k + _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q)+P(x_q,y_q)-k ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≥ ≥ ∑z∑1≤j≤kj≠q[P(yjxj∣z)+P(xj∣z) _z \ _ subarrayc1≤ j≤ k\\ j≠ q subarray [P(y_j_x_j z)+P(x_j z) −P(xj,yj∣z)]+P(xq,yq∣z)−(k−1) -P(x_j,y_j z) ]+P(x_q,y_q z)-(k-1) \ ×P(z) × P(z) = = ∑1≤j≤kj≠q[P(yjxj)+P(xj)−P(xj,yj)] _ subarrayc1≤ j≤ k\\ j≠ q subarray [P(y_j_x_j)+P(x_j)-P(x_j,y_j) ] +P(xq,yq)−(k−1) +P(x_q,y_q)-(k-1) ∑zP(y1x1,…,ykxk,yq∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,y_q z)× P(z) ≤ ≤ ∑zP(yqxq∣z)×P(z) _zP(y_q_x_q z)× P(z) = = P(yqxq) P(y_q_x_q) ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≤ ≤ ∑z[P(xq,yq∣z)+∑k+1≤j≤nj≠qP(xj,yq∣z)] _z [P(x_q,y_q z)+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q z) ] ×P(z) × P(z) = = P(xq,yq)+∑k+1≤j≤nj≠qP(xj,yq) P(x_q,y_q)+ _ subarrayck+1≤ j≤ n\\ j≠ q subarrayP(x_j,y_q) ∑zP(y1x1,…,ykxk,xp∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p z)× P(z) ≤ ≤ ∑z[P(yjxj∣z)−P(xj,yj∣z)]×P(z) _z [P(y_j_x_j z)-P(x_j,y_j z) ]× P(z) = = P(yjxj)−P(xj,yj) P(y_j_x_j)-P(x_j,y_j) Thus, we can guarantee that the proposed lower and upper bounds are no looser than those of 14. Following the notation in 10, P(yjxj∣z)P(y_j_x_j z) denotes experimental data within the subpopulation characterized by z. ∎ Proof of Theorem 5 Proof. PN(k,p,q) PN(k,p,q) = = P(y1x1,…,ykxk,xp,yq) P(y_1_x_1,...,y_k_x_k,x_p,y_q) (7) = = ∑zP(y1x1,…,ykxk,xp,yq∣z) _zP(y_1_x_1,...,y_k_x_k,x_p,y_q z) ×P(z) × P(z) First, we need to prove: max0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xp,yq∣z)−k \ array[]c0,\\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_p,y_q z)-k\\ array \ ≤P(y1x1,…,ykxk,xp,yq∣z) ≤ P(y_1_x_1,...,y_k_x_k,x_p,y_q z) minP(xp,yq∣z),For j∈1,…,k:P(yjxj∣z)−P(xj,yj∣z) \ array[]cP(x_p,y_q z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z)-P(x_j,y_j z)\\ array \ ≥P(y1x1,…,ykxk,xp,yq∣z) ≥ P(y_1_x_1,...,y_k_x_k,x_p,y_q z) By the Fréchet Inequalities, for any z with P(z)>0P(z)>0, we can obtain the first lower bound and the first upper bound, P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z) ≥ ≥ 0 0 P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z) ≤ ≤ P(xp,yq∣z). P(x_p,y_q z). The equality of the first lower bound holds when ∃j∈[1,k],that P(yjxj∣z)=0∃ j∈[1,k],that P(y_j_x_j z)=0 or P(xp∣z)=0P(x_p z)=0 or P(yq∣z)=0P(y_q z)=0, p≠jp≠ j. The equality of the first upper bound holds when P(yjxj∣z)=1P(y_j_x_j z)=1 for ∀j∈[1,k]∀ j∈[1,k]. For the second lower bound P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z) = = P(y1x1,…,ykxk,xp,yq∣z)+P(y1x1,…,ykxk∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z)+P(y_1_x_1,...,y_k_x_k z) −P(y1x1,…,ykxk∣z) -P(y_1_x_1,...,y_k_x_k z) = = P(y1x1,…,ykxk∣z)+P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k z)+P(y_1_x_1,...,y_k_x_k,x_p,y_q z) −∑j=1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) = = P(y1x1,…,ykxk∣z)+P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k z)+P(y_1_x_1,...,y_k_x_k,x_p,y_q z) +∑j=1nP(xj∣z)−1 + _j=1^nP(x_j z)-1 −∑j=1kP(y1x1,…,ykxk,xj,yj∣z) - _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z)−∑j=1kP(y1x1,…,ykxk,xj,yj∣z) + _j=1^kP(x_j z)- _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑j=k+1n∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _j=k+1^n _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) +P(y1x1,…,ykxk,xp,yq∣z) +P(y_1_x_1,...,y_k_x_k,x_p,y_q z) = = P(y1x1,…,ykxk∣z)−1 P(y_1_x_1,...,y_k_x_k z)-1 +∑j=1kP(xj∣z)−∑j=1kP(y1x1,…,ykxk,xj,yj∣z) + _j=1^kP(x_j z)- _j=1^kP(y_1_x_1,...,y_k_x_k,x_j,y_j z) +∑j=k+1nP(xj∣z) + _j=k+1^nP(x_j z) −∑k+1≤j≤n,j≠p∑l=1nP(y1x1,…,ykxk,xj,yl∣z) - _ subarrayck+1≤ j≤ n,\\ j≠ p subarray _l=1^nP(y_1_x_1,...,y_k_x_k,x_j,y_l z) −∑1≤l≤n,l≠pP(y1x1,…,ykxk,xp,yl∣z) - _ subarrayc1≤ l≤ n,\\ l≠ p subarrayP(y_1_x_1,...,y_k_x_k,x_p,y_l z) ≥ ≥ ∑j=1kP(yjxj∣z)−(k−1)−1+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-(k-1)-1+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z)+∑j=k+1nP(xj∣z) - _j=1^kP(x_j,y_j z)+ _j=k+1^nP(x_j z) −∑k+1≤j≤n,j≠pP(xj∣z)−∑1≤l≤n,l≠pP(xp,yl∣z) - _ subarrayck+1≤ j≤ n,\\ j≠ p subarrayP(x_j z)- _ subarrayc1≤ l≤ n,\\ l≠ p subarrayP(x_p,y_l z) here, the equal sign holds when ∃j∈[1,n], , the equal sign holds when ∃ j∈[1,n], and P(yixi∣z)=1 for ∀i∈[1,k],i≠j. and P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. = = ∑j=1kP(yjxj∣z)−k+∑j=1kP(xj∣z) _j=1^kP(y_j_x_j z)-k+ _j=1^kP(x_j z) −∑j=1kP(xj,yj∣z)+P(xp∣z) - _j=1^kP(x_j,y_j z)+P(x_p z) −∑1≤l≤n,l≠pP(xp,yl∣z) - _ subarrayc1≤ l≤ n,\\ l≠ p subarrayP(x_p,y_l z) = = ∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)] _j=1^k [P(y_j_x_j z)+P(x_j z)-P(x_j,y_j z) ] +P(xp,yq∣z)−k +P(x_p,y_q z)-k The equality of the second lower bound holds when ∃j∈[1,n],P(yixi∣z)=1 for ∀i∈[1,k],i≠j∃ j∈[1,n],P(y_i_x_i z)=1 for ∀ i∈[1,k],i≠ j. For the remaining upper bounds, ∀j∈[1,k]∀ j∈[1,k]: P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z) = = P(y1x1,…,ykxk,xp,yq∣z)+P(yjxj∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z)+P(y_j_x_j z) −P(yjxj∣z) -P(y_j_x_j z) = = P(y1x1,…,ykxk,xp,yq∣z)+P(yjxj∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z)+P(y_j_x_j z) −∑i1,…,ij−1,ij+1,…,ik+2∈1,…,nk+1P(yi1x1,…,yij−1xj−1, - _ subarrayc\i_1,...,i_j-1,i_j+1,...,i_k+2\\\ ∈\1,...,n\^k+1 subarrayP(y_i_1_x_1,...,y_i_j-1_x_j-1, OPENyjxj,yij+1xj+1,…,yikxk,xik+1,yik+2∣z) y_j_x_j,y_i_j+1_x_j+1,...,y_i_k_x_k,x_i_k+1,y_i_k+2 z) Since p≠jp≠ j for 1≤j≤k1≤ j≤ k, P(y1x1,…,ykxk,xp,yq∣z) P(y_1_x_1,...,y_k_x_k,x_p,y_q z) ≤ ≤ P(yjxj∣z)−∑i1,…,ij−1,ij+1,…,ik∈1,…,nk−1P(yi1x1,…CLOSE, P(y_j_x_j z)- _ subarrayc\i_1,...,i_j-1,i_j+1,...,i_k\\\ ∈\1,...,n\^k-1 subarrayP(y_i_1_x_1,..., OPENyij−1xj−1,yjxj,yij+1xj+1,…,yikxk,xj,yj∣z) y_i_j-1_x_j-1,y_j_x_j,y_i_j+1_x_j+1,...,y_i_k_x_k,x_j,y_j z) here, the equal sign holds when P(xj∣z)=0, , the equal sign holds when P(x_j z)=0, P(yj∣z)=0 and P(xt1,yt2∣z)=0 P(y_j z)=0 and P(x_t_1,y_t_2 z)=0 for ∀j∈[k+1,n],∀t1,t2∈[1,k] and t1≠t2. for ∀ j∈[k+1,n],∀ t_1,t_2∈[1,k] and t_1≠ t_2. = = P(yjxj∣z)−P(yjxj,xj,yj∣z) P(y_j_x_j z)-P(y_j_x_j,x_j,y_j z) = = P(yjxj∣z)−P(xj,yj∣z) P(y_j_x_j z)-P(x_j,y_j z) The equality of the second upper bound holds when P(xj∣z)=0,P(yj∣z)=0 and P(xt1,yt2∣z)=0 for ∀j∈[k+1,n],t1,t2∈[1,k] and t1≠t2P(x_j z)=0,P(y_j z)=0 and P(x_t_1,y_t_2 z)=0 for ∀ j∈[k+1,n],t_1,t_2∈[1,k] and t_1≠ t_2. By substituting max0,∑j=1k[P(yjxj∣z)+P(xj∣z)−P(xj,yj∣z)]+P(xp,yq∣z)−k \ array[]c0,\\ _j=1^k [P(y_j_x_j z)+P(x_j z)-\\ -P(x_j,y_j z) ]+P(x_p,y_q z)-k\\ array \ ≤P(y1x1,…,ykxk,xp,yq∣z) ≤ P(y_1_x_1,...,y_k_x_k,x_p,y_q z) minP(xp,yq∣z),For j∈1,…,k:P(yjxj∣z)−P(xj,yj∣z) \ array[]cP(x_p,y_q z),\\ \\ For j∈\1,...,k\:\\ P(y_j_x_j z)-P(x_j,y_j z)\\ array \ ≥P(y1x1,…,ykxk,xp,yq∣z) ≥ P(y_1_x_1,...,y_k_x_k,x_p,y_q z) into equation (7), and applying law of total probability, we have ∑zP(y1x1,…,ykxk,xp,yq∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p,y_q z)× P(z) ≥ ≥ ∑z0×P(z) _z0× P(z) = = 0 0 OPEN∑zP(y1x1,…,ykxk,xp,yq∣z))×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p,y_q z))× P(z) ≥ ≥ ∑z∑j=1k[P(yjxj∣z)+P(xj∣z) _z \ _j=1^k [P(y_j_x_j z)+P(x_j z) −P(xj,yj∣z)]+P(xp,yq∣z)−k×P(z) -P(x_j,y_j z) ]+P(x_p,y_q z)-k \× P(z) = = ∑j=1k[P(yjxj)+P(xj)−P(xj,yj)] _j=1^k [P(y_j_x_j)+P(x_j)-P(x_j,y_j) ] +P(xp,yq)−k +P(x_p,y_q)-k ∑zP(y1x1,…,ykxk,xp,yq∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p,y_q z)× P(z) ≤ ≤ P(xp,yq∣z)×P(z) P(x_p,y_q z)× P(z) = = P(xp,yq) P(x_p,y_q) ∑zP(y1x1,…,ykxk,xp,yq∣z)×P(z) _zP(y_1_x_1,...,y_k_x_k,x_p,y_q z)× P(z) ≤ ≤ [P(yjxj∣z)−P(xj,yj∣z)]×P(z) [P(y_j_x_j z)-P(x_j,y_j z) ]× P(z) = = OPENP(yjxj)−P(xj,yj)) P(y_j_x_j)-P(x_j,y_j)) Thus, we can guarantee that the proposed lower and upper bounds are no looser than those of 14. Following the notation in 10, P(yjxj∣z)P(y_j_x_j z) denotes experimental data within the subpopulation characterized by z. ∎ Proof of Theorem 6 Proof. PNS(k) PNS(k) = = P(y1x1,…,ykxk) P(y_1_x_1,...,y_k_x_k) = = ∑z1,…,zk∈1,…,nkP(y1x1,…,ykxk,z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_x_1,...,y_k_x_k,z_1_x_1,...,z_k_x_k) = = ∑z1,…,zk∈1,…,nkP(y1x1,…,ykxk∣z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_x_1,...,y_k_x_k z_1_x_1,...,z_k_x_k) ×P(z1x1,…,zkxk) × P(z_1_x_1,...,z_k_x_k) ≤ ≤ ∑z1,…,zk∈1,…,nkminP(y1x1∣z1x1,…,zkxk),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1_x_1 z_1_x_1,...,z_k_x_k),..., P(ykxk∣z1x1,…,zkxk) P(y_k_x_k z_1_x_1,...,z_k_x_k) \ ×minP(z1x1),…,P(zkxk) × \P(z_1_x_1),...,P(z_k_x_k) \ the equality sign holds when for ∀j∈[1,k]∀ j∈[1,k], P(yjxj∣z1x1,…,zkxk)=0 or P(zjxj)=0 P(y_j_x_j z_1_x_1,…,z_k_x_k)=0 or P(z_j_x_j)=0 = = ∑z1,…,zk∈1,…,nkminP(y1x1∣z1x1),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1_x_1 z_1_x_1),..., P(ykxk∣zkxk)×minP(z1x1),…,P(zkxk) P(y_k_x_k z_k_x_k) \× \P(z_1_x_1),...,P(z_k_x_k) \ it follows from the cross-world conditional independences that derive from graph: Yxj⟂Zxi:i≠j|Zxj,j=1,…,k.Y_x_j \!\!\! \Z_x_i:i≠ j\ Z_x_j, j=1,…,k. = = ∑z1,…,zk∈1,…,nkminP(y1∣z1x1,x1),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1 z_1_x_1,x_1),..., P(yk∣zkxk,xk)×minP(z1x1),…,P(zkxk) P(y_k z_k_x_k,x_k) \× \P(z_1_x_1),...,P(z_k_x_k) \ since for ∀xj,Yxj⟂X|Zxj∀ x_j,\;Y_x_j \!\!\! X Z_x_j. = = ∑z1,…,zk∈1,…,nkminP(y1∣z1,x1),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1 z_1,x_1),..., P(yk∣zk,xk)×minP(z1x1),…,P(zkxk) P(y_k z_k,x_k) \× \P(z_1_x_1),...,P(z_k_x_k) \ Hence, we can say for j ∈1,…,k∈\1,...,k\, PNS(k) PNS(k) ≤∑z1,…,zk∈1,…,nk ≤ _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray minjP(yj∣xj,zj) _j\P(y_j x_j,z_j)\ ×minjP(zjxj) × _j\P(z_j_x_j)\ ∎ Proof of Theorem 7 Proof. PSub(k,p) PSub(k,p) = = P(y1x1,…,ykxk,xp) P(y_1_x_1,...,y_k_x_k,x_p) = = ∑z1,…,zk∈1,…,nkP(y1x1,…,ykxk,xp,z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_x_1,...,y_k_x_k,x_p,z_1_x_1,...,z_k_x_k) = = ∑z1,…,zk∈1,…,nkP(y1x1,…,ykxk,xp∣z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_x_1,...,y_k_x_k,x_p z_1_x_1,...,z_k_x_k) ×P(z1x1,…,zkxk) × P(z_1_x_1,...,z_k_x_k) = = ∑z1,…,zk∈1,…,nkP(y1x1,…,ykxk∣z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_x_1,...,y_k_x_k z_1_x_1,...,z_k_x_k) ×P(xp∣z1x1,…,zkxk)×P(z1x1,…,zkxk) × P(x_p z_1_x_1,...,z_k_x_k)× P(z_1_x_1,...,z_k_x_k) since (Yx1,…,Yxk)⟂X|(Zx1,…,Zxk) (Y_x_1,…,Y_x_k ) \!\!\! X (Z_x_1,…,Z_x_k ) = = ∑z1,…,zk∈1,…,nkP(y1x1,…,ykxk∣z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_x_1,...,y_k_x_k z_1_x_1,...,z_k_x_k) ×P(z1x1,…,zkxk,xp) × P(z_1_x_1,...,z_k_x_k,x_p) ≤ ≤ ∑z1,…,zk∈1,…,nkminP(y1x1∣z1x1,…,zkxk),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1_x_1 z_1_x_1,...,z_k_x_k),..., P(ykxk∣z1x1,…,zkxk) P(y_k_x_k z_1_x_1,...,z_k_x_k) \ ×minP(z1x1),…,P(zkxk),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(x_p) \ the equality sign holds when for ∀j∈[1,k]∀ j∈[1,k], P(yjxj∣z1x1,…,zkxk)=0 P(y_j_x_j z_1_x_1,…,z_k_x_k)=0 or P(zjxj)=0 or P(xp)=0 or P(z_j_x_j)=0 or P(x_p)=0 = = ∑z1,…,zk∈1,…,nkminP(y1x1∣z1x1),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1_x_1 z_1_x_1),..., P(ykxk∣zkxk) P(y_k_x_k z_k_x_k) \ ×minP(z1x1),…,P(zkxk),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(x_p) \ as for j∈[1,k]j∈[1,k]: Yxj⟂Zxi:i≠j|ZxjY_x_j \!\!\! \Z_x_i:i≠ j\ Z_x_j = = ∑z1,…,zk∈1,…,nkminP(y1∣z1x1,x1),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1 z_1_x_1,x_1),..., P(yk∣zkxk,xk) P(y_k z_k_x_k,x_k) \ ×minP(z1x1),…,P(zkxk),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(x_p) \ since for ∀xj,Yxj⟂X|Zxj∀ x_j,\;Y_x_j \!\!\! X Z_x_j. = = ∑z1,…,zk∈1,…,nkminP(y1∣z1,x1),…, _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray \P(y_1 z_1,x_1),..., P(yk∣zk,xk) P(y_k z_k,x_k) \ ×minP(z1x1),…,P(zkxk),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(x_p) \ Hence, we can say for j ∈1,…,k∈\1,...,k\, PSub(k,p) PSub(k,p) ≤∑z1,…,zk∈1,…,nk ≤ _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray minjP(yj∣xj,zj) _j\P(y_j x_j,z_j)\ ×minjP(zjxj),P(xp) × _j\P(z_j_x_j),P(x_p)\ ∎ Proof of Theorem 8 Proof. PRep(k,q) PRep(k,q) = = P(y1x1,…,ykxk,yq) P(y_1_x_1,...,y_k_x_k,y_q) ≤ ≤ P(y1x1,…,ykxk) P(y_1_x_1,...,y_k_x_k) the equality sign holds when P(yq)=0 equality sign holds when P(y_q)=0 ≤ ≤ ∑z1,…,zk∈1,…,nkminjP(yj∣xj,zj)×minjP(zjxj) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray _j\P(y_j x_j,z_j)\× _j\P(z_j_x_j)\ Hence, we can say for j ∈1,…,k∈\1,...,k\, PRep(k,q) PRep(k,q) ≤∑z1,…,zk∈1,…,nk ≤ _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarray minjP(yj∣xj,zj)×minjP(zjxj) _j\P(y_j x_j,z_j)\× _j\P(z_j_x_j)\ ∎ Proof of Theorem 9 Proof. PN(k,p,q) PN(k,p,q) = = P(y1x1,…,ykxk,xp,yq) P(y_1_x_1,...,y_k_x_k,x_p,y_q) = = P(y1x1,…,ykxk,yqxp,xp) P(y_1_x_1,...,y_k_x_k,y_q_x_p,x_p) = = ∑z1,…,zk,zp∈1,…,nk+1P(y1x1,…,ykxk,yqxp,xp,z1x1,…CLOSE, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarrayP(y_1_x_1,...,y_k_x_k,y_q_x_p,x_p,z_1_x_1,..., OPENzkxk,zpxp) z_k_x_k,z_p_x_p) = = ∑z1,…,zk,zp∈1,…,nk+1P(y1x1,…,ykxk,yqxp,xp∣z1x1,…, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarrayP(y_1_x_1,...,y_k_x_k,y_q_x_p,x_p z_1_x_1,..., OPENzkxk,zpxp) z_k_x_k,z_p_x_p) ×P(z1x1,…,zkxk,zpxp) × P(z_1_x_1,...,z_k_x_k,z_p_x_p) = = ∑z1,…,zk,zp∈1,…,nk+1P(y1x1,…,ykxk,yqxp∣z1x1,…,zkxk, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarrayP(y_1_x_1,...,y_k_x_k,y_q_x_p z_1_x_1,...,z_k_x_k, OPENzpxp) z_p_x_p) ×P(xp∣z1x1,…,zkxk,zpxp) × P(x_p z_1_x_1,...,z_k_x_k,z_p_x_p) ×P(z1x1,…,zkxk,zpxp) × P(z_1_x_1,...,z_k_x_k,z_p_x_p) since (Yx1,…,Yxk,Yxp)⟂X|(Zx1,…,ZxkCLOSE, (Y_x_1,…,Y_x_k,Y_x_p ) \!\!\! X (Z_x_1,…,Z_x_k, OPENZxp) Z_x_p) = = ∑z1,…,zk,zp∈1,…,nk+1P(y1x1,…,ykxk,yqxp∣z1x1,…,zkxk, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarrayP(y_1_x_1,...,y_k_x_k,y_q_x_p z_1_x_1,...,z_k_x_k, OPENzpxp) z_p_x_p) ×P(z1x1,…,zkxk,zpxp,xp) × P(z_1_x_1,...,z_k_x_k,z_p_x_p,x_p) ≤ ≤ ∑z1,…,zk,zp∈1,…,nk+1minP(y1x1∣z1x1,…,zkxk,zpxp), _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarray \P(y_1_x_1 z_1_x_1,...,z_k_x_k,z_p_x_p), ...,P(ykxk∣z1x1,…,zkxk,zpxp), ...,P(y_k_x_k z_1_x_1,...,z_k_x_k,z_p_x_p), P(yqxp∣z1x1,…,zkxk,zpxp) P(y_q_x_p z_1_x_1,...,z_k_x_k,z_p_x_p) \ ×minP(z1x1),…,P(zkxk),P(zpxp),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(z_p_x_p),P(x_p) \ the equality sign holds when for ∀j∈[1,k]∀ j∈[1,k], P(yjxj∣z1x1,…,zkxk,zpxp)=0 P(y_j_x_j z_1_x_1,…,z_k_x_k,z_p_x_p)=0 or P(yqxp∣z1x1,…,zkxk,zpxp)=0 or P(y_q_x_p z_1_x_1,…,z_k_x_k,z_p_x_p)=0 or P(zjxj)=0 or P(zpxp)=0 or P(xp)=0 or P(z_j_x_j)=0 or P(z_p_x_p)=0 or P(x_p)=0 = = ∑z1,…,zk,zp∈1,…,nk+1minP(y1x1∣z1x1),…, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarray \P(y_1_x_1 z_1_x_1),..., P(ykxk∣zkxk),P(yqxp∣zpxp) P(y_k_x_k z_k_x_k),P(y_q_x_p z_p_x_p) \ ×minP(z1x1),…,P(zkxk),P(zpxp),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(z_p_x_p),P(x_p) \ as for j∈1,…,k,pj∈\1,…,k,p\: Yxj⟂Zxi:i≠j|ZxjY_x_j \!\!\! \Z_x_i:i≠ j\ Z_x_j = = ∑z1,…,zk,zp∈1,…,nk+1minP(y1∣z1x1,x1),…, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarray \P(y_1 z_1_x_1,x_1),..., P(yk∣zkxk,xk),P(yq∣zpxp,xp) P(y_k z_k_x_k,x_k),P(y_q z_p_x_p,x_p) \ ×minP(z1x1),…,P(zkxk),P(zpxp),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(z_p_x_p),P(x_p) \ since for ∀xj,Yxj⟂X|Zxj∀ x_j,\;Y_x_j \!\!\! X Z_x_j. = = ∑z1,…,zk,zp∈1,…,nk+1minP(y1∣z1,x1),…, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarray \P(y_1 z_1,x_1),..., P(yk∣zk,xk),P(yq∣zp,xp) P(y_k z_k,x_k),P(y_q z_p,x_p) \ ×minP(z1x1),…,P(zkxk),P(zpxp),P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(z_p_x_p),P(x_p) \ Hence, we can say for j ∈1,…,k∈\1,...,k\, PN(k,p,q) PN(k,p,q) ≤∑z1,…,zk,zp∈1,…,nk+1 ≤ _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarray minjP(yj∣xj,zj),P(yq∣xp,zp) _j\P(y_j x_j,z_j),P(y_q x_p,z_p)\ ×minjP(zjxj),P(zpxp),P(xp) × _j\P(z_j_x_j),P(z_p_x_p),P(x_p)\ ∎ Proof of Theorem 10 Proof. PNS(k) PNS(k) = = P(y1x1,…,ykxk) P(y_1_x_1,...,y_k_x_k) = = ∑z1,…,zk∈1,…,nkP(y1z1,…,ykzk,z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_z_1,...,y_k_z_k,z_1_x_1,...,z_k_x_k) = = ∑z1≠…≠zkP(y1z1,…,ykzk)×P(z1x1,…,zkxk) _ subarraycz_1≠...≠z_k subarrayP(y_1_z_1,...,y_k_z_k)× P(z_1_x_1,...,z_k_x_k) ≤ ≤ ∑z1≠…≠zkminP(y1z1),…,P(ykzk) _ subarraycz_1≠...≠z_k subarray \P(y_1_z_1),...,P(y_k_z_k)\ ×minP(z1x1),…,P(zkxk) × \P(z_1_x_1),...,P(z_k_x_k)\ the equality sign holds when for ∀j∈[1,k]∀ j∈[1,k], P(yjzj)=0 or P(zjxj)=0 P(y_j_z_j)=0 or P(z_j_x_j)=0 = = ∑z1≠…≠zkminP(y1∣z1),…,P(yk∣zk) _ subarraycz_1≠...≠z_k subarray \P(y_1 z_1),...,P(y_k z_k)\ ×minP(z1∣x1),…,P(zk∣xk) × \P(z_1 x_1),...,P(z_k x_k)\ Hence, we can say for j∈1,…,kj∈\1,...,k\, PNS(k) PNS(k) ≤∑z1≠…≠zk∈1,…,nk ≤ _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray minjP(yj∣zj)×minjP(zj∣xj) _j\P(y_j z_j)\× _j\P(z_j x_j)\ ∎ Proof of Theorem 11 Proof. PSub(k,p) PSub(k,p) = = P(y1x1,…,ykxk,xp) P(y_1_x_1,...,y_k_x_k,x_p) = = ∑z1,…,zk∈1,…,nkP(y1z1,…,ykzk,xp,z1x1,…,zkxk) _ subarraycz_1,...,z_k\\ ∈\1,...,n\^k subarrayP(y_1_z_1,...,y_k_z_k,x_p,z_1_x_1,...,z_k_x_k) = = ∑z1≠…≠zkP(y1z1,…,ykzk)×P(z1x1,…,zkxk) _ subarraycz_1≠...≠z_k subarrayP(y_1_z_1,...,y_k_z_k)× P(z_1_x_1,...,z_k_x_k) ×P(xp) × P(x_p) as X⟂Yzj,ZxjX \!\!\! \Y_z_j,Z_x_j\ ≤ ≤ ∑z1≠…≠zkminP(y1z1),…,P(ykzk) _ subarraycz_1≠...≠z_k subarray \P(y_1_z_1),...,P(y_k_z_k)\ ×minP(z1x1),…,P(zkxk)×P(xp) × \P(z_1_x_1),...,P(z_k_x_k)\× P(x_p) the equality sign holds when for ∀j∈[1,k]∀ j∈[1,k], P(yjzj)=0 or P(zjxj)=0 P(y_j_z_j)=0 or P(z_j_x_j)=0 = = ∑z1≠…≠zkminP(y1∣z1),…,P(yk∣zk) _ subarraycz_1≠...≠z_k subarray \P(y_1 z_1),...,P(y_k z_k)\ ×minP(z1∣x1),…,P(zk∣xk)×P(xp) × \P(z_1 x_1),...,P(z_k x_k)\× P(x_p) Hence, we can say for j∈1,…,kj∈\1,...,k\, PSub(k,p) PSub(k,p) ≤ ≤ ∑z1≠…≠zk∈1,…,nkminjP(yj∣zj) _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray _j\P(y_j z_j)\ ×minjP(zj∣xj)×P(xp) × _j\P(z_j x_j)\× P(x_p) ∎ Proof of Theorem 12 Proof. PRep(k,q) PRep(k,q) = = P(y1x1,…,ykxk,yq) P(y_1_x_1,...,y_k_x_k,y_q) ≤ ≤ P(y1x1,…,ykxk) P(y_1_x_1,...,y_k_x_k) the equality sign holds when P(yq)=0 equality sign holds when P(y_q)=0 ≤ ≤ ∑z1≠…≠zk∈1,…,nkminjP(yj∣zj)×minjP(zj∣xj) _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray _j\P(y_j z_j)\× _j\P(z_j x_j)\ Hence, we can say for j∈1,…,kj∈\1,...,k\, PRep(k,q) PRep(k,q) ≤∑z1≠…≠zk∈1,…,nk ≤ _ subarraycz_1≠...≠z_k\\ ∈\1,...,n\^k subarray minjP(yj∣zj)×minjP(zj∣xj) _j\P(y_j z_j)\× _j\P(z_j x_j)\ ∎ Proof of Theorem 13 Proof. PN(k,p,q) PN(k,p,q) = = P(y1x1,…,ykxk,xp,yq) P(y_1_x_1,...,y_k_x_k,x_p,y_q) = = P(y1x1,…,ykxk,yqxp,xp) P(y_1_x_1,...,y_k_x_k,y_q_x_p,x_p) = = ∑z1,…,zk,zp∈1,…,nk+1P(y1z1,…,ykzk,yqzp,z1x1,…,zkxkCLOSE, _ subarraycz_1,...,z_k,z_p\\ ∈\1,...,n\^k+1 subarrayP(y_1_z_1,...,y_k_z_k,y_q_z_p,z_1_x_1,...,z_k_x_k, OPENzpxp,xp) z_p_x_p,x_p) = = ∑z1≠…≠zk≠zpP(y1z1,…,ykzk,yqzp) _ subarraycz_1≠...≠z_k≠z_p subarrayP(y_1_z_1,...,y_k_z_k,y_q_z_p) ×P(z1x1,…,zkxk,zpxp)×P(xp) × P(z_1_x_1,...,z_k_x_k,z_p_x_p)× P(x_p) as X⟂Yzj,ZxjX \!\!\! \Y_z_j,Z_x_j\ ≤ ≤ ∑z1≠…≠zk≠zpminP(y1z1),…,P(ykzk),P(yqzp) _ subarraycz_1≠...≠z_k≠z_p subarray \P(y_1_z_1),...,P(y_k_z_k),P(y_q_z_p)\ ×minP(z1x1),…,P(zkxk),P(zpxp)×P(xp) × \P(z_1_x_1),...,P(z_k_x_k),P(z_p_x_p)\× P(x_p) the equality sign holds when for ∀j∈[1,k]∀ j∈[1,k], P(yjzj)=0 or P(yqzp)=0 P(y_j_z_j)=0 or P(y_q_z_p)=0 or P(zjxj)=0 or P(zpxp)=0 or P(z_j_x_j)=0 or P(z_p_x_p)=0 = = ∑z1≠…≠zk≠zpminP(y1∣z1),…,P(yk∣zk), _ subarraycz_1≠...≠z_k≠z_p subarray \P(y_1 z_1),...,P(y_k z_k), P(yq∣zp) P(y_q z_p)\ ×minP(z1∣x1),…,P(zk∣xk),P(zp∣xp) × \P(z_1 x_1),...,P(z_k x_k),P(z_p x_p)\ ×P(xp) × P(x_p) Hence, we can say for j∈1,…,kj∈\1,...,k\, PN(k,p,q) PN(k,p,q) ≤∑z1≠…≠zk≠zp∈1,…,nk+1 ≤ _ subarraycz_1≠...≠z_k≠z_p\\ ∈\1,...,n\^k+1 subarray minjP(yj∣zj),P(yq∣zp) _j\P(y_j z_j),P(y_q z_p)\ ×minjP(zj∣xj),P(zp∣xp) × _j\P(z_j x_j),P(z_p x_p)\ ×P(xp) × P(x_p) ∎ Examples Example 1: Family History as a Covariate From Table 1, we can collect all data we want. Since each entry in the table represents the count n(x,y,z)n(x,y,z), for each fixed value Z=zZ=z, we have P(x∣z)=∑yn(x,y,z)∑x,yn(x,y,z),P(x z)= _yn(x,y,z) _x,yn(x,y,z), P(y∣x,z)=n(x,y,z)∑yn(x,y,z),P(y x,z)= n(x,y,z) _yn(x,y,z), and P(y,x∣z)=n(x,y,z)∑x,yn(x,y,z).P(y,x z)= n(x,y,z) _x,yn(x,y,z). These quantities satisfy P(y,x∣z)=P(y∣x,z)P(x∣z).P(y,x z)=P(y x,z)P(x z). For z1z_1, we have P(z1)=25, P(z_1)= 25, P(x1∣z1)=16,P(x2∣z1)=13,P(x3∣z1)=12. P(x_1 z_1)= 16, P(x_2 z_1)= 13, P(x_3 z_1)= 12. P(y1∣x1,z1) P(y_1 x_1,z_1) =2330, = 2330, P(y1∣x2,z1) P(y_1 x_2,z_1) =130, = 130, P(y1∣x3,z1) P(y_1 x_3,z_1) =930, = 930, P(y2∣x1,z1) P(y_2 x_1,z_1) =630, = 630, P(y2∣x2,z1) P(y_2 x_2,z_1) =2830, = 2830, P(y2∣x3,z1) P(y_2 x_3,z_1) =2030, = 2030, P(y3∣x1,z1) P(y_3 x_1,z_1) =130, = 130, P(y3∣x2,z1) P(y_3 x_2,z_1) =130, = 130, P(y3∣x3,z1) P(y_3 x_3,z_1) =130. = 130. P(x1,y1∣z1) P(x_1,y_1 z_1) =23180, = 23180, P(x2,y1∣z1) P(x_2,y_1 z_1) =2180, = 2180, P(x3,y1∣z1) P(x_3,y_1 z_1) =27180, = 27180, P(x1,y2∣z1) P(x_1,y_2 z_1) =6180, = 6180, P(x2,y2∣z1) P(x_2,y_2 z_1) =56180, = 56180, P(x3,y2∣z1) P(x_3,y_2 z_1) =60180, = 60180, P(x1,y3∣z1) P(x_1,y_3 z_1) =1180, = 1180, P(x2,y3∣z1) P(x_2,y_3 z_1) =2180, = 2180, P(x3,y3∣z1) P(x_3,y_3 z_1) =3180. = 3180. For z2z_2, we have P(z2)=15, P(z_2)= 15, P(x1∣z2)=12,P(x2∣z2)=16,P(x3∣z2)=13. P(x_1 z_2)= 12, P(x_2 z_2)= 16, P(x_3 z_2)= 13. P(y1∣x1,z2) P(y_1 x_1,z_2) =130, = 130, P(y1∣x2,z2) P(y_1 x_2,z_2) =330, = 330, P(y1∣x3,z2) P(y_1 x_3,z_2) =130, = 130, P(y2∣x1,z2) P(y_2 x_1,z_2) =2530, = 2530, P(y2∣x2,z2) P(y_2 x_2,z_2) =2530, = 2530, P(y2∣x3,z2) P(y_2 x_3,z_2) =130, = 130, P(y3∣x1,z2) P(y_3 x_1,z_2) =430, = 430, P(y3∣x2,z2) P(y_3 x_2,z_2) =230, = 230, P(y3∣x3,z2) P(y_3 x_3,z_2) =2830. = 2830. P(x1,y1∣z2) P(x_1,y_1 z_2) =3180, = 3180, P(x2,y1∣z2) P(x_2,y_1 z_2) =3180, = 3180, P(x3,y1∣z2) P(x_3,y_1 z_2) =2180, = 2180, P(x1,y2∣z2) P(x_1,y_2 z_2) =75180, = 75180, P(x2,y2∣z2) P(x_2,y_2 z_2) =25180, = 25180, P(x3,y2∣z2) P(x_3,y_2 z_2) =2180, = 2180, P(x1,y3∣z2) P(x_1,y_3 z_2) =12180, = 12180, P(x2,y3∣z2) P(x_2,y_3 z_2) =2180, = 2180, P(x3,y3∣z2) P(x_3,y_3 z_2) =56180. = 56180. For z3z_3, we have P(z3)=25, P(z_3)= 25, P(x1∣z3)=23,P(x2∣z3)=16,P(x3∣z3)=16. P(x_1 z_3)= 23, P(x_2 z_3)= 16, P(x_3 z_3)= 16. P(y1∣x1,z3) P(y_1 x_1,z_3) =2430, = 2430, P(y1∣x2,z3) P(y_1 x_2,z_3) =2230, = 2230, P(y1∣x3,z3) P(y_1 x_3,z_3) =230, = 230, P(y2∣x1,z3) P(y_2 x_1,z_3) =330, = 330, P(y2∣x2,z3) P(y_2 x_2,z_3) =130, = 130, P(y2∣x3,z3) P(y_2 x_3,z_3) =130, = 130, P(y3∣x1,z3) P(y_3 x_1,z_3) =330, = 330, P(y3∣x2,z3) P(y_3 x_2,z_3) =730, = 730, P(y3∣x3,z3) P(y_3 x_3,z_3) =2730. = 2730. P(x1,y1∣z3) P(x_1,y_1 z_3) =96180, = 96180, P(x2,y1∣z3) P(x_2,y_1 z_3) =22180, = 22180, P(x3,y1∣z3) P(x_3,y_1 z_3) =2180, = 2180, P(x1,y2∣z3) P(x_1,y_2 z_3) =12180, = 12180, P(x2,y2∣z3) P(x_2,y_2 z_3) =1180, = 1180, P(x3,y2∣z3) P(x_3,y_2 z_3) =1180, = 1180, P(x1,y3∣z3) P(x_1,y_3 z_3) =12180, = 12180, P(x2,y3∣z3) P(x_2,y_3 z_3) =7180, = 7180, P(x3,y3∣z3) P(x_3,y_3 z_3) =27180. = 27180. After applying the back-door adjustment formula, which gives P(yjxj∣z)=P(yj∣xj,z). P(y_j_x_j z)=P(y_j x_j,z). Substituting this equality into Theorems 2 yields a new theorem that requires only observational data, without the need for experimental data. The new equation is listed below: ∑zmax0,∑j=1kP(yj∣xj,z)−k+1,For i∈1,…,k:∑1≤j≤kj≠i[P(yj∣xj,z)++P(xj∣z)−P(xj,yj∣z)]++P(xi,yi∣z)−k+1×P(z) _z \ array[]c0,\\ \\ _j=1^kP(y_j x_j,z)-k+1,\\ \\ For i∈\1,...,k\:\\ _ subarrayc1≤ j≤ k\\ j≠ i subarray [P(y_j x_j,z)+\\ +P(x_j z)-P(x_j,y_j z) ]+\\ +P(x_i,y_i z)-k+1 array \× P(z) ≤PNS(k) ≤ PNS(k) ∑zmin∑j=1kP(xj,yj∣z)++∑j=k+1nP(xj∣z),For j∈1,…,k:P(yj∣xj,z),For m∈1,…,k−1,tj∈1,…,k:1m[∑j=0mP(ytj∣xtj,z)−P(xtj,ytj∣z)]×P(z) _z \ array[]c _j=1^kP(x_j,y_j z)+\\ + _j=k+1^nP(x_j z),\\ \\ For j∈\1,...,k\:\\ P(y_j x_j,z),\\ \\ For m∈\1,...,k-1\,\\ t_j∈\1,...,k\:\\ 1m [ _j=0^mP(y_t_j x_t_j,z)-\\ -P(x_t_j,y_t_j z) ] array \× P(z) ≥PNS(k) ≥ PNS(k) By applying the new bounds, we can derive ∑zmax0,P(y1∣x1,z)+P(y2∣x2,z)+P(y3∣x3,z)−2,[P(y2∣x2,z)+P(x2∣z)−P(x2,y2∣z)]+[P(y3∣x3,z)+P(x3∣z)−P(x3,y3∣z)]+P(x1,y1∣z)−2,[P(y1∣x1,z)+P(x1∣z)−P(x1,y1∣z)]+[P(y3∣x3,z)+P(x3∣z)−P(x3,y3∣z)]+P(x2,y2∣z)−2,[P(y1∣x1,z)+P(x1∣z)−P(x1,y1∣z)]+[P(y2∣x2,z)+P(x2∣z)−P(x2,y2∣z)]+P(x3,y3∣z)−2×P(z) _z \ array[]c0,\\ P(y_1 x_1,z)+P(y_2 x_2,z)\\ +P(y_3 x_3,z)-2,\\ [P(y_2 x_2,z)+P(x_2 z)\\ -P(x_2,y_2 z) ]+ [P(y_3 x_3,z)\\ +P(x_3 z)-P(x_3,y_3 z) ]\\ +P(x_1,y_1 z)-2,\\ [P(y_1 x_1,z)+P(x_1 z)\\ -P(x_1,y_1 z) ]+ [P(y_3 x_3,z)\\ +P(x_3 z)-P(x_3,y_3 z) ]\\ +P(x_2,y_2 z)-2,\\ [P(y_1 x_1,z)+P(x_1 z)\\ -P(x_1,y_1 z) ]+ [P(y_2 x_2,z)\\ +P(x_2 z)-P(x_2,y_2 z) ]\\ +P(x_3,y_3 z)-2 array \× P(z) ≤PNS(k) ≤ PNS(k) ∑zminP(x1,y1∣z)+P(x2,y2∣z)+P(x3,y3∣z),P(y1∣x1,z),P(y2∣x2,z),P(y3∣x3,z),[P(y1∣x1,z)−P(x1,y1∣z)+P(y2∣x2,z)−P(x2,y2∣z)],[P(y1∣x1,z)−P(x1,y1∣z)+P(y3∣x3,z)−P(x3,y3∣z)],[P(y2∣x2,z)−P(x2,y2∣z)+P(y3∣x3,z)−P(x3,y3∣z)],12[P(y1∣x1,z)−P(x1,y1∣z)+P(y2∣x2,z)−P(x2,y2∣z)+P(y3∣x3,z)−P(x3,y3∣z)]×P(z) _z \ array[]cP(x_1,y_1 z)+P(x_2,y_2 z)\\ +P(x_3,y_3 z),\\ P(y_1 x_1,z),\\ P(y_2 x_2,z),\\ P(y_3 x_3,z),\\ [P(y_1 x_1,z)-P(x_1,y_1 z)\\ +P(y_2 x_2,z)-P(x_2,y_2 z) ],\\ [P(y_1 x_1,z)-P(x_1,y_1 z)\\ +P(y_3 x_3,z)-P(x_3,y_3 z) ],\\ [P(y_2 x_2,z)-P(x_2,y_2 z)\\ +P(y_3 x_3,z)-P(x_3,y_3 z) ],\\ 12 [P(y_1 x_1,z)-P(x_1,y_1 z)\\ +P(y_2 x_2,z)-P(x_2,y_2 z)\\ +P(y_3 x_3,z)-P(x_3,y_3 z) ] array \× P(z) ≥PNS(k) ≥ PNS(k) After applying all the required data we obtained before, we can derive 0≤PNS(3)≤0.033. 0≤ PNS(3)≤ 0.033. Example 2: Blood glucose as a pure mediator From Table 2, we can collect all data we want. Since each cell in the table represents the joint count n(x,y,z)n(x,y,z), we obtain P(z∣x)=∑yn(x,y,z)∑z,yn(x,y,z).P(z x)= _yn(x,y,z) _z,yn(x,y,z). That is, for a fixed X=xX=x, we first sum over Y within each level Z=zZ=z and then divide by the total number of individuals with X=xX=x. Similarly, P(y∣z)=∑xn(x,y,z)∑x,yn(x,y,z).P(y z)= _xn(x,y,z) _x,yn(x,y,z). That is, for a fixed Z=zZ=z, we sum over X for each outcome Y=yY=y and then divide by the total number of individuals in the stratum Z=zZ=z. P(z1∣x1) P(z_1 x_1) =2830, = 2830, P(z2∣x1) P(z_2 x_1) =130, = 130, P(z3∣x1) P(z_3 x_1) =130, = 130, P(z1∣x2) P(z_1 x_2) =1930, = 1930, P(z2∣x2) P(z_2 x_2) =830, = 830, P(z3∣x2) P(z_3 x_2) =330, = 330, P(z1∣x3) P(z_1 x_3) =130, = 130, P(z2∣x3) P(z_2 x_3) =730, = 730, P(z3∣x3) P(z_3 x_3) =2230. = 2230. P(y1∣z1) P(y_1 z_1) =1630, = 1630, P(y2∣z1) P(y_2 z_1) =1330, = 1330, P(y3∣z1) P(y_3 z_1) =130, = 130, P(y1∣z2) P(y_1 z_2) =230, = 230, P(y2∣z2) P(y_2 z_2) =2730, = 2730, P(y3∣z2) P(y_3 z_2) =130, = 130, P(y1∣z3) P(y_1 z_3) =630, = 630, P(y2∣z3) P(y_2 z_3) =330, = 330, P(y3∣z3) P(y_3 z_3) =2130. = 2130. Following the example, we can apply Thm. 10: minPNSUB,minP(y1∣z1),P(y2∣z2),P(y3∣z3)×minP(z1∣x1),P(z2∣x2),P(z3∣x3)++minP(y1∣z1),P(y2∣z3),P(y3∣z2)×minP(z1∣x1),P(z3∣x2),P(z2∣x3)++minP(y1∣z2),P(y2∣z1),P(y3∣z3)×minP(z2∣x1),P(z1∣x2),P(z3∣x3)++minP(y1∣z2),P(y2∣z3),P(y3∣z1)×minP(z2∣x1),P(z3∣x2),P(z1∣x3)++minP(y1∣z3),P(y2∣z1),P(y3∣z2)×minP(z3∣x1),P(z1∣x2),P(z2∣x3)++minP(y1∣z3),P(y2∣z2),P(y3∣z1)×minP(z3∣x1),P(z2∣x2),P(z1∣x3) \ array[]cPNS_UB,\\ \\ \P(y_1 z_1),P(y_2 z_2),P(y_3 z_3)\×\\ \P(z_1 x_1),P(z_2 x_2),P(z_3 x_3)\\\ +\\ + \P(y_1 z_1),P(y_2 z_3),P(y_3 z_2)\×\\ \P(z_1 x_1),P(z_3 x_2),P(z_2 x_3)\\\ +\\ + \P(y_1 z_2),P(y_2 z_1),P(y_3 z_3)\×\\ \P(z_2 x_1),P(z_1 x_2),P(z_3 x_3)\\\ +\\ + \P(y_1 z_2),P(y_2 z_3),P(y_3 z_1)\×\\ \P(z_2 x_1),P(z_3 x_2),P(z_1 x_3)\\\ +\\ + \P(y_1 z_3),P(y_2 z_1),P(y_3 z_2)\×\\ \P(z_3 x_1),P(z_1 x_2),P(z_2 x_3)\\\ +\\ + \P(y_1 z_3),P(y_2 z_2),P(y_3 z_1)\×\\ \P(z_3 x_1),P(z_2 x_2),P(z_1 x_3)\ array \ ≥PNS(3) ≥ PNS(3) By applying the data, we have: min0.507,min1630,2730,2130×min2830,830,2230+min1630,330,130×min2830,330,730+min230,1330,2130×min130,1930,2230+min230,330,130×min130,330,130+min630,1330,130×min130,1930,730+min630,2730,130×min130,830,130 \ array[]c0.507,\\ \ 1630, 2730, 2130 \× \ 2830, 830, 2230 \\\[5.69054pt] + \ 1630, 330, 130 \× \ 2830, 330, 730 \\\[5.69054pt] + \ 230, 1330, 2130 \× \ 130, 1930, 2230 \\\[5.69054pt] + \ 230, 330, 130 \× \ 130, 330, 130 \\\[5.69054pt] + \ 630, 1330, 130 \× \ 130, 1930, 730 \\\[5.69054pt] + \ 630, 2730, 130 \× \ 130, 830, 130 \ array \ = = min0.507,1630830+130330+230130+130130+130130+130130 \ array[]c0.507,\\ \\ 1630 830+ 130 330+ 230 130+ 130 130+ 130 130\\ \\ + 130 130 array \ = = 0.151. 0.151. Hence, we can conclude: 0≤PNS(3)≤0.151. 0 (3)\ ≤ 0.151. Simulation Algorithm We used the following algorithm to generate samples and conduct the simulations. Q selects the causal quantity; G and Z select the structure. Every theorem in the paper is one choice of (Q,G,Z)(Q,G,Z). Following 10, we use the same procedure to generate the conditional probability tables. Algorithm 1 Generate simulation data for Q under G Input: Number of output samples n Input: Causal diagram G Input: Variable to condition on Z Input: Quantity Q, where Input: Q∈PNS(k),PSub(k,p), Q∈\PNS(k),PSub(k,p), Input: PRep(k,q),PN(k,p,q) (k,q),PN(k,p,q)\ Output: List of 4-tuples containing the general Output: lower bound, graph-based lower bound, Output: graph-based upper bound, and general Output: upper bound 1: for i←1i← 1 to n do 2: cpt←generate-cpt(G,Exp(1))cpt← generate-cpt(G,Exp(1)) 3: // General (Shu et al.) lower and upper bounds 4: (lb,ub)←q-bounds(Q,cpt)(lb,ub)← q-bounds(Q,cpt) 5: // Graph-based lower and upper bounds 6: (lbG,ubG)←q-graph(Q,cpt,G,Z)(lb_G,ub_G)← q-graph(Q,cpt,G,Z) 7: append-result(lb,lbG,ubG,ub) append-result(lb,lb_G,ub_G,ub) 8: end for 9: return output list