Conveniently, we can separate the one-run free energy for a run into one term for each call to the choose function or the evidence function. F(G, P, E, x) is the sum of

 For each call to the choose function, log(GC(c)/PC(c)), 
where c is the value that was chosen, PC(c) is the probability of that choice according to the distribution provided by the model, and GC(c) is the probability of that choice according to the distribution provided by the guide.

 For each call evidence(p) to the evidence function, 
-log(p)
So we have a very easy way of computing the one-run free energy. Furthermore, we can assign credit/blame to the particular parts of the program that contribute to the onerun free energy. This could prove useful in directing our optimization efforts.

If GX = PX|e , we call G a **perfect guide**. For example, the guide shown above for example 1 happens to be a perfect guide. If G is a perfect guide, here are some interesting facts:

 The free energy F(G, P, e) = -log(P(e)) , the smallest possible value.

 The one run free energy is the same for every possible execution path x. F(G, P, e, x) = -
log(P(e))
(the converse is not true - a constant one-run free energy does not imply a perfect guide)
 Across different runs, the constant one-run free energy separates into terms in very different ways.

 For every call to the choose function, the guide distribution for that choice GC is equal to the posterior distribution for that choice PC|e

## Guided Sampling With Rejection

So far, we have only dealt with guides that always work. 

In practice, for a given guide program, the model program or the guide program could occasionally crash or exhaust our computing resources, or the one-run free energy could sometimes be very low. This isn't a reason to dismiss that guide program entirely. Say we reject the runs where either the program crashed or where the one-run free energy exceeded some threshold specified in the guide program. Accepting only the successful runs induces its own distribution G'X over execution paths. Let the acceptance rate A(G) be the fraction of runs that are accepted. For any accepted execution path x, G'X (x) = GX (x) / A(G)
F(G', P, e, x) = F(G, P, e, x) - log(A(G))
So to estimate the free energy of G', we compute the average value of F(G, P, e, x) over the non-rejected samples, and subtract the log of the observed acceptance rate. 

## Other Utility Metrics For Guide Programs

In addition to favoring guide programs with lower free energy, we may want to favor guide programs which make life easier for us in other ways - most notably by costing us fewer computing resources to sample from. For example, a guide program that just echoes the model program's priors and then rejects at the end with probability (1-P(e|x)) 
has an optimal free energy, but is very expensive to sample from. So we define a utility on guide programs U(G) = F(G, p, e) + k * (average time to successfully extract a sample from G) + other terms and we optimize for that instead. k here is a constant representing our level of impatience.

## Pros And Cons Of Guided Sampling

Guided sampling can be seen as an extension of maximum likelihood search (searching for the most likely execution path). The two methods are identical if we restrict our search for guides to "deterministic" guides that always provide single-point distributions for every choice. As such, guided sampling shares some of the the advantages of maximum likelihood search. In particular 1. It can yield incremental results 2. The results are measurable. 3. It can be easily parallelized across computers and across search heuristics. 

On the negative side:
1. Guided sampling is more complicated than maximum likelihood search. 

2. It requires repeated sampling to produce and verify results.

## Importance Sampling

There may be something better we can do with a guide program. Say we are trying to compute the conditional probability of a hypothesis h(x) given the evidence e 
(rather than just wanting to sample from PX|e *per se*). 

Instead of a 0/1 boolean, we can let h(x) be any positive function and we will try to determine its conditional expected value given e. Recall equation 1:
 (1) E(h(x)|e) = ΣxP(x) P(e|x) h(x) / ΣxP(x) P(e|x)
This is the quotient of two sums of the form F = ΣxP(x)f(x)
where f(x) is an easily computable non-negative function. These sums can be very time-consuming to compute exactly. To approximate them, we turn to importance sampling. Importance sampling will allow us to statistically prove lower bounds on the two sums. 

While this proves nothing about their quotient, we believe this can often yield a good estimate.