Return to Question

Suppose we are given points $P_1,\cdots,P_m$ in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1. An probability distribution $p_{i,j}$ is assigned for $1\leq i,j\leq m$, that is $p_{i,j}\geq 0$ and $\sum_{i,j} p_{i,j}=1$.

For a given constant $\epsilon>0$, we have the following inequality holds $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Now the question is to ask whether it is always possible to clustering these points into groups such that

1. Any two points in the same group has distance no more than $\epsilon'$.

2. The total joint probability between points of difference groups is less than $\delta$.

$\epsilon',\delta$ only depend on $\epsilon$, not on $n,m$. As long as $\epsilon$ goes to 0, $\epsilon',\delta$ go to 0.

Let $P_1,\cdots,P_m$ be points in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1.

Let $p_{i,j}$ be a probability distribution on pairs of these points, that is for $1\leq i,j\leq m$, $p_{i,j}\geq 0$ and $\sum_{i,j} p_{i,j}=1$.

Let $\epsilon>0$ be such that $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Is there a way to choose $\epsilon'$ and $\delta$ and cluster these points into groups satisfying these three conditions?

1. $\epsilon'$ and $\delta$ only depend on $\epsilon$, not on $n,m$. As $\epsilon$ goes to 0, $\epsilon'$ and $\delta$ go to 0 also.

2. Any two points in the same group have distance less than $\epsilon'$.

3. The total probability of pairs of points from different groups is less than $\delta$.

Suppose we are given points $P_1,\cdots,P_m$ in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1. An probability distribution $p_{i,j}$ is given for $1\leq i,j\leq m$.

For a given constant $\epsilon>0$, we have the following inequality holds $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Now the question is to ask whether it is always possible to clustering these points into groups such that

1. Any two points in the same group has distance no more than $\epsilon'$.

2. The total joint probability between points of difference groups is less than $\delta$.

$\epsilon',\delta$ only depend on $\epsilon$, not on $n,m$. As long as $\epsilon$ goes to 0, $\epsilon',\delta$ go to 0.

Suppose we are given points $P_1,\cdots,P_m$ in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1. An probability distribution $p_{i,j}$ is assigned for $1\leq i,j\leq m$, that is $p_{i,j}\geq 0$ and $\sum_{i,j} p_{i,j}=1$.

For a given constant $\epsilon>0$, we have the following inequality holds $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Now the question is to ask whether it is always possible to clustering these points into groups such that

1. Any two points in the same group has distance no more than $\epsilon'$.

2. The total joint probability between points of difference groups is less than $\delta$.

$\epsilon',\delta$ only depend on $\epsilon$, not on $n,m$. As long as $\epsilon$ goes to 0, $\epsilon',\delta$ go to 0.

Suppose we are given points $P_1,\cdots,P_m$ in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1. An probability distribution $p_{i,j}$ is given for $1\leq i,j\leq m$.

For a given constant $\epsilon>0$, we have the following inequality holds $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Now the question is to ask whether it is always possible to clustering these points into groups such that

1. Any two points in the same group has distance no more than $\epsilon'$, which only depends on $\epsilon$, not on $n,m$.

2. The total joint probability between points of difference groups is less than $\delta$, which only depends on $\epsilon$, not on $n,m$.

Suppose we are given points $P_1,\cdots,P_m$ in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1. An probability distribution $p_{i,j}$ is given for $1\leq i,j\leq m$.

For a given constant $\epsilon>0$, we have the following inequality holds $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Now the question is to ask whether it is always possible to clustering these points into groups such that

1. Any two points in the same group has distance no more than $\epsilon'$.

2. The total joint probability between points of difference groups is less than $\delta$.

$\epsilon',\delta$ only depend on $\epsilon$, not on $n,m$. As long as $\epsilon$ goes to 0, $\epsilon',\delta$ go to 0.