Detecting random sets by samplings from their values
We examine the extent to which random samplings from the values of a random set, determine the distribution of the random set itself. We also comment on how, given the statistics of the sampling, to detect the distribution. Several methods are displayed, leading to positive results, counter-examples, and open problems.
\section{Introduction}\label{S1}
Random sets are random variable with the variables being subsets of a given, say metric, 
space. The mathematics of random sets offers both geometrical and combinatorial challenges, 
emerging, at times, from applications, including in morphology, pattern analysis, data 
analysis, econometrics, and more. For the theory and applications of random sets, consult 
the comprehensive presentations, and references therein, in Chui, Stoyan, Kendall and Mecke
\cite{ChStKeMe13}, Molchanov \cite{Mol17}, Molchanov and Molinari \cite{MolMol18}, Nguyen 
\cite{Ngu06}, and the workshop proceedings Goutsias, Mahler and Nguyen (editors) \cite{GoMaNg97}.

The mathematical question we address in this paper has not been looked at, so it seems, in the 
literature. It alludes to a situation where samples from the values of the random set are given, 
but not the random set itself. Eventually, one may wish to exploit the samples from the
values of the random sets for the inference of properties of the random set, or even to detect
the distribution of the random set. To this end, the correspondence between the distribution of 
the random set and the distribution of the samples from its values, should be one-to-one.
This is not always the case. A challenge, therefore, is to identify conditions under which the 
distribution of samples, which we refer to as the statistics of samples, determines the 
distribution of the random set. When the samples determine the distribution,
algorithms are sought, that identify, or at least approximate, the distribution. In the 
next section we display, via some easy to follow examples and comments, what are the issues. 
In particular, we show that in order to achieve the goals, one-point sample may not be enough, 
while $m$-point statistics may determine the distribution. Then the challenge is to find the 
smallest such $m$. 

The inference issue itself is not address in the present paper. The results introduced
here, in addition to the mathematical interest they offer, should help create a reliable
inference procedures.

In Section 3 we display the general technical setting, and mention some conditions
that will be of help when reaching general positive results. In Section 4 we concentrate on
the case of random intervals in the real line. The geometrical structure of intervals 
yields quite general positive results, yet, the general question concerning random intervals
is still open. A procedure, named the peeling property, is introduced in Section 5.
When holds, it helps in detecting the distribution of the random set. Finitely supported 
random sets are examined in Section 6. Combinatorial arguments help to state a general
criterion, and to identify, in some specific families of random sets, the smallest $m$ for 
which the $m$-point statistics determines the distribution. In the closing section we
examine the possibility to find a generalization of the interval-valued results, in
convex-valued random sets in higher dimensions. A counter-example is given, yet, for some
families of random convex-valued sets, an $m$ for which $m$-point statistics determines
the distribution exists, and can be computed. A general criterion is still not available,


\section{Comments and examples}\label{S2}

We offer in this section some easy to follow examples, and comments, demonstrating the 
mathematical issues and challenges examined in the paper. The first example is concerned 
with a random compact interval in the real line. 

\begin{example}\label{Exa2.1}
Consider two random intervals. One with distribution being the probability measures 
$\hbox{\boldmath\char'026}_1$ supported on the interval $[1,3]$ (namely, a random set with a constant value). 
The second, with distribution $\hbox{\boldmath\char'026}_2$ equally split between the intervals $[1,2]$ and 
$[2,3]$. Suppose that once an interval is chosen according to one of the distributions,
the sampling from that interval is taken according to the normalized Lebesgue measure.
\end{example}
 
In the previous example, the distributions of the $1$-point sampling of the two 
distributions coincide. It is the uniform distribution over $[1,3]$. In fact, the same 
statistics results from many random intervals, e.g., any convex combination of the two
distributions, namely $\hbox{\boldmath\char'026} = \alpha \hbox{\boldmath\char'026}_1 + (1 - \alpha)\hbox{\boldmath\char'026}_2 $, with  
$0 \le \alpha \le 1$. We conclude that the $1$-point sampling in this example does
not determine that distribution of the random interval. 

The situation is different when the statistics of the $2$-point sampling is revealed, 
namely, at each stage two points are sampled, independently, from the interval. Then 
the statistics of the $2$-point sample for $\hbox{\boldmath\char'026}_1$, is the uniform distribution over 
the square $[1,3]^2$ in $R^2$, while the corresponding statistics for $\hbox{\boldmath\char'026}_2$ is
the uniform distribution over the union of $[1,2]^2$ and $[2,3]^2$, see Figure 1.
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{Figure1}
\caption{}
\end{figure}
We conclude that in this example, between $\hbox{\boldmath\char'026}_1$ and $\hbox{\boldmath\char'026}_2$, the $2$-point 
statistics determines the distribution of the random interval. In fact, it is easy 
to see that the $2$-point statistics of any random interval with values being the 
three intervals in Example \ref{Exa2.1}, determines the distribution of the
random interval. 

In Section 4 we verify, the not so obvious claim, that when the sampling is done
according to the normalized Lebesgue measure, the statistics of the $2$-point sampling
determines the distribution of any compact-valued random interval. A similar result
holds for other sampling rules, as follows.

\begin{example}\label{Exa2.2}
Consider two random intervals with distributions being probability measures $\hbox{\boldmath\char'026}_1$ 
and $\hbox{\boldmath\char'026}_2$, where $\hbox{\boldmath\char'026}_1$ is equally distributed between the two intervals $[1,2]$ 
and $[3,4]$, and $\hbox{\boldmath\char'026}_2$ is equally split between $[1,3]$ and $[2,4]$. Suppose that
the sampling rule is that given an interval, the two end points of it are chosen with
equal probabilities. 
\end{example}

The $1$-point statistics for both $\hbox{\boldmath\char'026}_1$ and $\hbox{\boldmath\char'026}_2$ in Example \ref{Exa2.2}
is equally distributed among the points $1, 2, 3$ and $4$. In particular, this statistics
does not determine the distribution. The statistics of the $2$-point sample, however, 
reveals the distribution of the random set. Indeed, the statistics of $\hbox{\boldmath\char'026}_1$ is equally
distributed among the points $\{(x,y): x = 1, 2, y = 1,2\}$ and
$\{(x,y): x = 3, 4, y = 3, 4\}$, and the statistics of $\hbox{\boldmath\char'026}_2$ is equally distributed
among the points $\{(x,y): x = 1, 3, y = 1,3\}$ and $\{(x,y): x = 2, 4, y = 2, 4\}$.

In Section 4 we prove a general result, relating to Example \ref{Exa2.2}, namely,
that when the sampling is among the end points of the interval, the $2$-point
statistics determines the distribution. 

Thus, the Examples \ref{Exa2.1} and \ref{Exa2.2} give rise to general positive results.
A general characterization of random intervals for which the $2$-point statistics 
determines the random interval, is still not available.   

Once an $m$-point statistics determines a distribution of a random set, one may
seek an algorithm to actually construct or at least to approximate the distribution.
It is easy to construct this distribution in the two previous examples. We do display 
algorithms that approximate the distribution for a general random interval with
the sampling rules as in the two example.

It is clear that in both Examples \ref{Exa2.1} and \ref{Exa2.2}, the fact that
the intervals are $1$-dimensional, plays a role (and the same will probably be
for the aforementioned characterization). One may ask whether a similar general result  
holds for random $2$-dimensional compact convex-valued, random sets. We give a
counter-example in Section 7, namely, a random set with convex and compact values, where
for no $m$ the $m$-point statistics determines the distribution. Under further restrictions
on the geometry of the values, one may establish positive results. We demonstrate it, yet, 
a general result for families in higher-dimensional spaces is still not known.




\section{The setting}\label{S3}
We display here, and comment on, the general technical framework we work in. Specific
assumptions may be needed when specific results are presented.

The notions we use are standard. Definitions, explanations, and elaborations, can be
found in Molchanov \cite{Mol17}. Relevant information on probability measures can also be
found in Ash \cite{Ash72}, and Billingsley \cite{Bil99}. We may abuse, slightly, rigorous
terminology, as we refer to the notions of probability measure, distribution, and, at times,
statistics, as synonymous terms. No confusion should arise.

For convenience, we recall some definitions. Weak convergence of measures $\nu$, on a
complete separable metric space $Y$, is characterized by the continuity of the mapping
$\int_Y b(y) \nu(dy)$, into the real line, this for every $b(y)$, real valued, bounded, 
and continuous mapping. Another characterization, of the weak convergence
of, say, $\nu_i$ to $\nu_0$, is that $\nu_i(B)$ converge to $\nu_0(B)$, whenever $B$ is
a Borel set with $\nu_0(\partial B) =0$ (here $\partial B$ is the boundary of $B$).
Although we are concerned primarily with probability measures, the weak convergence is
applicable to general finite measures, and we shall use it that way. The weak convergence
is metrizable, for instance, with the Prokhorov metric. We shall allude to a metric, since
we do not need to adhere to a specific metric. The family of probability measures supported
on a prescribed compact set in $Y$, is compact with respect to the weak convergence.

The Hausdorff distance of two compact subsets, say $A$ and $B$, of a metric space $Y$,
is denoted by $haus(A,B)$, and given by
\begin{equation}\label{Eq3.1}
haus(A,B)  = \max (\max_{a \in A}\min_{b \in B} d(a,b),  \max_{b \in B}\min_{a \in A} d(a,b)),
\end{equation}
where $d(a,b)$ is the distance in $Y$ between $a$ and $b$. The family of compact subsets
of a compact set in $Y$, is compact with respect  to the Hausdorff metric.

A random set is a measurable mapping from a probability measure space into a collection of
sets. In this paper, the values of the random sets are compact subsets of a complete
separable metric space $X$ (often taken as $R^n$, the
$n$-dimensional Euclidean space). We denote by $\Kscr$ the family of compact subsets of $X$,
endowed with the Hausdorff metric. We consider $\Kscr$ with its  Borel field. In fact, what
matters to us is the distribution of the values of the random set, which is represented by a
probability measure, say $\hbox{\boldmath\char'026}$, on $\Kscr$.

As mentioned, our goal is to find out whether the distribution, say $\hbox{\boldmath\char'026}$, of a random
set, is determined by samplings from the values of the random set. To that end, for each
$K \in \Kscr$, a probability measure $P_K$ on $X$, supported on $K$ is prescribed, according
to which, points in $K$ are sampled. We refer to $P_K$ as the {\sl sampling rule.} The
following are two useful properties.
\begin{property}\label{Prty3.1}
The measures $P_K$ depend continuously on $K$.
\end{property}
\begin{property}\label{Prty3.2}
For every compact set $C$, the mapping $P_K(C)$ is measurable in the variable $K$.
\end{property}
The continuity and measurability alluded to in the previous properties is with respect to
the Hausdorff metric on $\Kscr$. They are useful as they allow a variety of
analytical tools. The continuity of $P_K$ implies, via the aforementioned
characterization of weak convergence, that for every compact set $C$ the mapping
$P_K(C)$ is upper semi-continuous, hence measurable. Hence, the first property
implies the second one.

The continuity property may not hold even in natural examples. For instance, the Lebesgue
measure (or rather, the normalized Lebesgue measure) on a set is not continuous with respect
to the Hausdorff distance. It is easy to see, though, that the measurability property
holds. Clearly, the continuity and measurability properties hold trivially when the
distribution of the random set is supported on a finite number of sets.

A useful class of sampling rules is as follows.
\begin{definition}\label{Def3.3}
We say that the sampling rule $P_K$ for the subsets of $X$  is {\sl regular}, if
there exists a positive measure $\gamma$ on $X$ (not necessarily
a probability measure), such that when $C$ is a subset of $K$ with $\gamma(K) > 0$,
then $P_K(C) = {\gamma(C) \over \gamma(K)}$.
\end{definition}
A regular sampling rule $P_K$ may not be continuous. It is easy to see, however, that
it posses the measurability  Property \ref{Prty3.2}.

The samples in our model are formed by a random choice of, say $m$, points in $K$, sampled
consequently and independently according to the distribution $P_K$. Equivalently, for
$K \in \Kscr$, denote by $K^m$ the $m$-times product $K^m = K \times K \times ... \times K$,
and by $P_K^m$ the $m$-times product of $P_K$ on $K^m$. Then the $m$-point sample
amounts to choosing a point in $K^m$, randomly with respect to $P_K^m$. Thus, by first
choosing $K$ randomly according to $\hbox{\boldmath\char'026}$, then choosing an $m$-sample randomly according
to $P_K^m$, we get a point in $X^m$. The distribution of these points on $X^m$, which is
a probability measure on $X^m$, is the {\sl statistics of the $m$-sampling}, denoted $S_m(\hbox{\boldmath\char'026})$.

Thus, to say that the statistics determines the distribution, on a given domain of distributions, 
means that $S_m(\hbox{\boldmath\char'026})$ is one-to-one in the domain.

In general, given the distribution $\hbox{\boldmath\char'026}$ of a random set, and the sampling rules $P_K$, the
statistics of the random $m$-samples from $K \in \Kscr$ is the probability measure $S_m(\hbox{\boldmath\char'026})$
on $X^m$, given by integrating the measures $P_K^m$ on $X^m$, according to $\hbox{\boldmath\char'026}$. Namely, for
every Borel set $H \subseteq X^m$, the value $S_m(\hbox{\boldmath\char'026})(H)$ is given by
\begin{equation}\label{Eq3.2}
S_m(\hbox{\boldmath\char'026})(B) = \int_\Kscr P_K^m(H)~\hbox{\boldmath\char'026}(dK).
\end{equation}
For (\ref{Eq3.2}) to make sense, we need that for each Borel set $H$ the real-valued
map $P_K^m(H)$ be measurable. For the results in this paper, it is enough that the Borel 
field on $X^m$ be generated by sets $H$ of the form $H = B_1 \times ... \times B_m$, where 
each $B_i$ is a compact subset of $X$, and since each measure on $X^m$ is determined by 
its values on such sets, it is enough to consider (\ref{Eq3.2}) on such sets (then the 
measurability for every Borel $H$ can be easily deduced).

The statistics $S_m$ depends, of course, on the probability measures $P_K$.
We suppress this dependence from the notation. No confusion is likely to arise.
As stated, the $m$-point statistics is a probability measure on $X^m$, namely,
on ordered strings of points in $X$. It is also possible to consider the
sample as a subset of $X$ of size $m$. Simple combinatorial adjustments to the
arguments should then be done. We do not address this possibility here.

In this paper we address primarily the determination issue. The possibility to
construct the random set, is displayed in comments that follow the positive results below.

The following observations are listed for further reference.
\begin{lemma}\label{Lem3.4}
Let $\Kscr_0$ be a compact collection of compact subsets of $X$. Then, \\
$(1)$ If for each compact set $C$ the real valued mapping $P_K(C)$ is measurable, then
for every $m$, the mapping $P_K^m(H)$ is measurable for every set $H$ which is the product
of compact sets (namely, of the form $H = C_1 \times ... \times C_m$,
where each $C_i$ is a compact subset of $X$). \\
$(2)$ If $P_K$ is continuous on $\Kscr_0$, then $P_K^m$ is continuous on the space
of $K^m$, for $K \in \Kscr_0$. Consequently, for each compact set $C$, the real
valued mapping $P_K(C)$ is measurable, and, for every set $H$ of the form
$H = C_1 \times ... \times C_m$, where each $C_i$ is a compact subset of $X$,
$P_K^m(H)$ is measurable. \\
$(3)$ If $P_K$ is continuous on $\Kscr_0$, then
$S_m(\cdot)$ is continuous (as a mapping from probability measures on $\Kscr_0$, to
the space of probability measures on $X^m$).
\end{lemma}
\begin{proof}
Item $(1)$ is trivial, as $P_K^m(H)$ is the product of $m$ measurable functions.
When  $P_K$ is continuous, the continuity of $P_K^m$ can be deduced from an iterated
Fubini's Theorem. Also, it is easy to see that for each compact set $B$ the
function $P_k(B)$ is upper semicontinous, hence measurable, and likewise
for $P_K^m (H)$.

For verifying $(3)$, we show that if $\mu_j$ converge weakly to $\mu_0$, then
$S_m(\mu_j)$ converge weakly to  $S_m(\mu_0)$. For convenience, we show it first for $m = 1$.
The latter convergence holds if $S_1(\mu_j)(B)$ converge to  $S_1(\mu_0)(B)$ whenever
$S_1(\mu_0)(\partial B) = 0$. For such a set $B$, the equality, in view of (\ref{Eq3.2}),
implies that $P_K(\partial B) = 0$, except possibly on a set in $\Kscr_0$ of $\mu_0$-measure
zero. Denote the latter set by $\Kscr_1$. The continuity of $P_K$ implies then that
$P_K(B)$ is continuous in $K$, except possibly at the set $\Kscr_1$. Now, cover the
set $\Kscr_1$ by a compact neighborhood, say $\Uscr_\varepsilon$ (i.e., a closure of an open set),
whose $\mu_0$-measure is small, say $\varepsilon$. The mapping $P_K(B)$ can now be changed on
$\Uscr_\varepsilon$ to make a continuous function bounded by $1$, say $P_K(B)_\varepsilon$  on $\Kscr_0$.
The convergence of $\mu_j$ to $\mu_0$ implies then that $\int_{\Kscr_0} P_K(B)_\varepsilon \mu_j(dK)$
converge to $\int_{\Kscr_0} P_K(B)_\varepsilon \mu_0(dK)$. Since $\varepsilon$ is arbitrarily small,
and since $\mu_j$ converge weakly to $\mu_0$ and $\mu_0(\Uscr_\varepsilon) \le \varepsilon$,
it follows that $\int_{\Kscr_0} P_K(B) \mu_j(dK)$ converge to $\int_{\Kscr_0} P_K(B) \mu_0(dK)$.
The latter convergence is what we need to verify for $S_1(\mu_j)$ to converge weakly to  
$S_1(\mu_0)$. The arguments for the case $m > 1$ are the same. This completes the proof.
\end{proof}
\begin{corollary}\label{Cor3.5}
Let $\Kscr_0$ be a compact collection of compact subsets of $X$, and let $\Mscr_0$ be a
compact set of distributions of random sets, all supported on $\Kscr_0$. Suppose that for
each $\hbox{\boldmath\char'026} \in \Mscr_0$ the statistics $S_m(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$, and that
$S_m(\hbox{\boldmath\char'026})$ is continuous (in $\hbox{\boldmath\char'026}$). Then the inverse of $S_m(\cdot)$ is continuous
(from the space of probability measures on $X^m$ to probability measures on $\Kscr_0$).
\end{corollary}
\begin{proof}
It is an easy exercise in point-set topology to show that the inverse
of a one-to-one continuous mapping on a compact set, is continuous,
\end{proof}

\section{Random intervals} \label{S4}
In this section we examine random sets that take values in the collection
$\Iscr$ of intervals $[x,y]$, with $x \le y$, in the real line. 
Here are some useful observations.

It is convenient to identify the space $\Iscr$ of intervals $[x,y]$, with the
subset of the plane $R^2$ given by $\{(x,y): x \le y\} $. Notice that then the
Hausdorff distance between intervals coincides with the $\max$ distance on $R^2$,
namely, the distance derived from the norm
$\Vert (x,y) \Vert_\infty = \max\{\vert x \vert, \vert y \vert \}$.
Employing this isometry, the distribution of a random interval is now a probability
measure on the subset of $R^2$ above the diagonal. Such a probability measure is
determined by its values on rectangles in the plane, see Figure 2. Furthermore, it
is enough to consider rectangles in the plain where the statistics $S_2(\hbox{\boldmath\char'026})$ assigns
zero probability to the lines that define them (i.e., the dashed lines in Figure 2,
given by $\{(x,y) : x = x_1\},~\{(x,y) : x = x_2\}$, etc.).
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{Figure2}
\caption{}
\end{figure}
Given an interval $I_0 = [x_0,y_0]$, the family
of intervals which strictly contain it, is the set in $R^2$ given by
$\{(x,y) : x < x_0, y > y_0 \}$, namely, the open upper left quadrant from $(x_0,y_0)$.
Denote the open upper left quadrant from the point $(x,y)$ by $U(x,y)$. Then, given a
distribution $\hbox{\boldmath\char'026}$ of a random interval, and a rectangular $B$ determined by
$x_1, x_2, y_1, y_2$, where the statistics $S_2(\hbox{\boldmath\char'026})$ assigns zero probability
to the lines that define $B$, the measure $\hbox{\boldmath\char'026}(B)$ satisfies
\begin{equation}\label{Eq4.1}
\hbox{\boldmath\char'026}(B) = \hbox{\boldmath\char'026}(U(x_2,y_1)) - \hbox{\boldmath\char'026}(U(x_1,y_1)) - \hbox{\boldmath\char'026}(U(x_2,y_2)) + \hbox{\boldmath\char'026}(U(x_1,y_2)).
\end{equation}
Hence, we have verified the following claim.
\begin{observation}\label{Obs4.1}
Let $\hbox{\boldmath\char'026}$ be the distribution of a random interval, and let $S_2(\hbox{\boldmath\char'026})$ be
its $2$-point statistics. The $2$-point statistics determines the distribution if
for every interval $[x,y]$ it determines $\hbox{\boldmath\char'026}(U(x,y))$.
\end{observation}
Here is our first positive result. Notice that, here, the sampling rule given by the normalized
Lebesgue measure has the continuity property \ref{Prty3.1}.
\begin{theorem}\label{The4.2}
Suppose that the sampling rule from intervals is the normalized Lebesgue measure.
Let $\Mscr_0$ be a compact family of distributions
of random intervals, all supported on one compact collection of intervals. Then,
for $\hbox{\boldmath\char'026}$ in $\Mscr_0$, the statistics of the $2$-point sample $S_2(\hbox{\boldmath\char'026})$
determines $\hbox{\boldmath\char'026}$, and the inverse of the one-to-one map $S_2(\cdot)$, is continuous.
\end{theorem}
\begin{proof}
Once we verify that $S_2(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$, namely, $S_2(\cdot)$ on $\Mscr_0$
is invertible, the continuity of the inverse follows from Lemma \ref{Lem3.4} and
Corollary \ref{Cor3.5}.

In view of Observation \ref{Obs4.1}, in order to verify that $S_2(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$,
it is enough to show that for every interval $[x_0,y_0]$, the statistics $S_2(\hbox{\boldmath\char'026})$
determines $\hbox{\boldmath\char'026}(U(x_0,y_0))$. It is enough to consider the case  $y_ 0 > x_0$. Indeed,
the definition (\ref{Eq3.2}) of the statistics $S_2(\hbox{\boldmath\char'026})$ implies that the contribution
to $S_2(\hbox{\boldmath\char'026})$ of the restriction of $\hbox{\boldmath\char'026}$ to the line $\{(x,x): x \in R\}$ (namely,
the degenerate intervals), coincides with the distribution $\hbox{\boldmath\char'026}$ itself.

Now, given such a point $(x_0,y_0)$, consider the rectangular in $R^2$ given by
\begin{equation}\label{Eq4.2}
B_\varepsilon = [x_0 - \varepsilon, x_0] \times [y_0 ,y_0 + \varepsilon].
\end{equation}
Denote by $\lambda(I)$ the Lebesgue measure, i.e. the length, of the interval $I$.
According to (\ref{Eq3.2}), the contribution of an interval $I = [x,y]$ in $U(x_0,y_0)$
to the value of the statistics $S_2(\hbox{\boldmath\char'026})$ of $B_\varepsilon$, is $\varepsilon^2 \lambda(I)^{-2} \hbox{\boldmath\char'026}(dI)$,
this unless $x_0 - x < \varepsilon$ or $y - y_0 < \varepsilon$. The latter cases may introduce an error
$e_\varepsilon(I)$. This error is not greater than $\varepsilon^2 \lambda(I)^{-2} \hbox{\boldmath\char'026}(dI)$, and recall
that $\lambda(I)$ is bounded away from $0$ on $U(x_0,y_0)$. Thus, we get that
\begin{equation}\label{Eq4.3}
 S_2(\hbox{\boldmath\char'026})(B_\varepsilon) = \int_{U(x_0,y_0)} (\varepsilon^2 \lambda(I)^{-2} + e_\varepsilon(I))  \hbox{\boldmath\char'026}(dI).
\end{equation}
Dividing by $\varepsilon^2$, and realizing that $e_\varepsilon(I)$ is zero except being bounded
on a set with $\hbox{\boldmath\char'026}$-measure converging to $0$ as $\varepsilon \to 0$, we get
\begin{equation}\label{Eq4.4}
 \lim_{\varepsilon \to 0}\varepsilon^{-2} S_2(\hbox{\boldmath\char'026})(B_\varepsilon) = \int_{U(x_0,y_0)} \lambda(I)^{-2}  \hbox{\boldmath\char'026}(dI).
\end{equation}
The left hand side of (\ref{Eq4.4}) is a function of the $2$-point statistics of the
random interval. Therefore, this statistics determines the measure of $U(x_0,y_0)$
according, however, to $\lambda(I)^{-2}  \hbox{\boldmath\char'026}(dI)$. Since this holds for any $U(x_0,y_0)$,
it follows that the $2$-point statistics determines the measure $\lambda(I)^{-2} \hbox{\boldmath\char'026}(dI)$
on the entire set of intervals satisfying $x < y$. The latter measure clearly determines
$\hbox{\boldmath\char'026}(dI)$. This completes the proof.
\end{proof}
\begin{comment}\label{Com4.3}
The proof of the preceding theorem suggests a way to compute an approximation
of the random interval, given its $2$-point statistics. It is, however, a cumbersome
way. More efficient avenues are welcome.
\end{comment}
Here is our second positive result. It is related to Example \ref{Exa2.2}. Notice that,
also here, the continuity Property \ref{Prty3.1} holds.

\begin{theorem}\label{The4.4}
Suppose that the sampling from the values of the random interval is carried out such that one
of the two ends of the interval $[x,y]$ is chosen, with probabilities $\alpha(x,y)$ and
$\beta(x,y) = 1 - \alpha(x,y)$, with $0 < \alpha(x,y) < 1$ and continuous. Let $\Mscr_0$
be a compact family of distributions of random intervals, all supported on one compact
collection of intervals. Then, for $\hbox{\boldmath\char'026}$ in $\Mscr_0$, the statistics of the $2$-point
sample $S_2(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$, and the inverse of the one-to-one map $S_2(\cdot)$
on $\Mscr_0$, is continuous.
\end{theorem}
\begin{proof}
Once we verify that $S_2(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$, namely, $S_2(\cdot)$ is invertible,
the continuity follows from Lemma \ref{Lem3.4} and Corollary \ref{Cor3.5}.

Consider an interval $I = [x,y]$ in the support of $\hbox{\boldmath\char'026}$, such that $x < y$. Its
contribution to the statistics $S_2(\hbox{\boldmath\char'026})$ is supported on the four points in $R^2$
given by $(x,x), (x,y), (y,y)$ and $(y,x)$, with weights $\alpha(x,y)^2$,
$\alpha(x,y)\beta(x,y)$, $\beta(x,y)^2$ and $\alpha(x,y)\beta(x,y)$ respectively, weighted,
however, by $\hbox{\boldmath\char'026}$, namely, by the infinitesimal $\hbox{\boldmath\char'026}(dI)$ (which becomes $\hbox{\boldmath\char'026}(I)$ if
$I$ is an atom of the distribution). Furthermore, since only the end points of the intervals
are sampled, the contribution to the statistics of a point $(x,y)$ with  $x < y$, comes
only from the infinitesimal measure of the interval $[x,y]$. Hence, for a Borel subset $B$
in the region $\{(x,y): x < y\}$, we have
\begin{equation}\label{Eq4.5}
S_2(\hbox{\boldmath\char'026})(B) = \int_B \alpha(x,y)\beta(x,y) \hbox{\boldmath\char'026}(dI).
\end{equation}
The latter measure on $\{(x,y): x < y\}$ gives rise to computing $\hbox{\boldmath\char'026}$ on $\{(x,y): x < y\}$,
namely
\begin{equation}\label{Eq4.6}
\hbox{\boldmath\char'026}(B) = \int_B (\alpha(x,y)\beta(x,y))^{-1} S_2(\hbox{\boldmath\char'026})(d(x,y)).
\end{equation}
In particular, the statistics $S_2(\hbox{\boldmath\char'026})$ determines the distribution $\hbox{\boldmath\char'026}$ on $\{(x,y): x < y\}$.
Now, each interval $I = [x,y]$ with $x < y$, contributes to the statistics on $\{(x,y): x = y\}$,
namely, the values $\alpha(x,y)^2 \hbox{\boldmath\char'026}(dI)$ on $(x,x)$ and the value $\beta(x,y)^2 \hbox{\boldmath\char'026}(dI)$ on
$(y,y)$. By removing the latter statistics from the diagonal $\{(x,y): x = y\}$, we are left on
the latter line with the statistics emanating from the value of $\hbox{\boldmath\char'026}$ on the diagonal,
namely on degenerate intervals. Clearly, the latter value coincides with the, given, statistics on
the diagonal. This completes the proof.
\end{proof}
\begin{comment}\label{Com4.5}
For the former sampling rule, (\ref{Eq4.6}) provides a way to compute the distribution of the
random interval on non-degenerate intervals, given the $2$-point statistics. The only information
needed is the sampling rule. In particular, there is no need to know beforehand what the support
of the random interval is.
\end{comment}
We introduce now a useful, and natural, assumption concerning random intervals.
\begin{assumption}\label{Ass4.6}
For every $I =[a.b]$, the support of the probability measure $P_I$ contains
the end points $a$ and $b$.
\end{assumption}
The role for the assumption is clear. If samples cannot get close to the end
points of the interval, then (unless additional assumptions are made) it is not
possible to distinguish between the interval and a shorter one. The sampling
rules in the previous two positive results satisfy the assumption.

A natural question arises, namely, is the generalization of the previous theorems
to arbitrary sampling rules possessing the continuity property, true? Likewise in regard
to general regular sampling rules, that satisfy Assumption \ref{Ass4.6}. We verify now
a general result for random intervals with finite support. Another result toward
the general one is provided in the next section (see Proposition \ref{Pro5.5}).
The general case is, however, left open,
\begin{theorem}\label{The4.7}
Let $\hbox{\boldmath\char'026}$ be a probability measure on $\Iscr$, with finite support, say, supported
on $\{I_1, ..., I_l\}$, with corresponding weights $\{\alpha_1, ..., \alpha_l\}$ (i.e.,
$\alpha_j \ge 0$ and the sum of the $\alpha_j$ is $1$).
Then the statistics of the $2$-point sample $S_2(\hbox{\boldmath\char'026})$, determines $\hbox{\boldmath\char'026}$.
\end{theorem}
\begin{proof}
The union of the sets $I_j^2$ is a union of squares in $R^2$, symmetric with respect
to the line $x = y$ (where $R^2$ is the space of pairs $(x,y)$, Figure 1 portrays the
union of squares in the case of Example \ref{Exa2.1}).

Denote the union of the finite number of squares on which $S_2(\hbox{\boldmath\char'026})$ is supported by
$V(\hbox{\boldmath\char'026})$. We claim that in any such $V(\hbox{\boldmath\char'026})$, there is a point in
$R^2$, say $(x_0,y_0)$, such that a neighborhood of $(x_0,y_0)$ in $V(\hbox{\boldmath\char'026})$, say
$N(x_0,y_0)$, belongs to only one of the squares $I_j^2$, say $I_1^2$, and that
$P_{I_1}^2(N(a_0,b_0)) >0$. To see this, just pick $x_0$ to be the smallest $x$ among the
finite number of intervals $[x,y]$ in the support of $\hbox{\boldmath\char'026}$, and if $x_0$ belongs to
more than one interval, pick $y_0$ to be the largest $y$ among these intervals. (In
Figure 1, if all three squares participate in the union, this point would be $(1,3)$.)
The condition $P_{I_1}^2(N(a_0,b_0)) >0$ is met since both $x_0$ and $y_0$ are in the
support of $P_{I_1}$. Also notice that the point $(x_0,y_0)$ in $R^2$ determines
the square $I_1^2$. The point $(x_0,y_0)$ can be detected using only the
statistics $S_2(\hbox{\boldmath\char'026})$, with no need to know beforehand on what intervals
the distribution $\hbox{\boldmath\char'026}$ is supported.

Now, since the neighborhood $N(x_0,y_0)$ is part of only the square $I_1^2$, the value of
the statistics $S(\hbox{\boldmath\char'026})$ on this neighborhood is given by $\alpha_1 P_{I_1}^2(N(a_0,b_0))$.
The coefficient $\alpha_1$ is now defined by the value the statistics assigns to $N(x_0,y_0)$
and the sampling rule  $P_{I_1}$. We can consider now the random set and its $2$-point
statistics, when $I_1$, and the corresponding components of $\hbox{\boldmath\char'026}$ and $S_2(\hbox{\boldmath\char'026})$, are
removed. We are left with a random set supported on $l - 1$ intervals. Repeating the
argument $l-1$ times, determines the entire distribution $\hbox{\boldmath\char'026}$.
\end{proof}
\begin{comment}\label{Com4.8}
The proof of the preceding result provides an algorithm to compute the distribution of
the random interval, given its $2$-point statistics. The only information needed is the
sampling rule, and that the random interval is supported on a finite set of intervals.
Indeed, given Assumption \ref{Ass4.6}, the set $V(\hbox{\boldmath\char'026})$ reveals, one step at the time,
the support of $\hbox{\boldmath\char'026}$.
\end{comment}
We may refer to the main tool in the previous proof as {\sl peeling}. We have used
peeling in a previous proof. It can be considered in a more general framework, as
suggested in the next section.


\section{The general peeling property}\label{S5}

Let $\Kscr$ be a collection of compact subsets of $X$, and let $P_K$ be
the associated sampling rule. For a finite collection $\Kscr_0$ of compact sets
in $\Kscr$, denote by  $V_m(\Kscr_0)$ the union, in $X^m$, of the sets $K^m$ for
$K \in \Kscr_0$.
\begin{definition}\label{Def5.1}
We say that a collection $\Kscr_1$ of compact sets in $\Kscr$
has the {\sl $m$-point peeling property}, if for any finite sub-collection
$\Kscr_0$ of $\Kscr_1$, there is a subset $H$ of $V_m(\Kscr_0)$, such that
$H$ is included in only one of the sets $K^m$ for $K \in \Kscr_0$,
and $P_K^m(H) > 0$.
\end{definition}
A collection of intervals has the $2$-point peeling property, as demonstrated
and used in Section 4. We encounter more examples later in the paper.
\begin{proposition}\label{Pro5.2}
Let $\hbox{\boldmath\char'026}$ be the distribution of a random set, supported on a finite collection
$\Kscr_1$ of compact sets. If $\Kscr_1$ has the $m$-point peeling property,
then $S_m(\hbox{\boldmath\char'026})$ determines the distribution $\hbox{\boldmath\char'026}$.
\end{proposition}
\begin{proof}
Suppose that the random set assigns the weight $\alpha_i$ to $K_i \in \Kscr_1$.
Suppose that $K_1$ is a set in the support of $\hbox{\boldmath\char'026}$, such that a subset, say $H$,
of $K_1^m$ has a positive $P_{K_1}^m$ measure, and $H$ does not intersect any
of the sets $K_j^m$, for $j \ne 1$. Let $h = S_m(\hbox{\boldmath\char'026})(H)$. The choice of $H$ and
(\ref{Eq3.2}) imply that $h = \alpha_1 P_{K_1}^m(H)$. This determines
the value of $\alpha_1$. Consider now $\Kscr_1$ without the set $K_1$, with
its weight $\alpha_1$. Then the $m$-point statistics is the former one without
$\alpha_1 P_{K_1}^m$. We are left then with a smaller collection of sets,
still possessing the $m$-point peeling property. After repeating the
process a finite number of times, all the weights that determine $\hbox{\boldmath\char'026}$
are revealed. This completes the proof.
\end{proof}
\begin{comment}\label{Com5.3}
The preceding proof suggests an algorithm to compute the distribution of $\hbox{\boldmath\char'026}$,
subject, however, to the conditions set in Comment \ref{Com4.8}.
\end{comment}
Here is a result on general distributions with the peeling property.
\begin{proposition}\label{Pro5.4}
Let $\Mscr_0$ be a compact family of distributions of random sets, all
supported on a compact collection of compact sets $\Kscr_1$. Suppose $\Kscr_1$
has the $m$-point peeling property. Also suppose that each $\hbox{\boldmath\char'026} \in \Mscr_0$
can be approximated, arbitrarily close, by a finitely supported random set in
$\Mscr_0$. Suppose that the inverse of $S_m^{-1}(\hbox{\boldmath\char'027})$ on
the image of distributions with finite support $\hbox{\boldmath\char'027}$ in $\Mscr_0$ (the existence
of the inverse is guaranteed by the previous proposition), is uniformly continuous.
Then the $m$-point statistics $S_m(\hbox{\boldmath\char'026})$ of any distribution in $\Mscr_0$ on
$\Kscr_1$ determines $\hbox{\boldmath\char'026}$, and its inverse is continuous.
\end{proposition}
\begin{proof}
Suppose two distributions $\hbox{\boldmath\char'026}_1$ and $\hbox{\boldmath\char'026}_2$ yield the same $m$-point
statistics, say $S_m$. The distributions can be approximated arbitrarily
close by distributions, say $\hbox{\boldmath\char'027}_1$ and $\hbox{\boldmath\char'027}_2$, each supported on
a finite collection of compact sets. The continuity of the
$m$-point statistics (see Lemma \ref{Lem3.4}) implies that
$S_m(\hbox{\boldmath\char'027}_1)$ and $S_m(\hbox{\boldmath\char'027}_2)$ are both arbitrarily close to $S_m$.
This contradicts the assumed uniform continuity. Hence the $m$-point
statistics on $\Kscr_1$ is a one-to-one mapping. The continuity of its
inverse follows, see Corollary \ref{Cor3.5}.
\end{proof}
Notice that in the previous proof, the uniform continuity of the
inverse of the statistics of the finitely supported distributions, is
needed only for approximations of the distributions in $\Mscr_0$.

The previous result is relevant to the open problem suggested in
the previous section, concerning random intervals. Indeed, the problem will be resolved 
if the inverse of the $2$-point statistics of random intervals with a finite number
of values (whose existence is verified in Theorem \ref{The4.7}), is
uniformly continuous. Here is a partial result in this direction.
\begin{proposition}\label{Pro5.5}
Let $\Iscr_0$ be a compact family of intervals with the property that
for no interval, say $[x,y]$, in $\Iscr_0$, a neighborhood $[x-\varepsilon, y+\varepsilon]$
is included in another interval in $\Iscr_0$. Let the sampling rule $P_I$ on
$\Iscr_0$ satisfy the continuity property \ref{Prty3.1} and the end points
Assumption \ref{Ass4.6}. Then the $2$-point statistics $S_2(\hbox{\boldmath\char'026})$ of a
distribution $\hbox{\boldmath\char'026}$ on $\Iscr_0$ determines $\hbox{\boldmath\char'026}$, and the inverse of
$S_2(\cdot)$ is continuous.
\end{proposition}
\begin{proof}
We utilize the observations made in Section 4. An interval $[x, y]$
can be viewed as the point $(x,y)$ in $R^2$, and its contribution to the
statistics $S_2(\hbox{\boldmath\char'026})$ is via the rectangle $[x, y]^2$ in $R^2$.
The non-inclusion property among intervals, implies that for each interval
$[x, y]$ in the support of $\hbox{\boldmath\char'026}$, the point $(x, y)$ is on the line
that forms the upper and left boundary of the support of $S_2(\hbox{\boldmath\char'026})$. In
particular, $\hbox{\boldmath\char'026}$ is supported on this line. A finitely supported
approximation of $\hbox{\boldmath\char'026}$ exists, supported on the same line. It is clear
then that the inverse of the statistics of the finitely supported
approximations are uniformly continuous. In view of Proposition \ref{Pro5.4},
the statistics is a one-to-one mapping on $\Mscr_0$ and its inverse is
continuous.
\end{proof}



\section{Finitely supported random sets}\label{S6}
We start with a general combinatorial criterion for the determination of a 
finitely supported random set, by the statistics of samplings. Additional structure 
will help to compute the smallest $m$ for specific families of random sets.

Let $K_1, K_2, ..., K_L$ be $L$ compact sets in a metric space $X$. The distribution
$\hbox{\boldmath\char'026}$ of a random set with values in this finite collection is given by a vector
$< \alpha >$ with $L$ coordinates, all greater or equal to $0$, sum up to $1$. We 
think of $<\alpha>$ as a row vector (and denote its transpose by $<\alpha>^T$). Thus, 
the $i$-th coordinate of $< \alpha >$ is the probability that $K_i$ will be sampled

We examine the $m$-point sampling of $<\alpha>$. 
The mapping $S_m(\hbox{\boldmath\char'026})$ is linear in $<\alpha>$, as is evident from $(\ref{Eq3.2})$.
Furthermore, the latter formula reveals the role of $\hbox{\boldmath\char'026}$ in the generation
of the $m$-point statistics, as follows. The probability measure $S_m(\hbox{\boldmath\char'026})$ is
determined by its values on sets in $X^m$ of the form $B_1 \times ... \times B_m$,
where each $B_i$ is a Borel subset in $X$ such that if $B_i$ intersects one of the
sets, say $K$, in the support, then it is included in that $K$. Indeed, any probability
measure on a product space is determined by its values on product of sets, and any such
product is determined by products of the form just described.

Now, given such a product, we have
\begin{equation}\label{Eq6.1}
S_m(\hbox{\boldmath\char'026})(B_1 \times ... \times B_m) =
\sum_{j =1}^L \alpha_j P_{K_j}(B_1)\cdot ... \cdot P_{K_j}(B_m).
\end{equation}
Suppose now that the sampling rule is regular (see Definition \ref{Def3.3}), and let 
$\gamma$ be the positive measure that governs the regularity. It follows that 
(\ref{Eq6.1}) can be written
as
\begin{equation}\label{Eq6.2}
S_m(\hbox{\boldmath\char'026})(B_1 \times ... \times B_m) =
\gamma(B_1)\cdot ... \cdot \gamma(B_m) <\beta>  <\alpha>^T,
\end{equation}
where $<\beta>$ is a row vector that depends on the sets $\{B_1, ..., B_m\}$. The
vector $<\beta>$ has $L$ entries. The $j$-th coordinate
of $<\beta>$ is equal to $0$ if one of the $B_i$ is not included in $K_j$. Otherwise,
the entry is equal to $\gamma(K_j)^{-m}$.

The number of distinct vectors $<\beta>$ may be large, depending on the
combinatorial structure of intersections among the different sets in the support
of $\hbox{\boldmath\char'026}$. The number of linearly independent vectors among them does not exceed
$L$, since each vector has $L$ coordinates. Let $l_0$ be the maximal number of linearly
independent vectors, and let $<\beta>_k$ for $k = 1, ..., l_0$ be $l_0$
linearly independent vectors. Arrange the $l_0$ vectors as an $l_0 \times L$
matrix, denoted ${\bf B}$. Denote by ${\bf B}_1$ the matrix obtained when
a row vector with entries equal to $1$ is added to  ${\bf B}$.

\begin{theorem}\label{The6.1}
Let $\Mscr_0$ be the family of probability measures supported on the sets
$\{K_1, ..., K_L\}$. Suppose that the sampling is carried out according to a
regular sampling rule $\gamma$. The statistics $S_m(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$
if and only if the matrix ${\bf B}_1$ has rank $L$.
\end{theorem}
\begin{proof}
Suppose ${\bf B}_1$ has rank less than $L$. Then there exists
a non-zero vector $<\eta>$ such that ${\bf B}_1<\eta>^T $ is the origin. In particular,
since all the entries in the last row of ${\bf B}_1$ are equal to $1$, the sum of the
coordinates of $<\eta>$ is $0$. Choose now a probability vector $<\alpha>$ with
positive entries. Then, for $\varepsilon > 0$ small enough, both $<\alpha> +\varepsilon <\eta>$
and $<\alpha> -\varepsilon <\eta>$ are positive vectors. Both are probability vectors
(since the sum of the coordinates of $<\eta>$ is $0$). The operation
of  ${\bf B}$ on both probability vectors yields the same outcome, hence yields the
same $m$-point statistics. This verifies the ``only if'' part. If ${\bf B}_1$ has
rank equal to $L$, the image by ${\bf B}_1$ of two distinct probability vectors
cannot be identical. Since for any probability vector, the image by ${\bf B}_1$ has
its last coordinate equal to $1$, the image by ${\bf B}$ of two distinct probability
vectors cannot be identical. Since distinct products of ${\bf B}_1 <\alpha>^T$ result
in distinct statistics, the proof is complete.
\end{proof}
\begin{comment}\label{Com6.2}
The proof of Proposition \ref{The6.1} is not constructive. It is possible, however,
to derive the distribution $<\alpha>$ from the $m$-point statistics is case
${\bf B}$ has full rank, or when ${\bf B}_1$ is $L \times L$ and has full rank.
Indeed, Choose $l_0$ strings of the form $B_1, ..., B_m$, each related
to a row in ${\bf B}$, or, to a row in ${\bf B}_1$, except the last one,
respectively. Consider the diagonal matrix ${\bf D}_1$, with entries
$T_J = \gamma(B_1)\cdot ... \cdot \gamma(B_m)$ in the diagonal, or in the first $L-1$
positions of the diagonal, and $1$ in the last, respectively. The vector
$S_{n-1}(\hbox{\boldmath\char'026})(T_J)$ is now equal to
${\bf B}_1 {\bf D}_1 <\alpha>^T $. Inverting ${\bf B}_1 {\bf D}_1 $, yields
$<\alpha>$ in terms of the $m$-point statistics of $\hbox{\boldmath\char'026}$.
\end{comment}

A trivial example of the previous considerations is the case where
the sets $\{K_1, ..., K_L\}$ are disjoint. Then, clearly, the $1$-point statistics 
suffices to determine the distribution, as can also be deduced from the construction of
the matrix ${\bf B}$. We now work out a more involved example, for which the exact 
bound $m$ for the statistics that determines the distribution is computed. The example
will serve in the next section, in the study of random convex-valued sets. 


\begin{example}\label{Exa6.3}
Let $G_0$, and $G_1, ..., G_n$ 
be $n+1$ compact subsets of a metric space, mutually disjoint. We consider the 
family of random sets that take as values the $2^n$ subsets, marked as $K_1, ..., K_{2^n}$, 
each is the union of $G_0$ and a subset of $G_1, ..., G_n$. Thus, a set $K$ 
in the support of the distribution of the random set, corresponds to a subset, say $J$, 
of $\{1, ..., n\}$ (including the empty set). Then $K$ is the union of $G_0$ and the sets 
$G_j, j \in J$ (in particular, when $J$ is the empty set, the value of the random set is 
$G_0$). We refer to such $K$ as $K_J$. The distribution of such a random set is determined 
by $2^n$ non-negative numbers $\alpha_1, ..., \alpha_{2^n}$, whose sum is $1$.
The sampling from the value $K$ of the random set, is done
according to a probability measure $P_K$.  We assume that if $i \in J$ then
$P_{K_J}(G_i) > 0$, and that $P_{K_J}(G_0) > 0$ for all $J$.
\end{example}
The results that follow pertain to Example \ref{Exa6.3}.
\begin{proposition}\label{Pro6.4}
Let $\Mscr_0$ be the family of probability measures supported on
$\{K_1, ..., K_{2^n}\}$. Then the statistics of the $n$-point sample $S_n(\hbox{\boldmath\char'026})$
of $\hbox{\boldmath\char'026} \in \Mscr_0$, determines $\hbox{\boldmath\char'026}$, and the inverse of $S_n(\cdot)$
is continuous.
\end{proposition}

\begin{proof}
We use the method of peeling. The statistics $S_n(\hbox{\boldmath\char'026})$ is a probability measure
on $X^n$, namely, it is the integral (in our case, the sum), of
$\alpha_J P_J^n$, with $J$ running over all subsets of $\{1, ..., n\}$.

Consider within the support of $S_n(\hbox{\boldmath\char'026})$, the subset where the
$n$-sample includes points in all the sets $\{G_1, ..., G_n\}$. This part of the
statistics is generated by only one value of the random set, namely, the union
of all $\{G_1, ..., G_n\}$ union $G_0$. The probability of this subset
of $X^n$, according to $P_{K_J}^n$ is positive. The value of the statistics on this set
is given. The ratio of the two numbers is the coefficient $\alpha_{J_1}$ where $J_1$
represents the said subset. Once this $\alpha_{J_1}$ is revealed, it can be removed
from the distribution of the random set, and the corresponding part of the
statistics can be peeled from the statistics.

We are left with a random set (actually, with part of a random set as the
underlying probability measure may have probability less than $1$, but we still
refer to it as a random set), with values as the initial one, without the
eliminated set.

Now consider within the support of the new $S_n(\hbox{\boldmath\char'026})$, the subset where the
$n$-sample includes points in $n-1$ sets $G_i$, say the first sets $\{G_1, ..., G_{n-1}\}$.
Once the set of all indices was eliminated, this part of the statistics is generated by
only one value of the random set, namely, the union of $\{G_0, G_1, ..., G_{n-1}\}$.
The same argument as the previous one can be applied, so the relevant $\alpha_J$ is
determined, and the respective parts can be peeled from both the random set and the
statistics. Repeating the argument $n-1$ times will determine the
coefficients $\alpha_J$ associated with points in the subsets of size $n-1$ of
$\{G_1, ..., G_n\}$. Then the respective contributions to the random set and the
statistics can be removed.

Next stage will be to consider subsets of $\{1, ..., n\}$ of size $n-2$. Since
all subsets of size $n-1$ were peeled, the peeling argument can be applied
at this stage as well. Continuing with the peeling argument through subsets
of $\{1, ..., n\}$ of sizes $n-3, ..., 2$, will reveal all the coefficients $\alpha_J$.
The continuity of the inverse mapping is obvious. This completes the proof.
\end{proof}
\begin{comment}\label{Com6.5}
As in a previous case of peeling, the proof of the preceding
result provides an algorithm to compute the distribution of the random set. This
time, however, the information needed is the sampling rule, and the support
of the distribution of the random set (indeed, in general, the statistics  may not
determine the peeled set).
\end{comment}
There may be sampling rules for which the $m$-point statistics of a random set
depicted in Example \ref{Exa6.3}, determines the distribution of the random set
with $m < n$. Under more structured sampling rules, we can get exact estimates.
One such rule is the regular sampling rule, introduced in Definition \ref{Def3.3}.
The following is the corresponding result,
where the regular sampling rule is generated by a measure $\gamma$ on $X$.

\begin{proposition}\label{Pro6.6}
Let $\Mscr_0$ be the family of probability measures supported on
$\{K_1, ..., K_{2^n}\}$. Suppose that the sampling rule is regular, governed by
a measure $\gamma$. Then the statistics of $n$-point sample $S_n(\hbox{\boldmath\char'026})$ of 
$\hbox{\boldmath\char'026} \in \Mscr_0$, determines $\hbox{\boldmath\char'026}$, and the inverse of $S_n(\cdot)$ on $\Mscr_0$ 
is continuous. The statistics of the $(n-1)$-point sample $S_{n-1}(\hbox{\boldmath\char'026})$, does not 
determine $\hbox{\boldmath\char'026}$.
\end{proposition}
\begin{proof}
The case of $n$-point samples is a particular case of the previous result. We
proceed to prove that the $(n-1)$-point sampling does not determine the random set.

We follow the derivations of the general case, introduced earlier in the section.
Let $<\alpha>$ denote the vector of weights that $\hbox{\boldmath\char'026}$ assigns to each set in its
support, namely, the coordinates of the vector $<\alpha>$ are indexed by $J$, running
over all $2^n$ subsets of $\{1, ..., n\}$. We think of $<\alpha>$ as a row vector.

The probability measure $S_{(n-1)}(\hbox{\boldmath\char'026})$ is determined
by its values on sets in $X^{(n-1)}$ of the form $B_1 \times ... \times B_{(n-1)}$,
where each $B_i$ is a Borel subset in $X$ such that if $B_i$ intersects one of the $G_l$,
then it is included in that $G_l$. Indeed, any probability measure on a product space is
determined by its values on product of sets, and any such product can be separated into
products of the form just described.

Now, given such a product, we have (compare with (\ref{Eq6.1}))
\begin{equation}\label{Eq6.3}
S_{(n-1)}(\hbox{\boldmath\char'026})(B_1 \times ... \times B_{(n-1)}) =
\sum_J \alpha_J P_J(B_1)\cdot ... \cdot P_J(B_{(n-1)}),
\end{equation}
where $J$ runs over all subsets of $\{1, ..., n\}$.

Since the sampling rule is regular, it follows (compare with (\ref{Eq6.2})) that 
(\ref{Eq6.3}) can be written
as
\begin{equation}\label{Eq6.4}
S_{(n-1)}(\hbox{\boldmath\char'026})(B_1 \times ... \times B_{(n-1)}) =
\gamma(B_1)\cdot ... \cdot \gamma(B_{(n-1)}) <\beta>  <\alpha>^T,
\end{equation}
where $<\beta>$ is a row vector that depends on the sets $\{B_1, ..., B_{(n-1)}\}$, with
$2^n$ entries according to $J \subseteq \{1, ..., n\}$.  The $J$-th coordinate
of $<\beta>$ is equal to $0$ if one of the $B_i$ is not included in $K_J$. Otherwise,
the entry is equal to $\gamma(K_J)^{-(n-1)}$. This structure implies that the number of
distinct vectors $<\beta>$ is given by
\begin{equation}\label{Eq6.5}
\sum_{l = 0}^{n-1}  {n \choose l},
\end{equation}
which is equal to $2^n - 1$. Now, arrange the distinct vectors $<\beta>$ as a matrix,
denoted ${\bf B}$. It has $2^n - 1$ rows and $2^n$ columns. We add to ${\bf B}$ a row vector 
with all its coordinates equal to $1$. We denote the new matrix by ${\bf B}_1$. Furthermore, 
(for visual convenience) we arrange the coordinates of $<\alpha>$ in a non-decreasing order of 
the size of $J$, and, accordingly, we arrange the columns of ${\bf B}_1$ in the same order. 
The result is a matrix with a bottom row of entries equal to $1$, and the rest being
an upper diagonal matrix, with entries in the $J$-th column being either equal to
$0$ or equal to $\gamma(K_J)^{-(n-1)}$, depending whether the subset that is associated
with the row is included in $J$ or not. (To make it easier to follow the arguments,
see Example \ref{Exa6.7} below, with $n = 3$).

All in all, the value of the $(n-1)$-point statistics $S_{(n-1)}(\hbox{\boldmath\char'026})$ of
$B_1 \times ... \times B_{(n-1)}$ is then given by  (\ref{Eq6.4}) for the appropriate
$<\beta>$.

We claim that the matrix ${\bf B}_1$ just constructed is singular, namely,
its rank is less than $2^n$. Once this claim is verified, Theorem \ref{The6.1}
implies that the $(n-1)$-point statistics does not determine the distribution
of the random set. 

It remains to verify that ${\bf B}_1$ is singular. To that end recall
that a nonzero entry in the column of ${\bf B}_1$ associated with a
subset $J$ of $\{1,2, ..., n\}$, is equal to $\gamma(K_J)^{-(n-1)}$, except on the
last row, where the entry is $1$. For each $J$ we multiply the $J$-th column by
$\gamma(K_J)^{(n-1)}$. This operation does not change the rank of the matrix.
Now, the entries of the last row in the matrix are $\gamma(K_J)^{(n-1)}$ with $J$
running over all subsets of $\{1,2, ..., n\}$. The first $(2^n-1)$ rows of ${\bf B}_1$
form an inclusion matrix, namely, its $(J_1,J_2)$ entry is $1$ if
$J_1$ is a subset of $J_2$, and $0$ otherwise. Now multiply by $-1$ each column
of the matrix which is associated with a subset $J$, i.e., a coordinate of $<\alpha>$,
that has an odd number of elements. Denote the new matrix by ${\bf C}$. The rank of
${\bf C}$ is the same as the rank of ${\bf B}_1$.

We claim that ${\bf C}$ is such that the sum of the entries in each
of its rows is $0$. This would verify that ${\bf C}$ has rank less than $2^n$.

To verify the claim, consider first the top row. Counting the number of entries
associated with sets with even number of elements, adding to that the number of entries
associated with an odd number of elements, multiplied however by $-1$, results in
\begin{equation}\label{Eq6.6}
\sum_{l = 0}^n  (-1)^l {n \choose l}.
\end{equation}
The value of the latter term is $( 1-1)^n = 0$

The computation of any other row except the last one is similar. Indeed, given a row in ${\bf B}$,
it has entries equal to $0$ until the diagonal, where the column is associated with a set
$J_0$. The non-zero entries in the rest of the row, are those associated with sets $J$ that
include $J_0$. Counting those with even number of entries, and adding the number of
those with odd number of elements multiplied by $-1$, results in a term like (\ref{Eq6.6}),
with $n$ replaced by $n - j_0$, where $j_0$ is the number of elements in $J_0$ (in particular,
$j_0 < n$). Hence the sum of the entries of any of the first $2^n-1$ rows in ${\bf C}$ is $0$.

The last step needed for the completion of the proposition is to show that the sum
of entries of the last row of ${\bf C}$ is $0$. To this end we need to spell out the
exact form of these entries, namely, 
\begin{equation}\label{Eq6.7}
\gamma(K_J)^{(n-1)} = (\gamma(G_0) + \sum_{j \in J} \gamma(G_j))^{(n-1)}.
\end{equation}
Expanding each of the latter terms, we get that each entry in the last row in ${\bf C}$
is a sum of monomials, of the form
$ \gamma(G_0)^{k_0} \gamma(G_1))^{k_1}\cdot \cdot \cdot \gamma(G_n))^{k_{(n-1)}}$,
with the sum of the $k_i$ is $n-1$, namely of order $n-1$, multiplied by the corresponding
binomial (rather, multinomial) coefficient ${(n-1)! \over k_1! k_2! \cdot \cdot \cdot k_{n-1}!}$.
Let $J_0$ be the subset associated with the indices with $k_j > 0$. It is clear that
this monomial appears exactly in those columns associated with $J$ which includes $J_0$.
Now the observations made for the $2^n-1$ rows, where the entries are equal to $1$, is
valid also for the summation of the constant entries forming the identified monomials.
Applying this to all the monomials appearing in the expansion verifies the claim.
This completes the proof.
\end{proof}
Here is the example promised in the proof of the previous result.
\begin{example}\label{Exa6.7}
We consider a specific case of the example examined so far, in the case $n=3$,
namely, the a  value of the random set is the union of a given set $G_0$ with
the sets that form subset of $(G_1, G_2, G_3)$. The sampling rule regular, generated
by a measure $\gamma$. Suppose that the measure $\gamma$ assigns to
the sets $G_i$ the values $\gamma(G_0) = 3$, $\gamma(G_1) = 2$, $\gamma(G_2) = 1$,
and $\gamma(G_3) = 4$. Arrange $<\alpha>$ according to the column vector
as appears in the displayed form. Here the index reflects the sets $G_i$ the union
of which forms a value of the random set. With these data, the matrix ${\bf B}_1$
invoked in the proof, here for a sample size $2$, is as follows.
\vskip 2pt
\begin{equation}\label{Eq6.8}
\begin{pmatrix}
3^{-2}  &5^{-2}  &4^{-2}  &7^{-2}  &6^{-2}  &8^{-2}  &9^{-2}  &10^{-2}  \\
0      &5^{-2}  &0      &0      &6^{-2}  &8^{-2}  &0      &10^{-2}  \\
0      &0      &4^{-2}  &0      &6^{-2}  &0      &9^{-2}  &10^{-2}  \\
0      &0      &0      &7^{-2}  &0      &8^{-2}  &9^{-2}  &10^{-2}  \\
0      &0      &0      &0      &6^{-2}  &0      &0      &10^{-2}  \\
0      &0      &0      &0      &0      &8^{-2}  &0      &10^{-2}  \\
0      &0      &0      &0      &0      &0      &9^{-2}  &10^{-2}  \\
1      &1      &1      &1      &1      &1      &1      &1
\end{pmatrix}
\begin{pmatrix}
\alpha_0   \\
\alpha_{01}  \\
\alpha_{02}  \\
\alpha_{03}  \\
\alpha_{012} \\
\alpha_{013} \\
\alpha_{023} \\
\alpha_{0123}
\end{pmatrix}.
\end{equation}
\vskip 2pt

To demonstrate the way the expression (\ref{Eq6.8}) is used in the generation
of the statistics, let $<\alpha>$ be the distribution of the random set.
The value of the $(n-1)$-point statistics
of, say $G_1 \times G_3$, is as follows. Invoking (\ref{Eq6.4}), and realizing
that the string $G_1 \times G_3$ relates to the $7$-th row, say ${\bf b}_7$, the
value of the statistics is $\gamma (G_1)\gamma(B_3) {\bf b}_7 <\alpha> $,
namely, $2 \cdot 3 ( 8^{-2}\alpha_{13} + 10^{-2}\alpha_{0123})$.
\end{example}
\begin{remark}\label{Rem6.8}
We may apply the procedure in Proposition \ref{Pro6.6} to $n$-point sampling. 
It would yield another proof (under, however, the additional conditions), that 
the $n$-point statistics determines the distribution. Indeed, the resulting matrix 
${\bf B}$ is then upper triangular with non-zero entries on the diagonal, hence 
with rank $2^n$. In particular, the statistics of distinct distributions cannot 
coincide. This also leads to a constructive way to compute the distribution, as 
noted in Comment \ref{Com6.2}.
\end{remark}
We exploit the previous computations to examine two small variations of the 
former one, demonstrating, however, a change in the determination parameters.


\begin{example}\label{Exa6.9}
Consider Example \ref{Exa6.3}, with the following change. 
The set $G_0$ is excluded from being a value of the random set. Thus,
the number of sets in the support of the distribution of a random
set is $2^n -1$, and the distribution of such a random set is given 
by the vector $\alpha_1, ..., \alpha_{2^n-1}$.
\end{example}

The, seemingly minor change of the former example, affects the size
of sampling needed to determine the distribution, as follows. 


\begin{proposition}\label{Pro6.10}
Let $\Mscr_0$ be the family of probability measures supported on
$\{K_1, ..., K_{2^n-1}\}$ in Example \ref{Exa6.9}. Suppose that the sampling rule
is regular, governed by a measure $\gamma$. Then the statistics of $(n-1)$-point 
sample $S_{n-1}(\hbox{\boldmath\char'026})$ of $\hbox{\boldmath\char'026} \in \Mscr_0$, determines $\hbox{\boldmath\char'026}$, and the inverse 
of $S_{n-1}(\cdot)$ on $\Mscr_0$ is continuous. The statistics of $(n-2)$-point 
sample $S_{n-2}(\hbox{\boldmath\char'026})$, does not determine $\hbox{\boldmath\char'026}$.
\end{proposition}
\begin{proof}
First we verify that the $(n-1)$-point sample $S_{n-1}(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$.
Consider the matrix ${\bf B}$ as previously constructed. It is clear that
it is identical to the matrix ${\bf B}$ in Proposition \ref{Pro6.6}, without, however,
the first row (since the set $G_0$ is not allowed to be a value of the random set).
We argue that the, now $(2^n-1) \times (2^n -1)$, matrix ${\bf B}$ has rank $2^n -1$.
To see that, you may first multiply each column of ${\bf B}$ by
$\gamma(K_J)^{(n-1)}$ where the column is associated with the set $K_J$. This makes
${\bf B}$ a matrix of zeroes and ones, without changing the rank. Now multiply
each column associated with $K_J$ with the size of $J$ being an odd number, by $-1$.
Again, the rank has not changed. Adding all columns to the last one results
in the vector $(1, 0, 0, ..., 0)^T$. This was verified in the computations
in the proof of Proposition \ref{Pro6.6}. Indeed, adding up the columns of ${\bf B}$ 
in the said proof results in the zero vector. Here, however, we have a non-zero result 
since the first column in the latter sum does not take part. Moving the last column 
to be the first one yields an upper diagonal matrix with non-zero entries on the diagonal,
hence having full $2^n -1$ rank. Invoking Proposition \ref{The6.1} completes the first
part of the proof,

To verify that the $(n-2)$-point statistics does not determine the distribution,
construct the relevant matrix ${\bf B}$. Its number of rows is given by
$\sum_{l = 0}^{n-2}  {n \choose l}$, which is less than $2^n -1$ even after adding
the row of ones, to get ${\bf B}_1$. Hence the latter is singular. Invoking
Theorem \ref{The6.1} completes the proof.
\end{proof}

\begin{example}\label{Exa6.11}
Let $\{G_1, G_2, ..., G_n\}$ be a finite collection of mutually disjoint 
sets in a space $X$. Let $K_1, ..., K_{(2^n-1)}$ be the $2^n-1$ unions of
non-empty sub-collections. Let $P_K$ be the sampling rule from the set $K$. A random
set with values in the family of such unions is determined by a probability vector
$\alpha_1, ..., \alpha_{2^n-1}$.
\end{example}
\begin{proposition}\label{Pro6.12}
Let $\Mscr_0$ be the family of probability measures supported on the sets
$\{K_1, ..., K_{2^n-1}\}$ in Example \ref{Exa6.11}. Suppose that the sampling rule
is regular, with regularity governed by a measure $\gamma$. Then the statistics
of $(n-1)$-point sample $S_{n-1}(\hbox{\boldmath\char'026})$ of $\hbox{\boldmath\char'026} \in \Mscr_0$, determines $\hbox{\boldmath\char'026}$,
and the inverse of $S_{n-1}(\cdot)$ on $\Mscr_0$ is continuous. The statistics of
$(n-2)$-point sample $S_{n-2}(\hbox{\boldmath\char'026})$, does not determine $\hbox{\boldmath\char'026}$.
\end{proposition}
\begin{proof}
First we verify that the $(n-1)$-point sample $S_{n-1}(\hbox{\boldmath\char'026})$ determines $\hbox{\boldmath\char'026}$.
Consider the matrix ${\bf B}$ as previously constructed. It is clear that
it is identical to the matrix ${\bf B}$ in Proposition \ref{Pro6.6}, without, however,
the first row and the first column. (since the set $G_0$ does not take part in
this example). The matrix ${\bf B}$ is, now, $(2^n-2) \times (2^n -1)$. We add to it
a row of $1$s, forming the matrix ${\bf B}_1$. We claim that ${\bf B}_1$ has full
$2^n-1$ rank. To see that, you may first multiply each column of ${\bf B}$ by
$\gamma(K_J)^{(n-1)}$ where the column is associated with the set $K_J$. This makes
${\bf B}$ a matrix of zeroes and ones, without changing the rank. Now multiply
each column associated with $K_J$ with the size of $J$ being an odd number, by $-1$.
Again, the rank has not changed. Adding all columns to the last one result
in the vector $(0, 0, 0, ..., c)^T$ with $c$ not equal to $0$. This was verified
in the computations in the said proof. Indeed, adding up the columns of ${\bf B}$ in
that proof results in the zero vector. Here, however, we have a non-zero result
since the first column in the latter sum does not take part. Simple operations on
the columns of the matrix will now lead to an upper diagonal matrix with
non-zero entries on the diagonal. Invoking Theorem \ref{The6.1} completes
the first part of the proof,

To verify that the $(n-2)$-point statistics does not determine the distribution,
construct the relevant matrix ${\bf B}$. Its number of rows is given by
$\sum_{l = 0}^{n-2}  {n \choose l}$, which is less than $2^n -1$ even after adding
the row of ones, to get ${\bf B}_1$. Hence the latter is singular. Invoking
Theorem \ref{The6.1} completes the proof.
\end{proof}
The two possibilities mentioned in the Comment \ref{Com6.2},
namely, that ${\bf B}$ is $L \times L$ and has full rank, and that
${\bf B}$ is $(L-1) \times L$ and ${\bf B}_1$ has full rank, may occur.
For instance, the first possibility occurs in Example \ref{Exa6.9},
Another example is when the sets $K_j$ are disjoint. Then the ${\bf B}$ 
matrix generated by the $1$-point statistics is the identity matrix. An 
example for the second possibility
is the one in Example \ref{Exa6.11}. The matrix ${\bf B}$
is then of order $(2^n -2) \times (2^n - 1)$, and the addition of the line
to make ${\bf B}_1$, results in a matrix of full rank. 



\section{On random convex sets}\label{S7}
One may seek a generalization of Theorem \ref{The4.2} to random convex sets
in, say, the two-dimensional plain, replacing the $2$-point sample by an $m$-point
sample for a certain $m$. We give counter-examples to such a possibility. 

First consider a convex polygon with $n$ edges, whose
vertices touch the edges of another convex $n$-polygon. The case of a regular hexagon
is depicted in Figure 3. Denote the set included in the smaller $n$-polygon by $G_0$,
and the $n$ triangles between the smaller polygon and the larger one by $G_1, ...,G_n$.
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{Figure3}
\caption{}
\end{figure}
Notice that the union of $G_0$ and the elements in any subset of $\{G_1, ..., G_n\}$,
is a convex set (we include in this count the empty set union $G_0$). There are $2^n$
such sets. 

Notice that if the sampling rule for the $2^n$ convex sets just described is regular,
say governed by the measure $\gamma$ on $R^2$, and if $\gamma$ assigns zero probability
to the boundaries of all $G_i$, say it is the Lebesgue measure, then the considerations of
Proposition \ref{Pro6.6} apply. Then the $m$-point statistics of a random convex set
supported on the $2^n$ sets determines the distribution if and only if
$m \ge n$. If $G_0$ is excluded from being a value, then Proposition \ref{Pro6.10} applies. 
Then the $m$-point statistics of a random convex set supported on the $2^n-1$ sets 
determines the distribution if and only if $m \ge n-1$. In particular, there is no bound on 
the least number $m$ that implies determination.

Furthermore, a variation of the example shows that if a denumerable number of convex values
is allowed, no $m$-point statistics is enough to determine the random set.
Indeed, consider a ``polygon'' like the one in Figure 3, with, however, a
denumerable number of edges.

Additional geometrical restrictions on the support of the random convex set,
may yield generalizations of the results for random intervals (homothetic
polygons may yield such estimates). The extent of such restrictions is not clear
at this point.





2021-07-22T02:17:06.000
2104
2104.12373
en
https://arxiv.org/abs/2104.12373
We examine the extent to which random samplings from the values of a random set, determine the distribution of the random set itself. We also comment on how, given the statistics of the sampling, to detect the distribution. Several methods are displayed, leading to positive results, counter-examples, and open problems.
Probability (math.PR)
Detecting random sets by samplings from their values
Qwen/Qwen-72B
1. YES
2. YES