Basic Definitions and Facts from Random Set Theory

[math] \newcommand{\edis}{\stackrel{d}{=}} \newcommand{\fd}{\stackrel{f.d.}{\rightarrow}} \newcommand{\dom}{\operatorname{dom}} \newcommand{\eig}{\operatorname{eig}} \newcommand{\epi}{\operatorname{epi}} \newcommand{\lev}{\operatorname{lev}} \newcommand{\card}{\operatorname{card}} \newcommand{\comment}{\textcolor{Green}} \newcommand{\B}{\mathbb{B}} \newcommand{\C}{\mathbb{C}} \newcommand{\G}{\mathbb{G}} \newcommand{\M}{\mathbb{M}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\T}{\mathbb{T}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\W}{\mathbb{W}} \newcommand{\bU}{\mathfrak{U}} \newcommand{\bu}{\mathfrak{u}} \newcommand{\bI}{\mathfrak{I}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cg}{\mathcal{g}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cu}{\mathcal{u}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \newcommand{\sF}{\mathsf{F}} \newcommand{\sM}{\mathsf{M}} \newcommand{\sG}{\mathsf{G}} \newcommand{\sT}{\mathsf{T}} \newcommand{\sB}{\mathsf{B}} \newcommand{\sC}{\mathsf{C}} \newcommand{\sP}{\mathsf{P}} \newcommand{\sQ}{\mathsf{Q}} \newcommand{\sq}{\mathsf{q}} \newcommand{\sR}{\mathsf{R}} \newcommand{\sS}{\mathsf{S}} \newcommand{\sd}{\mathsf{d}} \newcommand{\cp}{\mathsf{p}} \newcommand{\cc}{\mathsf{c}} \newcommand{\cf}{\mathsf{f}} \newcommand{\eU}{{\boldsymbol{U}}} \newcommand{\eb}{{\boldsymbol{b}}} \newcommand{\ed}{{\boldsymbol{d}}} \newcommand{\eu}{{\boldsymbol{u}}} \newcommand{\ew}{{\boldsymbol{w}}} \newcommand{\ep}{{\boldsymbol{p}}} \newcommand{\eX}{{\boldsymbol{X}}} \newcommand{\ex}{{\boldsymbol{x}}} \newcommand{\eY}{{\boldsymbol{Y}}} \newcommand{\eB}{{\boldsymbol{B}}} \newcommand{\eC}{{\boldsymbol{C}}} \newcommand{\eD}{{\boldsymbol{D}}} \newcommand{\eW}{{\boldsymbol{W}}} \newcommand{\eR}{{\boldsymbol{R}}} \newcommand{\eQ}{{\boldsymbol{Q}}} \newcommand{\eS}{{\boldsymbol{S}}} \newcommand{\eT}{{\boldsymbol{T}}} \newcommand{\eA}{{\boldsymbol{A}}} \newcommand{\eH}{{\boldsymbol{H}}} \newcommand{\ea}{{\boldsymbol{a}}} \newcommand{\ey}{{\boldsymbol{y}}} \newcommand{\eZ}{{\boldsymbol{Z}}} \newcommand{\eG}{{\boldsymbol{G}}} \newcommand{\ez}{{\boldsymbol{z}}} \newcommand{\es}{{\boldsymbol{s}}} \newcommand{\et}{{\boldsymbol{t}}} \newcommand{\ev}{{\boldsymbol{v}}} \newcommand{\ee}{{\boldsymbol{e}}} \newcommand{\eq}{{\boldsymbol{q}}} \newcommand{\bnu}{{\boldsymbol{\nu}}} \newcommand{\barX}{\overline{\eX}} \newcommand{\eps}{\varepsilon} \newcommand{\Eps}{\mathcal{E}} \newcommand{\carrier}{{\mathfrak{X}}} \newcommand{\Ball}{{\mathbb{B}}^{d}} \newcommand{\Sphere}{{\mathbb{S}}^{d-1}} \newcommand{\salg}{\mathfrak{F}} \newcommand{\ssalg}{\mathfrak{B}} \newcommand{\one}{\mathbf{1}} \newcommand{\Prob}[1]{\P\{#1\}} \newcommand{\yL}{\ey_{\mathrm{L}}} \newcommand{\yU}{\ey_{\mathrm{U}}} \newcommand{\yLi}{\ey_{\mathrm{L}i}} \newcommand{\yUi}{\ey_{\mathrm{U}i}} \newcommand{\xL}{\ex_{\mathrm{L}}} \newcommand{\xU}{\ex_{\mathrm{U}}} \newcommand{\vL}{\ev_{\mathrm{L}}} \newcommand{\vU}{\ev_{\mathrm{U}}} \newcommand{\dist}{\mathbf{d}} \newcommand{\rhoH}{\dist_{\mathrm{H}}} \newcommand{\ti}{\to\infty} \newcommand{\comp}[1]{#1^\mathrm{c}} \newcommand{\ThetaI}{\Theta_{\mathrm{I}}} \newcommand{\crit}{q} \newcommand{\CS}{CS_n} \newcommand{\CI}{CI_n} \newcommand{\cv}[1]{\hat{c}_{n,1-\alpha}(#1)} \newcommand{\idr}[1]{\mathcal{H}_\sP[#1]} \newcommand{\outr}[1]{\mathcal{O}_\sP[#1]} \newcommand{\idrn}[1]{\hat{\mathcal{H}}_{\sP_n}[#1]} \newcommand{\outrn}[1]{\mathcal{O}_{\sP_n}[#1]} \newcommand{\email}[1]{\texttt{#1}} \newcommand{\possessivecite}[1]{\ltref name="#1"\gt\lt/ref\gt's \citeyear{#1}} \newcommand\xqed[1]{% \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill \quad\hbox{#1}} \newcommand\qedex{\xqed{$\triangle$}} \newcommand\independent{\protect\mathpalette{\protect\independenT}{\perp}} \DeclareMathOperator{\Int}{Int} \DeclareMathOperator{\conv}{conv} \DeclareMathOperator{\cov}{Cov} \DeclareMathOperator{\var}{Var} \DeclareMathOperator{\Sel}{Sel} \DeclareMathOperator{\Bel}{Bel} \DeclareMathOperator{\cl}{cl} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\essinf}{essinf} \DeclareMathOperator{\esssup}{esssup} \newcommand{\mathds}{\mathbb} \renewcommand{\P}{\mathbb{P}} [/math]

This appendix provides basic definitions and results from random set theory that are used throughout this chapter..</ref> I refer to for a textbook presentation of random set theory, and to for a discussion focusing on its applications in econometrics. The theory of random closed sets generally applies to the space of closed subsets of a locally compact Hausdorff second countable topological space [math]\carrier[/math], see . In this chapter I let [math]\carrier = \R^d[/math] to simplify the exposition. Closedness is a property satisfied by random points (singleton sets), so that the theory of random closed sets includes the classical case of random points or random vectors as a special case. A random closed set is a measurable map [math]\eX:\Omega\mapsto\cF[/math], where measurability is defined by specifying the family of functionals of [math]\eX[/math] that are random variables.

Definition (Random closed set)

A map [math]\eX[/math] from a probability space [math](\Omega,\salg,\P)[/math] to the family [math]\cF[/math] of closed subsets of [math]\R^d[/math] is   called a random closed set if

[[math]] \begin{equation} \label{eq:X-} \eX^-(K)=\{\omega\in\Omega:\; \eX(\omega)\cap K\neq\emptyset\} \end{equation} [[/math]]

belongs to the [math]\sigma[/math]-algebra [math]\salg[/math] on [math]\Omega[/math] for each compact set [math]K[/math] in [math]\R^d[/math].

A random compact set is a random closed set which is compact with probability one, so that almost all values of [math]\eX[/math] are compact sets. A random convex closed set is defined similarly, so that [math]\eX(\omega)[/math] is a convex closed set for almost all [math]\omega[/math]. Definition~ means that [math]\eX[/math] is explored by its hitting events, i.e., the events where [math]\eX[/math] hits a compact set [math]K[/math]. The corresponding hitting probabilities are very important in random set theory, because they uniquely determine the probability distribution of a random closed set [math]\eX[/math], see . The formal definition of the hitting probabilities, and the closely related containment probabilities, follows.

Definition (Capacity functional and containment functional)

• A functional [math]\sT_\eX(K):\cK\mapsto[0,1][/math] given by
  [[math]] \sT_\eX(K)=\Prob{\eX\cap K\neq\emptyset},\quad K\in\cK, [[/math]]
  is called capacity (or hitting) functional of [math]\eX[/math].
• A functional [math]\sC_\eX(F):\cF\mapsto[0,1][/math] given by
  [[math]] \sC_\eX(F)=\Prob{\eX\subset F},\quad F\in\cF, [[/math]]
  is called the containment functional of [math]\eX[/math].

I write [math]\sT(K)[/math] instead of [math]\sT_{\eX}(K)[/math] and [math]\sC(K)[/math] instead of [math]\sC_{\eX}(K)[/math] where no ambiguity occurs.

Ever since the seminal work of , it has been common to think of random sets as bundles of random variables -- the selections of the random sets.

Definition (Measurable selection)

For any random set [math]\eX[/math], a (measurable) selection of [math]\eX[/math] is a random element [math]\ex[/math] with values in [math]\R^d[/math] such that [math]\ex(\omega)\in\eX(\omega)[/math] almost surely. I denote by [math]\Sel(\eX)[/math] the set of all selections from [math]\eX[/math].

The space of closed sets is not linear, which causes substantial difficulties in defining the expectation of a random set. One approach, inspired by and pioneered by , relies on representing a random set using the family of its selections, and considering the set formed by their expectations. If [math]\eX[/math] possesses at least one integrable selection, then [math]\eX[/math] is called integrable. The family of all integrable selections of [math]\eX[/math] is denoted by [math]\Sel^1(\eX)[/math].

Definition (Unconditional and conditional Aumann --or selection-- expectation)

The (selection or) Aumann expectation of an integrable random closed set [math]\eX[/math] is given by

[[math]] \E \eX = \cl \left\{ \int_\Omega \ex d\P: \; \ex \in \Sel^1(\eX) \right\}. [[/math]]

For each sub-[math]\sigma[/math]-algebra [math]\ssalg \subset \salg[/math], the conditional (selection or) Aumann expectation of [math]\eX[/math] given [math]\ssalg[/math] is the [math]\ssalg[/math]-measurable random closed set [math]\eY=\E(\eX|\ssalg)[/math] such that the family of [math]\ssalg[/math]-measurable integrable selections of [math]\eY[/math], denoted [math]\Sel^1_\ssalg(\eY)[/math], satisfies

[[math]] \begin{equation*} \Sel^1_\ssalg(\eY)=\cl\Big\{\E(\ex|\ssalg): \, \ex \in \Sel^1(\eX)\Big\}, \end{equation*} [[/math]]

where the closure in the right-hand side is taken in [math]\mathbf{L}^1[/math].

If [math]\eX[/math] is almost surely non-empty and its norm [math]\|\eX\|=\sup\{\|\ex\|:\; \ex\in \eX\}[/math] is an integrable random variable, then [math]\eX[/math] is said to be integrably bounded and all its selections are integrable. In this case, since [math]\eX[/math] takes its realizations in [math]\R^d[/math], the family of expectations of these integrable selections is already closed and there is no need to take an additional closure as required in Definition~, see . The selection expectation depends on the probability space used to define [math]\eX[/math], see and . In particular, if the probability space is non-atomic and [math]\eX[/math] is integrably bounded, the selection expectation [math]\E \eX[/math] is a convex set regardless of whether or not [math]\eX[/math] might be non-convex itself . This convexification property of the selection expectation implies that the expectation of the closed convex hull of [math]\eX[/math] equals the closed convex hull of [math]\E \eX[/math], which in turn equals [math]\E \eX[/math].

It is then natural to describe the Aumann expectation through its support function, because this function traces out a convex set's boundary and therefore knowing the support function is equivalent to knowing the set itself, see equation (eq:rocka) below.

Definition (Support function)

Let [math]K[/math] be a convex set. The support function of [math]K[/math] is

[[math]] h_K(u)=\sup\{k^\top u:\; k\in K\}\,, \qquad u\in\R^d\,, [[/math]]

where [math]k^\top u[/math] denotes the scalar product.

The support function is finite for all [math]u[/math] if [math]K[/math] is bounded, and is sublinear (positively homogeneous and subadditive) in [math]u[/math]. Hence, it can be considered only for [math]u \in \Ball[/math] or [math]u \in \Sphere[/math]. Moreover, one has

[[math]] \begin{equation} \label{eq:rocka} K=\cap_{u \in \Ball}\{k: k^\top u \leq h_K(u) \} =\cap_{u \in \Sphere}\{k: k^\top u \leq h_K(u)\}. \end{equation} [[/math]]

Next, I define the Hausdorff metric, a distance on the family [math]\cK[/math] of compact sets:

Definition (Hausdorff metric)

Let [math]K,L\in\cK[/math]. The Hausdorff distance between [math]K[/math] and [math]L[/math] is

[[math]] \rhoH(K,L)=\inf\Big\{r \gt 0:\; K\subseteq L^r,\; L\subseteq K^r\Big\}, [[/math]]

where [math]K^r=\{x: \dist(x,K)\le r\}[/math] is the [math]r[/math]-envelope of [math]K[/math].

Since [math]K\subseteq L[/math] if and only if [math]h_K(u)\leq h_L(u)[/math] for all [math]u\in\Sphere[/math] and [math]h_{K^r}(u)=h_K(u)+r[/math], the uniform metric for support functions on the sphere turns into the Hausdorff distance between compact convex sets. Namely,

[[math]] \begin{align} \rhoH(K,L)=\sup\Big\{|h_K(u)-h_L(u)|:\; \|u\|=1\Big\}. \label{eq:Hormander} \end{align} [[/math]]

It follows that

[[math]] \|K\|=\rhoH(K,\{0\})=\sup\big\{|h_K(u)|:\; \|u\|=1\big\}. [[/math]]

Finally, I define independently and identically distributed random closed sets (see ):

Definition (i.i.d. random closed sets)

Random closed sets [math]\eX_1,\dots,\eX_n[/math] in [math]\R^d[/math] are independent if and only if [math]\Prob{\eX_1\cap K_1 \ne \emptyset,\dots,\eX_n\cap K_n \ne \emptyset}=\prod_{i=1}^n\sT_{\eX_i}(K_i)[/math] for all [math]K_1,\dots,K_n \in \cK[/math]. They are identically distributed if and only if for each open set [math]G[/math], [math]\Prob{\eX_1\cap G \ne \emptyset}=\Prob{\eX_2\cap G \ne \emptyset}= \dots =\Prob{\eX_n\cap G \ne \emptyset}[/math].

With these definitions in hand, I can state the theorems used throughout the chapter. The first is a dominance condition due to (and ) that characterizes probability distributions of selections (see ):

Theorem (Artstein)

A probability distribution [math]\mu[/math] on [math]\R^d[/math] is the distribution of a selection of a random closed set [math]\eX[/math] in [math]\R^d[/math] if and only if

[[math]] \begin{equation} \label{eq:domin-t} \mu(K)\leq \sT(K)=\Prob{\eX\cap K\neq\emptyset} \end{equation} [[/math]]

for all compact sets [math]K\subseteq\R^d[/math]. Equivalently, if and only if

[[math]] \begin{equation} \label{eq:dom-c} \mu(F)\geq \sC(F)=\Prob{\eX\subset F} \end{equation} [[/math]]

for all closed sets [math]F\subset\R^d[/math]. If [math]\eX[/math] is a compact random closed set, it suffices to check \eqref{eq:dom-c} for compact sets [math]F[/math] only.

If [math]\mu[/math] from Theorem~ is the distribution of some random vector [math]\ex[/math], then it is not guaranteed that [math]\ex\in \eX[/math] a.s., e.g. [math]\ex[/math] can be independent of [math]\eX[/math]. Theorem~ means that for each such [math]\mu[/math], it is possible to construct [math]\ex[/math] with distribution [math]\mu[/math] that belongs to [math]\eX[/math] almost surely. In other words, [math]\ex[/math] and [math]\eX[/math] can be realized on the same probability space (coupled) as random elements [math]\ex^\prime[/math] and [math]\eX^\prime[/math] such that [math]\ex\edis\ex^\prime[/math] and [math]\eX\edis\eX^\prime[/math] with [math]\ex^\prime \in \eX^\prime[/math] a.s. The definition of the distribution of a random closed set (Definition) and the characterization results for its selections in Theorem require working with functionals defined on the family of all compact sets, which in general is very rich. It is therefore important to reduce the family of all compact sets required to describe the distribution of the random closed set or to characterize its selections.

Definition

A family of compact sets [math]\cM[/math] is said to be a core determining class for a random closed set [math]\eX[/math] if any probability measure [math]\mu[/math] satisfying the inequalities

[[math]] \begin{equation} \label{eq:cdclass} \mu(K)\leq \Prob{\eX\cap K\neq\emptyset} \end{equation} [[/math]]

for all [math]K\in\cM[/math], is the distribution of a selection of [math]\eX[/math], implying that \eqref{eq:cdclass} holds for all compact sets [math]K[/math].

The notion of a core determining class was introduced by . A simple and general, but still mostly too rich, core determining class is obtained as a subfamily of all compact sets that is dense in a certain sense in the family [math]\cK[/math]. For instance, in the Euclidean space, it suffices to consider compact sets obtained as finite unions of closed balls with rational centers and radii (e.g., ). For the case that [math]\eX[/math] is a subset of a finite space, propose a simple algorithm to compute core determining classes. provide a related algorithm. Throughout this chapter, several results are mentioned where the class of sets over which \eqref{eq:domin-t} is verified is reduced from the class of compact subsets of the carrier space, to a (significantly) smaller collection. The next result characterizes a dominance condition that can be used to verify the existence of selections of [math]\eX[/math] with specific properties for their means (see )

Theorem (Convexification in [math]\R^d[/math])

Let [math]\eX[/math] be an integrable random set. If [math]\eX[/math] is defined on a non-atomic probability space, or if [math]\eX[/math] is almost surely convex, then [math]\E \eX=\E \conv\eX[/math] and

[[math]] \begin{equation} \E h_\eX(u)=h_{\E \eX}(u),\quad u\in\R^d. \label{eq:supf} \end{equation} [[/math]]

If [math]\P[/math] is atomless over [math]\ssalg[/math], then [math]\E(\eX|\ssalg)[/math] is convex and

[[math]] \begin{equation} \E(h_\eX(u)|\ssalg)=h_{\E(\eX|\ssalg)}(u),\quad u\in\R^d. \label{eq:supf:cond} \end{equation} [[/math]]

Hence, for any vector [math]b\in\R^d[/math], it holds that

[[math]] \begin{align} b \in \E \eX &\Leftrightarrow b^\top u \le \E h_\eX(u)~~\forall u\in\Sphere,\label{eq:dom_Aumann}\\ b \in \E(\eX|\ssalg) &\Leftrightarrow b^\top u \le \E(h_\eX(u)|\ssalg)~~\forall u\in\Sphere.\label{eq:dom_Aumann:cond} \end{align} [[/math]]

An important consequence of Theorem is that it allows one to verify whether [math]b \in \E \eX[/math] without having to compute [math]\E \eX[/math] but only [math]\E h_\eX(u)[/math] (and similarly for the conditional case), a substantially easier task. Finally, i.i.d. random closed sets satisfy a law of large numbers and a central limit theorem that are similar to the ones for random singletons. Recall that the Minkowski sum of two sets [math]K[/math] and [math]L[/math] in a linear space (which in this chapter I assume to be the Euclidean space [math]\R^d[/math]) is obtained by adding each point from [math]K[/math] to each point from [math]L[/math], formally,

[[math]] K+L=\big\{x+y:\; x\in K,\;y\in L\big\}. [[/math]]

Below, [math]\eX_1+\cdots+\eX_n[/math] denotes the Minkowski sum of the random closed sets [math]\eX_1,\dots,\eX_n[/math], and [math](\eX_1+\cdots+\eX_n)/n[/math] denotes their Minkowski average.

Theorem (Law of large numbers for integrably bounded random sets)

Let [math]\eX,\eX_1,\eX_2,\ldots[/math] be i.i.d. integrably bounded random compact sets. Define [math]\eS_n=\eX_1+\cdots+\eX_n[/math]. Then

[[math]] \begin{align} \label{eq:LLN} \rhoH\left(\frac{\eS_n}{n},\E \eX\right)\to 0 \quad \text{a.s. as }\ n\to\infty. \end{align} [[/math]]

The support function of a random closed set [math]\eX[/math] such that [math]\E\|\eX\|^2 \lt \infty[/math], is a random continuous function [math]h_\eX(u)[/math] on [math]\Sphere[/math] with square integrable values. Define its covariance function as

[[math]] \begin{align} \Gamma_\eX(u,v)\equiv\E\left[(h_\eX(u)-h_{\E \eX}(u))(h_\eX(v)-h_{\E \eX}(v))\right], ~~u,v\in\Sphere. \label{eq:cov-Gamma} \end{align} [[/math]]

Let [math]\zeta(u)[/math] be a centered Gaussian random field on [math]\Sphere[/math] with the same covariance structure as [math]\eX[/math], i.e. [math]\E\big[\zeta(u)\zeta(v)\big]=\Gamma_\eX(u,v),~u,v\in\Sphere[/math]. Since the support function of a compact set is Lipschitz, it is easy to show that the random field [math]\zeta[/math] has a continuous modification by bounding the moments of [math]|\zeta(u)-\zeta(v)|[/math].

Theorem (Central limit theorem)

Let [math]\eX_1,\eX_2,\dots[/math] be i.i.d. copies of a random closed set [math]\eX[/math] in [math]\R^d[/math] such that [math]\E \|\eX\|^2 \lt \infty[/math], and let [math]\eS_n=\eX_1+\cdots+\eX_n[/math]. Then as [math]n\to\infty[/math],

[[math]] \begin{equation} \label{eq:h-weak} \sqrt{n}\Big(h_{\frac{\eS_n}{n}}(u)-h_{\E\eX}(u)\Big)\Rightarrow \zeta \end{equation} [[/math]]

in the space of continuous functions on the unit sphere with the uniform metric. Furthermore,

[[math]] \begin{equation} \label{eq:clt-basic} \sqrt{n}\rhoH\left(\frac{\eS_n}{n},\E \eX\right)\Rightarrow \|\zeta\|_\infty=\sup\big\{|\zeta(u)|:\; u\in\Sphere\big\}. \end{equation} [[/math]]

General references

Molinari, Francesca (2020). "Microeconometrics with Partial Identification". arXiv:2004.11751 [econ.EM].