I've been reading about convex volume estimation, and have found the paper "Simulated Annealing in Convex Bodies and an $O^{*}(n^4)$ Volume Algorithm" by Lovasz and Vempala, which can be read here.
The algorithm provided relies the standard multi-phase monte-carlo technique of producing a series of values, the first of which is easy to compute, the remainder estimatable by random variables, and then combining each of these variables in some way to produce an estimate of the volume. This particular technique involves extruding an $n$-dimensional shape into an $n+1$-dimensional pencil, and estimating the volume of that pencil. The pencil is defined as the intersection of a cylinder over the convex body and a cone. Let $K$ be the convex body, and
$$ C = \{{\bf x} \in \mathbb{R}^{n+1} | x_0 > 0, \; \sum^n_{i=1}x_i^2 \leqslant x_0^2\} $$ The pencil, $K'$, is defined: $$ K' = ([0,2D] \times K) \cap C $$
By assumption, $K$ contains the unit ball, so the set of points in $K'$ with $x_0<1$ is exactly the $n+1$-dimensional hypercone with height $1$ and whose base is the $n$-ball of radius $1$. This cone is referred to as $C_B$. We also denote by $\pi_n$ the volume of the unit n-ball. The estimates of the volume of the pencil are provided using the following function:
$$ Z(a) = \int_{K'} e^{-ax_0} d{\bf x} $$
For a sufficiently small value of $a$, $Z(a)$ can be shown to be a good estimate for the volume of $K'$. For $a \geqslant 2n$, it is claimed that $Z(a)$ is close to the above integral taken over the entire cone $C$. We know that $K' \subseteq C$ from its definition, hence
$$ Z(a) = \int_{K'} e^{-ax_0} d{\bf x} \leqslant \int_{C} e^{-ax_0} d{\bf x} = \int_0^\infty e^{-at}t^n \pi_n dt = n! \pi_n a^{-(n+1)} $$
We know also that $C_B \subseteq K'$, hence
$$ Z(a) \geqslant \int_{C_B} e^{-ax_0} d{\bf x} = \int_0^1 e^{-at}t^n \pi_n dt $$
At this point, I can no longer follow the paper's reasoning. It is stated that
$$ \int_0^1 e^{-at}t^n \pi_n dt > (1-\varepsilon) \int_0^\infty e^{-at}t^n \pi_n dt $$
No bounds are specified on $\varepsilon$. Indeed, our estimation algorithm should be able to take an arbitrarily small value of $\varepsilon$. The integrand, hovever, is non-negative across its domain of integration, so it must be the case that
$$ \int_0^1 e^{-at}t^n \pi_n dt \leqslant \int_0^\infty e^{-at}t^n \pi_n dt $$
Surely, then, the inequality in $\varepsilon$ would only hold for a sufficiently large value of $\varepsilon$, rather than for an arbitrarily small one. Further, stating that $a\geqslant 2n$ gives no information about a relationship between $\varepsilon$ and $a$. How is it even possible to reach the conclusion from the premise in this case? Further still, an independent talk on the algorithm found here suggests instead that the inequality only holds for $a>6n$, rather than $a>2n$. The paper states that this is true by standard computation, so I do feel that I must be missing something here, but I cannot tell what.
I've emailed both of the authors at the email addresses I can find for them, and haven't received any response from them, so hopefully someone from here can help.
