Say we have a guide program which induces a probability distribution G(x). 

F = ΣxP(x)f(x) ≥ Σx|G(x)>0G(x)P(x)f(x)/G(x) =
 <f(x)P(x)/G(x)>G
That is, our sum is greater than or equal to the expected value under G of f(x)P(x)/G(x), with equality coming when G(x) is positive for all x such that f(x)P(x) is non-zero. We can therefore sample from G and use the samples f(x)P(x)/G(x) to find statistical lower bounds for F. Our problem is now that of heuristically finding a G that lets us efficiently prove a good statistical lower bound on F. A test for this is given in [Breth et al.].

We search for a guide algorithm which lets us quickly prove as great a lower bound as we can on F. A trivial guide which sampled from the priors would have the correct mean <f(x)P(x)/G(x)>G = F, but the variance could be so great that it could take exponentially long to statistically prove a good lower bound on F. A 
perfect guide here would be one which f(x)P(x)/G(x) = F for all x. 

Note that in general, estimation of the numerator and the denominator from the right hand side of equation 1 have different perfect guides. 

## Extra Guide Choices

It might sometimes be easier for the guide to specify extra choices not made by the model program. Say our model is that a monkey types a string of a million random characters, and the evidence is that the text of this paper occurs somewhere in the string. One good guide would first choose a position in the string for this paper to occur. It would then guide the choices of those characters to contain the characters of this paper and leave the rest random. The system so far described forbids us from counting the probability of the choice of starting position in computing G(x). This is because we have no proof that different values of extra choices made by the guide lead to different execution paths of the model program. Thus we could end up underestimating G(x) and hence overestimating F. To solve this problem, we introduce the idea of model extensions. Before making an extra choice y, the guide program extends the model from a distribution over x to one over (x,y) by specifying a function for the conditional distribution PG(y|x) in terms of the complete execution path x. The guide program then provides a distribution G(y) and the choice of y is chosen from it. At the end of the execution of the model program, we can compute PG(x,y) = P(x)PG(y|x) and G(x,y) = G(x)G(y). We do importance sampling on the distribution PG(x,y) using G(x,y) as the proposal distribution. PG(x,y) marginalizes to P(x), so the expectation of any function of x is unchanged.

In the case of the prolific monkey, y is the position at which our paper will appear in the monkey's output. The guide makes G(y) the uniform distribution over all possible starting positions. The guide sets PG(y|x) to a function of the execution path x that returns the position of the first occurrence of our paper in the output. 

We extend this method to making multiple extra choices. The guide program has a command to insert an extra choice yi at any point in the execution. If the model choices made so far are (x1...xj) and the extra guide choices made so far are (y1...yi-1) the guide program specifies a distribution G(yi|x1..xj,y1..yi-1) 
from which the choice is actually made, and a function from the complete execution path x to a conditional distribution PG(yi|x,y1...yi-1). If we consider y to be the sequence of extra choices (y1...yn) made over the course of he execution, then we are drawing from G(x,y) and we can at the end compute PG(x,y) = P(x)PG(y1|x)...PG(yn|x,y1...yn-1). So, as above, we can do importance sampling over PG(x,y) using G(x,y) 
as a proposal distribution. Since PG(x,y) marginalizes to P(x), we can use this to sample from P(x).

## Acknowledgments

Thanks to Jeremy Bem for introducing us to program induction, Sergey Pankov to importance sampling, and Noah Goodman, Vikash Mansinghka, Daniel Roy for a discussion on extra choices.

## References

Breth, M., Maritz, J. and Williams, E. (1978). On distribution-free lower confidence limits for the mean of a nonnegative random variable. Biometrika 65 529-534.

Jordan, M.I., Ghahramani, Z., Jaakkola, T.S. and Saul, L.K. (1999). *An Introduction to Variational Methods for* Graphical Models. In Machine Learning, 37, \#2, 183-233. Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, San Mateo, CA: Morgan Kaufmann.