coverage index?

Question

Suppose I have a space of potential outcomes X with a probability distribution on it. I assume that there is a distance function between elements of X (e.g. X is a metric space). I also have a set S of points in X. I want to measure how well S "covers" X. intuitively "covers" means here that a random point in X should be close to some extent to a point in S. I thought of a few directions. For example: cover(S) = E(d(x,S)) where d(x,S) is the minimum distance between x and a point in S, and the expectation is taken over all points in X. another alternative is to have parameter r and compute the probability of the set of all points in X whose distance from S is less than r. or the dual approach setting p as a parameter and compute the minimal distance from S required to achieve a subset of probability p or above.

After settling on such a "covering index" there are questions like, what is the expectation of the size of S to achieve certain covering, how to choose minimal covering sets etc.

Before moving on with my musings on assessing coverage, I wonder if there is anything like this in the literature (I come from a computer science background - so there is plenty of covering problems discussed there, without regard to probability at all. and would like to know if statisticians have considered this problem or similar ones). Any reference and/or thought would be much appreciated.

Answer 1

From what I understand, you're asking about a measure of how "typical" are points in set $S$ for the random variable $X$. The most straightforward approach, is to look at the probability of observing points in $S$ according to the distribution of $X$, i.e.

$$ \int_{s\in S} \,f_X(s)\,ds $$

More typical values, would appear with higher probability, so this seems to answer your problem. Setting up thresholds also seems straightforward, since you only need to decide on the probability cut-off, and then, from what I understand, seek for the highest density interval, if this is what you're after.

Answer 2

Just an attempt:

How about finding the center of $S$ (the definition of center needs to be chosen based on the context and definition of metric in your metric space $X$). In your case, the center may be chosen using probability, e.g., it could be the mean or median in $S$.

Let this center be defined as $c(S) \in S$.

Consider the space: $X_S$ which has $S$ replaced by $c(S)$.

Now consider $cover(S)=\frac{Var(X_S)}{Var(X)}$

This tells you how much of the variation in X is just covered by $S$ alone.

Of course, whether this makes sense would totally depend on the context of its use. But this can be one of the definitions I guess.