3
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Various functions of distances to nearest neighbors and mean distances within neighborhoods have been used in spatial statistics for a long time: it's a huge literature and research into it will be rewarding. $\endgroup$ – whuber♦ Aug 23 '19 at 13:34
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the comment. That would completely ignore the underlying distance function. $\endgroup$ – amit Aug 24 '19 at 14:42
0
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the comment. I am wondering if this would just create a bias towards high probability points beig chosen into s, regardless of the distances. In many contexts you would like to choose S to be the "cheapest" possible, both in terms of its size, but also in terms of its probability (in cases where the "price" for a point is relative to its probability) $\endgroup$ – amit Aug 24 '19 at 14:40
  • $\begingroup$ To some extent you'd want the high probability points to be included otherwise probability would not have any impact on cover. To ensure that it doesn't matter too much, variance will ensure that S also has loosely connected points so that larger variance is "covered". It is somewhat an alternative to mean distance within S, as you suggested. As for cheapest S, I guess this question can be put in larger context of clustering. We create clusters in data and then get cover measure of each cluster. Then decide which one is cheapest. $\endgroup$ – Dayne Aug 25 '19 at 1:26
  • $\begingroup$ if I have two very high probability points nearby, it might be more efficient to "cover them" by a low probability point in between them, thus saving a point. In fact, an advanced version of the problem would try to find S with minimal cost. that is to find low probability points that cover high probability points, where the cost of a point is its probability, and the cover is a function of the distance function. $\endgroup$ – amit Sep 9 '19 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.