Conditional Multi-variate Normal Distribution I would like to find a computationally quick and sufficiently accurate way (i.e., either analytically or numerical approximation) to compute a conditional probability for a specific multi-variate normal distribution, which is defined as follows:
Let $X_1, \dots, X_n$ be n independent (univariate) normal random variables. And let $A_1, \dots, A_k$ be defined as sums of subsets of those random variables, i.e.,:
$\forall i: A_i = \sum_{j \in S} X_j$, where $S \subseteq \{1,\dots, n\}$.
I am looking for the following conditional probabilities of $A_i$:
Pr[ $A_i \leq x$ | $A_j \leq t$ $\forall j \in C$ and $j \neq i$ ], where $x$ is any number smaller than $t$, and $C \subseteq \left\{ 1,...,k \right\}$ is a subset of all possible variable indices on which the probability is conditioned. So the condition is on several $A_j$'s.
To the best to my knowledge, the conditional density of a multi-variate normal density is generally not a (uni-variate) normal distribution. I tried via Monte-Carlo simulation, but approximation is not sufficiently accurate when using 500,000 samples, 2000 bins (to classify the results) for a "problem" with 50 random variables, i.e. n=50.
Analytically that doesn't seem to be trivial. I have asked quite a few Statisticians around me and so far we haven't found a solution.
 A: Let $X \sim \mathcal N(\mu \mathbf 1, \sigma^2 I)$ be your $X_i$ stacked up into a vector. Then $A_i = w_i X$, where $w_i = \left[ \mathbb 1(x_j \in S_i) \right]_j$ is the binary membership vector corresponding to the $i$th sum.
The joint distribution of $A_i$ and $A_j$ is then, using the distribution of an affine transformation of a multivariate normal:
\begin{align}
\begin{bmatrix}A_i \\ A_j\end{bmatrix}
&= \begin{bmatrix} w_i^T \\ w_j^T \end{bmatrix} X
\\&\sim \mathcal N\left( \begin{bmatrix} w_i^T \\ w_j^T \end{bmatrix} \mu \mathbf 1, \begin{bmatrix} w_i^T \\ w_j^T \end{bmatrix} \sigma^2 I \begin{bmatrix} w_i & w_j \end{bmatrix}\right)
\\&= \mathcal N\left( \mu \begin{bmatrix} w_i^T \mathbf 1 \\ w_j^T \mathbf 1 \end{bmatrix}, \sigma^2 \begin{bmatrix} \lVert w_i \rVert^2 & w_i^T w_j \\ w_j^T w_i & \lVert w_j \rVert^2 \end{bmatrix} \right)
\\&= \mathcal N\left( \mu \begin{bmatrix} n_i \\ n_j \end{bmatrix}, \sigma^2 \begin{bmatrix} n_i^2 & n_{ij} \\ n_{ij} & n_j^2 \end{bmatrix} \right)
\end{align}
where $n_i = \lvert S_i \rvert$ and $n_{ij} = \lvert S_i \cap S_j \rvert$.
Your desired entries are then computable from the CDF of a bivariate normal, available in various standard programming environments:
$$\Pr(A_i \le s \mid A_j \le t) = \frac{\Pr(A_i \le s, A_j \le t)}{\Pr(A_j \le t)}.$$

If you need to condition on multiple variables, you can easily extend this in exactly the same way. For example, 
\begin{align}
\begin{bmatrix}A_i \\ A_j \\ A_k\end{bmatrix}
&= \mathcal N\left( \mu \begin{bmatrix} n_i \\ n_j \\ n_k \end{bmatrix}, \sigma^2 \begin{bmatrix} n_i^2 & n_{ij} & n_{ik} \\ n_{ij} & n_j^2 & n_{jk} \\ n_{ik} & n_{jk} & n_k^2 \end{bmatrix} \right)
\end{align}
and
$$\Pr(A_i \le s \mid A_j \le t, A_k \le r) = \frac{\Pr(A_i \le s, A_j \le t, A_k \le r)}{\Pr(A_j \le t, A_k \le r)}.$$
