  We formalize the notion of nesting probabilistic programming queries and
investigate the resulting statistical implications. We demonstrate that while
query nesting allows the definition of models which could not otherwise be
expressed, such as those involving agents reasoning about other agents,
existing systems take approaches which lead to inconsistent estimates. We show
how to correct this by delineating possible ways one might want to nest queries
and asserting the respective conditions required for convergence. We further
introduce a new online nested Monte Carlo estimator that makes it substantially
easier to ensure these conditions are met, thereby providing a simple framework
for designing statistically correct inference engines. We prove the correctness
of this online estimator and show that, when using the recommended setup, its
asymptotic variance is always better than that of the equivalent fixed
estimator, while its bias is always within a factor of two.
