2

Consider a metric space $(M,d)$, and let $D: M \times M \to \mathbb{R}_+$ be a measure of similarity on it, so that $D(x,y)$ is large when $x$ and $y$ are close (i.e., $d(x,y)$ is small).

Consider a collection of points $X := \{x_1,\dots,x_n\} \subset M$. Let $$ N_\epsilon(y;X) := | \{ x \in X: D(x,y) > \epsilon \}| $$ where the RHS is the cardinality of a set. For a set $Y \subset M$, define $$ N_\epsilon(Y;X) = \inf_{y \in Y} N_\epsilon(y;X) $$ Does this quantity look familiar, or is related to a more standard object?

passerby51
  • 4,140
  • 1
    Is there a reason you don't just use $d(x,y)<\epsilon$ instead of $D(x,y) > \epsilon$? What's the precise meaning of "$D$ is large when $d$ is small"? Either way, I don't recall seeing this before. – Anthony Carapetis Aug 22 '13 at 05:52
  • 1
    In what context did this arise? – dfeuer Aug 22 '13 at 07:15
  • @AnthonyCarapetis, the reason I am using $D$ is the way I have arrived at this quantity. You could define things in terms of $d$ as you pointed out, if that helps. – passerby51 Aug 22 '13 at 09:40
  • @dfeuer, it arised in studying the mixing time of of a Markov chain. I want a lower bound on $\sum_{x \in X} D(x,y)$, uniformly over $Y$, and this seemed natural. – passerby51 Aug 22 '13 at 09:42

0 Answers0