Inequality Methods

Inequality methods provide lower or upper bounds for the true integral value.

Let $P(t) = T_k(-{\bf t},{\bf t};{\bf R},\nu)$, and define $A_j = \{ {\bf x}: \vert(C{\bf x})_j\vert \leq t \}$. In order to be consistent with other methods we assume the constraint matrix $C$ has been scaled so that $C{\bf R}C^t$ is a correlation matrix. If we let

$$S_1(t) = \sum_{j=1}^q Prob(A_j^c(t)),$$

where $A_j^c(t)$ is the compliment of the set $A_j(t)$, then the Bonferroni lower bound for $P(t)$ (see Hsu, 1996) is

$$L^{(1)}(t) = 1-S_1(t) \leq P(t).$$

A simple upper bound for $P(t)$ is

$$P(t) \leq 1- \min_j Prob(A_j^c(t)) = U^{(1)}(t).$$

Both of these bounds require only 1-dimensional distribution values. If $t^{(1)}_l$ and $t^{(1)}_u$ are determined by solving $U^{(1)}(t) = 1-\alpha$ and $L^{(1)}(t) = 1-\alpha$, respectively, then $t^{(1)}_l \leq t_{1-\alpha} \leq t^{(1)}_u$. The bounding interval for $t_{1-\alpha}$ can be found directly using the appropriate 1-dimensional inverse distribution function:

$$[t^{(1)}_l, t^{(1)}_u] = [t_\nu^{-1}(1-\frac{\alpha}{2}),t_\nu^{-1}(1-\frac{\alpha}{2q})],$$

where $t_\nu(u) = \frac{\Gamma(\frac{\nu+1}{2})}{\Gamma(\frac{\nu}{2})\sqrt{\nu\pi}} \int_{-\infty}^u (1+\frac{s^2}{\nu})^{-\frac{\nu+1}{2}}ds$.

Shorter bounding intervals can be found using bivariate distribution values (Dunnett and Sobel, 1954) if a modified Bonferroni bound (Dawson and Sankoff, 1967) is combined with the Hunter-Worsley bound. These bounds are described the book by Hsu (1966, Appendix A). If we define $S_2(t)$ by

$$S_2(t) = \sum_{j<i} Prob(A_j^c(t)\cap A_i^c(t)),$$

then the modified Bonferroni bounds and Hunter-Worsley guarantee that

$$L^{(2)}(t) = 1 - S_1(t) + \sum_{(i,j)\in T^*} Prob(A_j^c(t)\cap A_i^c(t))$$

$$\leq P(t) \leq 1-2\frac{S_1(t)-S_2(t)/k}{k+1} = U^{(2)}(t).$$

where $k = 1 + \lfloor 2S_2(t)/S_1(t)\rfloor$ and $T^*$ is maximal spanning tree for the complete graph of order $q$ with edge weights $Prob(A_j^c(t)\cap A_i^c(t))$. If we determine $t^{(2)}_l$, $t^{(2)}_u$ that satisfy $U^{(2)}(t^{(2)}_l) = 1-\alpha$ and $L^{(2)}(t^{(2)}_u) = 1-\alpha$, then $t^{(1)}_l \leq t^{(2)}_l \leq t_{1-\alpha} \leq t^{(2)}_u \leq t^{(1)}_u$. Starting with $[t^{(1)}_l, t^{(1)}_u]$, we use numerical optimization, applied to $L^{(2)}(t)$, to determine $t^{(2)}_u$. Then we use numerical optimization, applied to $U^{(2)}(t)$, starting with $[t^{(1)}_l, t^{(2)}_u]$, to determine $t^{(2)}_l$.

Even shorter bounding intervals for $t_{1-\alpha}$ can be determined for many problems if trivariate distribution values are used. If we define $S_3(t)$ by

$$S_3(t) = \sum_{k<j<i} Prob(A_k^c(t)\cap A_j^c(t)\cap A_i^c(t)),$$

then sharp bounds that use $S_1(t)$, $S_2(t)$ and $S_3(t)$ (see Boros and Prekopa, 1989) are given by

$$L^{(3)}(t)= 1 - S_1(t) + 2\frac{(2j-1)S_2(t)-3S_3(t)}{j(j+1)},$$

and

$$U^{(3)}(t) = 1-\frac{(i+2q-1)S_1(t)-2((2i+q-2)S_2(t)-3S_3(t))/i}{q(i+1)},$$

where $i = 1 + \lfloor 2((q-2)S_2(t)-3S_3(2))/((q-1)S_1(t)-2S_2(t))\rfloor$ and $j = 2 + \lfloor 3S_3(t)/S_2(t)\rfloor$. We can use numerical optimization applied to $L^{(3)}(t)$ and $U^{(3)}(t)$, to determine $t^{(3)}_u$ and $t^{(3)}_l$. Unfortunately, it is not always true that $L^{(2)}(t)\leq L^{(3)}(t)$, so we cannot assume that $t^{(3)}_u$ will be closer to $t_{1-\alpha}$ than $t^{(2)}_u$. However, Boros aand Prekopa (1989) show that $U^{(3)}(t)\leq U^{(2)}(t)$, so $t^{(3)}_l$ will be at least as close to $t_{1-\alpha}$ as $t^{(2)}_l$. The cost of computing $S_3(t)$ can be quite high for problems where $q$ is large because of the $q(q-1)(q-2)/6$ trivariate values needed for $S_3(t)$.

There are also bounds (hybrid bounds) that use only selected trivariate distribution values. The cherry tree bounds (see Bukszar and Prekopa, 2001), which we denote by $L^{(2,3)}(t)$, are lower bounds for $P(t)$ that require only $q-2$ trivariate values. The optimal cherry tree bound can be expensive to compute, but we use a bound defined by

$$L^{(2,3)}(t) = L^{(2)}(t) + \sum_{(i,j)\in T^{**}}(Prob(A_j^c(t)\cap A_i^c(t)) -Prob(A_{k_{(i,j)}}^c(t)\cap A_j^c(t)\cap A_i^c(t))),$$

The edge set $T^{**}$ contains $q-2$ of the $q-1$ edges in the $L^{(2)}(t)$ bound edge set $T^*$. For each edge in $T^{**}$ the vertex $k_{(i,j)}$ is selected using the method described by Bukszar and Prekopa (2001). We always have $L^{(2,3)}(t) \geq L^{(2)}(t)$ because $Prob(A_j^c(t)\cap A_i^c(t)) \geq Prob(A_{k_{(i,j)}}^c(t)\cap A_j^c(t)\cap A_i^c(t))$. If we let $t^{(2,3)}_u$ be the point where $L^{(2,3)}(t) = 1-\alpha$, then $t_{1-\alpha} \leq t^{(2,3)}_u \leq t^{(2)}_u \leq t^{(1)}_u$.

A class of hybrid upper bounds has been described by Tomescu (1986). Define

$$U^{(2,3)}(t) = 1 - S_1(t) + S_2(t) - \sum_{E(T_q^3)}Prob(A_k^c(t)\cap A_j^c(t)\cap A_i^c(t)),$$

where $E(T_q^3)$ is the set of $(q-1)(q-2)/2$ hyperedges $(i,j,k)$ for a 3-hypertree. Tomescu shows that $P(t) \leq U^{(2,3)}(t)$. The optimal hypertree bound can also be expensive to compute because all possible trivariate distribution values are needed. We use a bound determined using $T^*$. We successively delete $q-2$ terminal vertices from $T^*$. Each time a terminal vertex $k$ (along with its edge) is deleted, that vertex is adjoined to each of the remaining $T^*$ edges to form a set of hyperedges. The union of the sets of $q-2, q-3, \ldots, 1$ hyperedges found in this way form the hypertree $T_q^3$ that we use for $U^{(2,3)}(t)$. This bound is always less than or equal to the second order Bonferroni $1 - S_1(t) + S_2(t)$ bound but is not necessarily less than or equal to $U^{(2)}(t)$ or $U^{(3)}(t)$. We define $t^{(2,3)}_l$ to be the point where $U^{(2,3)}(t) = 1-\alpha$.