  The challenge of simulating random variables is a central problem in
Statistics and Machine Learning. Given a tractable proposal distribution $P$,
from which we can draw exact samples, and a target distribution $Q$ which is
absolutely continuous with respect to $P$, the A* sampling algorithm allows
simulating exact samples from $Q$, provided we can evaluate the Radon-Nikodym
derivative of $Q$ with respect to $P$. Maddison et al. originally showed that
for a target distribution $Q$ and proposal distribution $P$, the runtime of A*
sampling is upper bounded by $\mathcal{O}(\exp(D_{\infty}[Q||P]))$ where
$D_{\infty}[Q||P]$ is the Renyi divergence from $Q$ to $P$. This runtime can be
prohibitively large for many cases of practical interest. Here, we show that
with additional restrictive assumptions on $Q$ and $P$, we can achieve much
faster runtimes. Specifically, we show that if $Q$ and $P$ are distributions on
$\mathbb{R}$ and their Radon-Nikodym derivative is unimodal, the runtime of A*
sampling is $\mathcal{O}(D_{\infty}[Q||P])$, which is exponentially faster than
A* sampling without assumptions.
