Corollary 1  If g(X) >0, then the optimal probability density function is

$$f(\mathbf{X})={\frac{g(\mathbf{X})}{I}}$$
$$a n d\ \sigma_{\,f({\bf x})}^{2}\,=\,0.$$

Although in practice sampling from precisely f(X) = g(X)/I will occur rarely, we expect that functions that are close enough to it can still reduce the variance effectively. Usually, the closer the shape of the function f ( X ) is to the shape of the function g ( X ), the smaller is σ 2 (x). In high-dimensional integrals, selection of the importance function, f (X), is far more critical than increasing the number of samples, since the former can dramatically affect σ i (x). It seems prudent to put more energy in oosing an importance function whose shape is as close as possible to that of g(X) than to apply the brute force method of increasing the number of samples It is worth noting here that if f ( X ) is uniform, importance sampling becomes a general Monte Carlo sampling. Another noteworthy property of importance sampling that can be derived from Equation 4 is that we should avoid f(X) ≪ | g(X) - I  f(X)| in any part of the domain of sampling, even if f ( X ) matches well g ( X )/I in important regions.  If f(X) ≪ |g(X) - I  f(X)|, the variance can become very large or even infinite.  We can avoid this by adjusting f ( X ) to be larger in unimportant regions of the domain of X .

While in this section we discussed importance sampling for continuous variables, the results stated are valid for discrete variables as well, in which case integration should be substituted by summation.

## 2.2  A Generic Importance Sampling Algorithm For Bayesian Networks

In the following discussion, all random variables used are multiple-valued, discrete variables.

Capital letters, such as A, B, or C, denote random variables. Bold capital letters, such as A, B, or C, denote sets of variables. Bold capital letter E will usually be used to denote the set of evidence variables. Lower case letters a, b, c denote particular instantiations of variables A, B, and C respectively. Bold lower case letters, such as a, b, c, denote particular instantiations of sets A, B, and C respectively.  Bold lower case letter e, in particular, will be used to denote the observations, i.e., instantiations of the set of evidence variables E. Anc(A) denotes the set of ancestors of node A. Pa(A) denotes the set of parents (direct ancestors) of node A. pa( A ) denotes a particular instantiation of Pa( A ). \ denotes set difference. Pa(A)lE=e denotes that we use the extended vertical bar to indicate substitution of e for E in A.

We know that the joint probability distribution over all variables of a Bayesian network model, Pr(X), is the product of the probability distributions over each of the nodes conditional on their parents, i.e.,

$$\operatorname*{Pr}(\mathbf{X})=\prod_{i=1}^{n}\operatorname*{Pr}(X_{i}|\operatorname{Pa}(X_{i}))\ .$$
$$\left({\bar{0}}\right)$$

In order to calculate Pr(E = e), we need to sum over all Pr(X\E,E = e).

$$\operatorname*{Pr}\left(\mathbf{E}=\mathbf{e}\,\right)=\sum_{\mathbf{X}\setminus\mathbf{E}}\operatorname*{Pr}\left(\mathbf{X}\setminus\mathbf{E}\,,\,\mathbf{E}\,=\mathbf{e}\,\right)$$
$${\mathrm{ver~all~Pr}}(\mathbf{X}\backslash\mathbf{E},\mathbf{E}=\mathbf{e}).$$
$$\left({\mathfrak{h}}\right)$$
$$159$$
