1$ there is $c'$ such that for all $t>0$ \[ w^{\mu}(t) \le w^{\mu}(ct) \le c' \cdot w^{\mu}(t). \] The second step would derive from this property the extension of Theorem~\ref{th:BL}. We don't know if any of these two steps is valid. We can weaken the claim of Theorem~\ref{th:BL} in a different way, while maintaining it for all measures. For example, it is plausible that the upper bound in the theorem holds for a subset of numbers $n \in \Nbb$ of positive density. On the other hand we do not know if there is a measure for which the bound of Theorem~\ref{th:BL} is valid only for a finite number of natural numbers. \section{Proof of Theorem~\ref{th:BLgen}}\label{sec:proofBLgen} Let $\mu$ be a probability measure in $\Rbb^d$. For better readability we drop all superscripts~$\mu$. \subsection{Lower bound}\label{p:lowerbound} \begin{proof} The proof of the lower bound is similar to the one in the convex-body case. For every fixed point $x\in W_t$, by definition, there exists a half-space $h$ with $x\in h$ and $\mu(h)\le t$. If $h\cap P_{n}$ is empty, then $x$ is not in $P_{n}$, and therefore, for $x\in W_t$, \begin{equation}\label{A.} \Pr[x\notin P_{n}] \ge \Pr[h\cap P_{n}=\emptyset] = (1-\mu(h))^{n}\ge (1-t)^{n}. \end{equation} Then, for any $t$, \[ \begin{aligned} 1-\Ebb [\mu(P_{n})] & = \int_{x\in \Rbb^d} \Pr[x \notin P_{n}]\dd\mu(x) \\ & \ge \int_{x\in W_t} \Pr[x \notin P_{n}]\dd\mu(x)\\ & \ge \int_{x\in W_t}(1-t)^{n} \dd\mu(x) = (1-t)^{n} w(t). \end{aligned} \] We choose $t=1/n$. Since the sequence $(1-\frac1n)^{n}$ is increasing, for $n \ge 2$ we have $1-\Ebb [\mu(P_{n})] \ge \frac14 w\left(\mtfrac1n\right)$. \end{proof} %%\bigskip To obtain the analogous lower bound from Theorem~\ref{th:fvector}$\MK$\eqref{list.1.4.1}, we write \[ \Ebb\ptb{f_0(P_n)} = n\Ebb\ptb{1-\mu(P_{n-1})} \ge n(1-t)^{n-1} w(t). \] Again, choosing $t=1/n$ yields the claimed lower bound \[ \Ebb\ptb{f_0(P_n)} \ge n\pth{1-\frac1n}^{n-1} w\left(\mtfrac1n\right)\ge {\frac1e}nw\left(\mtfrac1n\right), \] since the sequence $(1-\frac1n)^{n-1}$ is now decreasing to ${\frac1e}$. \subsection{Floating bodies and \texorpdfstring{$\eps$}{eps}-nets}\label{s:epsnet} Before we turn our attention to the upper bound, we will point out a connection to $\eps$-nets. Consider a probability space $(U,\mu)$ and a family $\Hcal$ of measurable subsets of $U$. An \emph{$\eps$-net} for $(U, \mu, \Hcal)$ is a set $S\subseteq U$ that intersects every $h\in \Hcal$ with $\mu(h)\ge \eps$~\cite[Section~10.2]{Mat}. In the special case where $U=(\Rbb^d,\mu)$ and $\Hcal$ consists of all half-spaces, if a set $S$ is an $\eps$-net, then the convex hull $P$ of $S$ contains $\Rbb^d\setminus W_\eps$. Indeed, assume that there exists a point $x$ in $\Rbb^d\setminus W_\eps$ and not in $P$. Consider a closed halfspace $h$ that contains $x$ and is disjoint from $P$. Since $x \notin W_\eps$ we must have $\mu(h) > \eps$ and $S$ cannot be an $\eps$-net. We call the region $\Rbb^d\setminus W_\eps$ the \emph{floating body} of the measure $\mu$ with parameter $\eps$, by analogy to the case of convex bodies. The relation between floating bodies and $\eps$-nets was first observed by Van Vu, who used the $\eps$-net Theorem to prove that $P_n^{\mu}$ contains $\Rbb^d \setminus W_{c\log n/n}$ with high probability~\cite[Lemma~4.2]{VanVu} (a fact previously established by Bárány and Dalla~\cite{BD} when $\mu$ is the normalized Lebesgue measure on a convex body). This implies that, with high probability, $1-\mu(P_n)\le w(c\log n/n)$. The analysis we give in Section~\ref{sec:upperbound} refines Vu's analysis to sharpen the constant. Note that Theorem~\ref{th:example} shows that Vu's result is already asymptotically best possible. \subsection{Upper bound}\label{sec:upperbound} For $d=1$, the proof of the upper bound is straightforward and may actually be improved. Indeed, we have $w(t)=\min\{2t,1\}$, and Efron's Formula~\eqref{eq:Efron2} yields \[ \Ebb\ptb{1-\mu(P_n)} \le \frac1{n+1} \Ebb\ptb{f_0(P_{n+1})} \le \frac2{n+1} \le w\pth{\frac{1}{n+1}} \le w\pth{3 \frac{\ln n}{n}}. \] We will therefore assume $d\ge2$. We use a lower bound on the probability of a random sample of $U$ to be an $\eps$-net for $(U, \mu, \Hcal)$. We define the \emph{shatter function} (or growth function) of the family $\Hcal$ as \[ \pi_{\Hcal}(N) = \max_{X\subseteq U, |X|\le N} |\{\, X\cap h : h \in \Hcal\,\}|, \] \begin{lemm}[{\cite[Theorem~3.2]{KPW}}]\label{lemma-shatter} Let $(U,\mu)$ be a probability space and $\Hcal$ a family of measurable subsets of $U$. Let $X_s$ be a sample of $s$ random independent elements chosen according to $\mu$. For any integer $N> s$, the probability that $X_s$ is not a $\eps$-net for $(U,\mu,\Hcal)$ is at most \begin{equation} \nonumber 2\pi_{\Hcal}(N) \cdot \left(1-\mtfrac{s}{N}\right)^{(N-s)\eps-1}. \end{equation} \end{lemm} Lemma~\ref{lemma-shatter} is a quantitative refinement of a foundational result in learning theory~\cite[Theorem~2]{VC}. It is commonly used to prove that small $\eps$-nets exist for range spaces of bounded Vapnik--Chervonenkis dimension~\cite{HW}, see also~\cite[Theorem~3.1]{KPW} or~\cite[Theorem~15.5] {Pach}. For that application, it is sufficient to show that the probability of failure is less than 1; this works for $\eps\approx d \ln n/n$ (with appropriate lower-order terms), where $d$ is the Vapnik--Chervonenkis dimension. In our proof, we will need a smaller failure probability of order $o(1/n)$, and we will achieve this by setting $\eps\approx (d+2) \ln n/n$. We will apply the lemma in the case where $U = \Rbb^d$ and $\Hcal$ is the set of halfspaces in~$\Rbb^d$. We mention that by increasing $\eps$ more aggressively, the probability of failure can be made exponentially small. For the family $\Hcal$ of halfspaces in $\Rbb^d$, we have the following sharp bound on the shatter function~\cite{Harding}: \[ \pi_{\Hcal}(N)\le 2\sum_{i=0}^{d} \binom{N-1}i. \] \begin{proof} The proof of the upper bound of Theorem~\ref{th:BLgen} starts by remarking that for any $\eps \in [0,1]$ we have: \begin{align*} \Ebb\ptb{1-\mu(P_n)} & = \int_{\Rbb^d} \Pr[x \notin P_{n}]\dd\mu(x)\\ & = \int_{\Rbb^d \setminus W_\eps} \Pr[x \notin P_{n}]\dd\mu(x) + \int_{W_\eps} \Pr[x \notin P_{n}]\dd\mu(x) \\ & \le \int_{\Rbb^d \setminus W_\eps} \Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}]\dd\mu(x) + \int_{W_\eps}\dd\mu(x)\\ & \le \Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}] + w(\eps). \end{align*} Here, the first inequality between the probabilities holds since the event $x \notin P_{n}$ trivially implies that $\Rbb^d \setminus W_\eps \not\subseteq P_{n}$ when $x\in \Rbb^d \setminus W_\eps$. We thus have \[ \Ebb\ptb{1-\mu(P_n)} \le w(\eps) + \Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}]. \] We now want to set $\eps$ so that $\Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}]$ is $\frac{\eps_d(n)}{n}$ with $\eps_d(n) \to 0$ as $n \to \infty$. As shown in Section~\ref{s:epsnet}, the event $\Rbb^d \setminus W_\eps \not\subseteq P_{n}$ implies that $P_{n}$ fails to be an $\eps$-net. The probability can thus be bounded from above using Lemma~\ref{lemma-shatter} with $s=n$. Taking logarithms, for any $N > n$, \[ \ln \Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}] \le \ln \pi_{\Hcal}(N) + \pth{(N-n)\eps-1} \ln \left(1-\mtfrac{n}{N}\right) + \ln 2. \] Since we assume that $d\ge 2$, we have \[ \pi_{\Hcal}(N) \le 2\sum_{i=0}^{d} \binom{N-1}i\le N^d \quad \text{and} \quad \ln\pi_{\Hcal}(N) \le d \ln N. \] We set $N = n \lceil \ln n \rceil$, so that: \[ \ln \Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}]\le d \ln n + d\ln \lceil \ln n \rceil+\pth{(N-n)\eps-1}\ln \left(1-\mtfrac{n}{N}\right) + \ln 2. \] We then set $\eps = \delta \frac{\ln n}{n}$, with $\delta \approx d$ to be fine-tuned later. If $n$ is large enough, the factor $\pth{{(N-n)\eps-1}}\approx \delta\ln^2 n$ is nonnegative, and we can use the inequality $\ln(1-x) \le -x$ for $x \in [0,1)$ in order to bound the second term: \begin{align*} \pth{(N-n))\eps-1} \ln \left(1-\mtfrac{n}{N}\right) &\le- \bigl({(N-n)\eps-1}\bigr)\frac{n}{N}\\ & = -n\eps +\frac{n}{\lceil \ln n \rceil}\eps +\frac1{\lceil \ln n \rceil} \\ &\le - \delta \ln n +\delta + 1. \end{align*} Altogether, we get \[ \Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}] \le 2^{\delta+1}e \cdot n^{d-\delta}\lceil \ln n \rceil^d \] so for every $\delta > d+1$ we have $\Pr[\Rbb^d \setminus W_\eps \not\subseteq P_{n}] = \frac{\eps_d(n)}{n}$ with $\eps_d(n) \to 0$ as $n \to \infty$. Setting $\delta=d+2$ yields the claimed bound. \end{proof} \section{Proof of Theorem~\ref{th:example}}\label{sec:example} In this section, logarithms are base~$2$. For better readability we drop the superscripts $\nu$. \subsection{The construction} The measure $\nu$ is supported on a sequence of concentric circles $C_1, C_2, \dots,$ where $C_i$ has radius \[ r_i=1-\frac1{i+1}. \] On each $C_i$, $\nu$ is uniform, implying that $\nu$ is rotationally invariant. We let $D_i=\bigcup_{j \ge i} C_j$. For $i \ge 1$ we put \[ \nu(D_i)= s_i := 4 \cdot 2^{-2^i} \] and remark that $\nu(\Rbb^2) = s_1 = 1$, so $\nu$ is a probability measure. The sequence $\{s_i\}_{i \in \Nbb}$ decreases very rapidly. The probabilities of the individual circles are \[ p_i:=\nu(C_i)=s_i-s_{i+1}=4\cdot\pth{2^{-2^i}-2^{-2^{i+1}}} =s_i\pth{1-\frac{s_i}4}\approx s_i, \] for $i\ge1$. The infinite sequence of values $n$ for which we claim the inequality of Theorem~\ref{th:example}~is \[ n_i :=2^{2^i+2i} \approx \mtfrac 1{s_i} \log^2 \mtfrac 1{s_i}. \] In Section~\ref{wet}, we examine the wet part and prove that $\wet{\mtfrac{\log n_i}{n_i}}\le s_i$. We then want to establish the complementary bound $\Ebb\ptb{1-\nu(P_{n_i})}> s_i/2$. Since $\nu$ is non-atomic, Efron's formula yields \[ \Ebb\ptb{1-\nu(P_{n_i })} = \frac1{n_i+1} \Ebb\ptb{f_0(P_{n_i+1)}} \] and it suffices to establish that $\Ebb\ptb{f_0(P_{n_i+1})} > (n_i+1) s_i/2$. This is what we do in Section~\ref{random}. \subsection{The wet part}\label{wet} Let us again drop the superscript $\nu$. Let $h_i$ be a closed halfplane that has a single point in common with $C_i$, so its bounding line is tangent to $C_i$. We have \[ \wet{t}=s_{i} \text{, \ for } \nu(h_{i}) \le t < \nu(h_{i-1}). \] So, as $t$ decreases, $\wet t$ drops step by step, each step being from $s_i$ to $s_{i+1}$. In particular, \begin{equation}\label{eq:drops-one} \wet {t}\le s_{i} \iff t< \nu(h_{i-1}). \end{equation} For $j > i$, the portion of $C_j$ contained in $h_i$ is equal to $2\arccos(r_i/r_j)$. Hence, \[ \nu(h_i\cap C_j)=\frac{\arccos(r_i/r_j)}{\pi} \cdot p_j. \] We will bound the term $\arccos(r_i/r_j)$ by a more explicit expression in terms of~$i$. To get rid of the $\arccos$ function, we use the fact that $\cos x \ge 1-x^2/2$ for all $x\in\Rbb$. We obtain, for $0\le y\le1$, \[ \arccos (1-y)\ge \sqrt{2y}. \] Moreover, the ratio ${r_i}/{r_{j}}$ can be bounded as follows: \[ \frac{r_i}{r_j}\le\frac{r_i}{r_{i+1}} =\frac i{i+1} \Bigm/\frac {i+1}{i+2} = 1-\frac{1}{(i+1)^2}. \] Thus we deduce that \[ \frac{\arccos(r_i/r_j)}{\pi} \ge\frac{\arccos(1- 1/{(i+1)^2})}{\pi} \ge \frac{\sqrt{2}}{\pi(i+1)}. \] We have established a bound on ${\arccos(r_i/r_j)}/{\pi}$, which is the fraction of a single circle $C_j$ that is contained in $h_i$. Hence, considering all circles $C_j$ with $j>i$ together, we get \[ \nu(h_i)\ge \frac{\sqrt{2}}{\pi(i+1)}s_{i+1}. \] We check that for $i\ge 4$, \[ \frac{\log n_i}{n_i}=\frac{2^{i}+2i}{2^{2^i+2i}} =2^{-2^i}2^{-2i} (2^{i}+2i) =\frac{s_i}4 2^{-i}(1+2^{1-i}i)< s_i \frac{\sqrt{2}}{\pi i}\le \nu(h_{i-1}), \] because $2^{-i}(1+2^{1-i}i) < \frac{\sqrt{2}}{\pi i}$ for all $i\ge 4$. Using~\eqref{eq:drops-one}, this gives our desired bound: \[ w\left(\mtfrac{\log n_i}{n_i}\right) \le s_i, \] for all $i\ge 4$. With little effort, one can show that actually $\wet {\mtfrac{\log n_i}{n_i}} = s_i$. One can also see that, for any $C>0$, the condition $\wet {C\mtfrac{\log n_i}{n_i}}\le s_i $ holds if $i$ is large enough, because the exponential factor $2^{-i}$ dominates any constant factor~$C$ in the last chain of inequalities. This justifies the remark that we made after the statement of Theorem~\ref{th:example}. \subsection{The random polytope}\label{random} Assume now that $X_n$ is a set of $n$ points sampled independently from $\nu$. We intend to bound from below the expectation $\Ebb\ptb{f_0(\conv X_{n_i+1})}$. Observe that for any $n \in\Nbb$ one has \[ \Ebb|X_n\cap C_i|=np_i\quad\text{and}\quad \Pr(X_n\cap D_{i+1}=\emptyset)=(1-s_{i+1})^n. \] Intuitively, as $n$ varies in the range near $n_i$, many points of $X_n$ lie on $C_i$ and yet no point of $X_n$ lies in $D_{i+1}$. So $P_n$ has, in expectation, at least $np_i \approx ns_i$ vertices. At the same time, the term $\wet {\log n/n}$ in the claimed lower bound drops to $s_i$. So the expected number of vertices is about $ns_i$ which is larger than $\frac 12 ns_i=\frac n2 \wet {\log n/n}$. \goodbreak \begin{proof} Formally, we estimate the expected number of vertices when $n=n_i+1$: \begin{align*} \Ebb\ptb{f_0(\conv X_{n_i+1})} &\ge\Ebb\ptb{f_0(\conv X_{n_i+1})\mid X_{n_i+1}\cap D_{i+1}=\emptyset} \cdot \Pr(X_{n_i+1}\cap D_{i+1}=\emptyset)\\ &\ge\Ebb[|X_{n_i+1}\cap C_i|]\cdot(1-s_{i+1})^{n_i+1}\\ &=(n_i+1)p_i(1-s_{i+1})^{n_i+1}\\ &=(n_i+1)s_i\left[\frac {p_i}{s_i}(1-s_{i+1})^{n_i+1}\right] \end{align*} The last square bracket tends to 1 as $i \to \infty$. In particular, it is larger than~$\frac 12$ for $i \ge 4$. This shows that for all $i\ge 4$ \[ \Ebb\ptb{f_0(\conv X_{n_i+1})}>\frac 12 (n_i+1)s_i \ge \frac 12(n_i+1)w\left(\mtfrac{\log n_i} {n_i}\right). \qedhere \] \end{proof} \subsection{Higher dimension} We can embed the plane containing $\nu$ in $\Rbb^d$ for $d \ge 3$. The analysis remains true but the random polytope is of course flat with probability~1. To get a full-dimensional example, we can replace each circle by a $(d-1)$-dimensional sphere, all other parameters being kept identical: all spheres are centered in the same point, $C_i$ has radius $1-\frac{1}{i+1}$, the measure is uniform on each $C_i$ and the measure of $\cup_{j \ge i} C_i$ is $4 \cdot 2^{-2^i}$. The analysis holds \emph{mutatis mutandis}. As another example, which does not require new calculations, we can combine $\nu$ with the uniform distribution on the edges of a regular $(d-2)$-dimensional simplex in the $(d-2)$-dimensional subspace orthogonal to the plane that contains the circles, mixing the two distributions in the ratio $50:50$. In all our constructions, the measure is concentrated on lower-dimensional manifolds of $\Rbb^d$, circles, spheres, or line segments. If a continuous distribution is desired, one can replace each circle in the plane by a narrow annulus and each sphere by a thin spherical shell, without changing the characteristic behaviour. \section{An alternative treatment of atomic measures}\label{sec:alternative} Even for measures with atoms, one can give a precise meaning to Efron's formula: The expression in~\eqref{eq:Efron0} counts the expected number of convex hull vertices of $P_n$ that are unique in the sample $X_n$. From this, it is obvious that Efron's formula~\eqref{eq:Efron} is a lower bound on $\Ebb[f_0(P_n)]$~\eqref{eq:Efron2}. For dealing with atomic measures, there is an alternative possibility. The resulting statements involve different quantities than our original results, but they have the advantage of holding for every measure. We denote by $\bar f_0(X_n)$ the number of points of the sample $X_n$ that lie \emph{on the boundary} of their convex hull $P_n $, counted with multiplicity in case of coincident points. We denote by $\breve P_n $ the interior of $P_n $. Then a derivation analogous to \thetag{\ref{eq:Efron0}--\ref{eq:Efron}} leads to the following variation of Efron's formula: %~\eqref{eq:Efron}: \begin{equation}\label{eq:Ef-open} \Ebb [\bar f_0(X_n)] =n(1-\Ebb [\mu(\breve P_{n-1})]) \end{equation} We emphasize that we mean the boundary and interior with respect to the ambient space $\Rbb^d$, not the \emph{relative} boundary or interior. Even for some non-atomic measures, this gives different results. Consider the uniform distribution on the boundary of an equilateral triangle. Then $\Ebb[\bar f_0(X_n)]=n$, while $\Ebb[f_0(P_n)]\le 6$. Accordingly, $\Ebb [\mu(\breve P_{n})]=0$, while $\Ebb [\mu(P_{n})]$ converges to~$1$. We denote the closure of the wet part $W_t^{\mu}$ by $\bar W_t^{\mu}$ and its measure by $\bar w^{\mu}(t)=\mu(\bar W_t^{\mu})$. With these concepts, we can prove the following analogs of Theorems~\ref{th:BLgen}--\ref{th:fvector}. Observe that for a measure $\mu$ for which for every hyperplane $H$, $\mu(H)=0$ the content of this theorem is the same as the previous ones. \begin{theo}\ \\*[-1.2em] \begin{enumerate}\romanenumi \item \label{list.5.1.1} For any probability measure $\mu$ in $\Rbb^d$ and $n \ge 2$, \begin{equation}\label{eq:closed-wet} \mtfrac 14 \bar w^{\mu}\left(\mtfrac1n\right) \le {\Ebb[1-\mu(\breve P_n^\mu)]} \le \bar w^{\mu}\left((d+2)\mtfrac{\ln n}n\right) + \mtfrac{\varepsilon_d(n)}{n}, \end{equation} and \begin{equation}\label{eq:boundary-f0} \mtfrac 1e n \bar w^{\mu}\left(\mtfrac1n\right) \le \Ebb\ptb{\bar f_0(X_n^\mu)} \le n \bar w^{\mu}\left({(d+2)\mtfrac{\ln n}n}\right) + \varepsilon_d(n), \end{equation} where $\varepsilon_d(n)\to 0$ as $n\to+\infty$ and is independent of $\mu$. \item \label{list.5.1.2} There is a non-atomic probability measure $\nu$ on $\Rbb^2$ such that \[ \Ebb[1-\mu(\breve P_n^\nu)] > \mtfrac 1{2} \cdot \bar w^\nu(\log_2 n/ n) \] and \[ \Ebb\ptb{\bar f_0(X_n^\nu)} > \mtfrac 1{2} n \cdot \bar w^\nu({\log_2 n/ n}) \] for infinitely many $n$. \end{enumerate} \end{theo} \begin{proof}[Proof sketch] Since the derivation is parallel to the proofs in Sections~\ref{sec:proofBLgen}--\ref{sec:example}, we only sketch a few crucial points. \begin{proof}[\eqref{list.5.1.1}] For proving the lower bound in~\eqref{eq:closed-wet}, we modify the initial argument leading to~\eqref{A.}: For every fixed $x\in W_t$, there is a \emph{closed} half-space $h$ with $x\in h$ whose corresponding open halfspace $\breve h$ has measure $\mu(\breve h)\le t$. Therefore, \[ \Pr[x\notin \breve P_{n}] \ge \Pr[h\cap \breve P_{n}=\emptyset]= \Pr[\breve h\cap P_{n}=\emptyset] = (1-\mu(\breve h))^{n}\ge (1-t)^{n}. \] The remainder of the proof can be adapted in a straightforward way. In Section~\ref{s:epsnet}, we have established that for an $\eps$-net $S$, its convex hull $P$ contains $\Rbb^d\setminus W_\eps$. Since the interior operator is monotone, this implies that $\Rbb^d\setminus \overline{W}_\eps \subseteq\breve P$. Therefore, the $\eps$-net argument of Section~\ref{sec:upperbound} applies to the modified setting and establishes the upper bound in~\eqref{eq:closed-wet}. Finally, by Efron's modified formula~\eqref{eq:Ef-open}, the result~\eqref{eq:closed-wet} carries over to~\eqref{eq:boundary-f0} as in our original derivation. \let\qed\relax \end{proof} \begin{proof}[\eqref{list.5.1.2}] The lower-bound construction of Theorem~\ref{th:example} gives zero measure to every hyperplane, and therefore all quantities in part~\eqref{list.5.1.2} are equal to the corresponding quantities in Theorem~\ref{th:example} and Theorem~\ref{th:fvector}$\MK$\eqref{list.1.4.2}. \end{proof} \let\qed\relax \end{proof} %%\bigskip \bibliography{AHL_Barani} \end{document}