2
$\begingroup$

Assume that we have a random set $B$ which is constructed by selecting elements from $U = \{ X_1, \dots, X_n \}$ where $X_i$ are independent samples from Gaussians with means $\mu_i$ and variances $\sigma_i^2 = 1$.

I am interested at is selecting a subset of $m \le n$ vectors that are closest to the origin according to their Euclidean norm.

Let $A$ be the set constructed by applying same rule to the set $W = \{ \mathbb E[X_1], \dots, \mathbb E[X_n] \} = \{ \mu_1, \dots, \mu_n \}$. I want to ask if there are such problems in probability/learning theory literature and whether there are concentration (or anti-concentration) bounds for them. More specifically I am interested in bounds that bound the following event

$$\Pr[ |A \ominus B| \ge t]$$

where $A \ominus B = (A \setminus B) \cup (B \setminus A)$ (i.e. the symmetric difference between $A$ and $B$) and $t \in \mathbb N - \{ 0 \}$.

Intuitively I want to find references where the "expected set" $A$ is "close" (or not) to the actual set $B$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Please give an example of what rules you are referring to. Also avoid using two versions of $A$ that look so similar. Many other letters are available $\endgroup$
    – Yuval Peres
    Commented Feb 1, 2021 at 1:49
  • $\begingroup$ @YuvalPeres Thank you very much! I updated my response with a more specific instance of the problem. $\endgroup$
    – bolzano
    Commented Feb 1, 2021 at 13:52
  • 1
    $\begingroup$ Could you explain what you mean by constructing a set by selecting elements from $U$? $\endgroup$
    – Will Sawin
    Commented Feb 2, 2021 at 2:12
  • $\begingroup$ As Will Sawin wrote- please explain. E.g. Give an explicit example of a rule used to select $B$ $\endgroup$
    – Yuval Peres
    Commented Feb 2, 2021 at 4:16
  • $\begingroup$ Except I'm missing something, isn't $|A \ominus B| = n$ w.p $1$ (simply because the distribution of $X_1$ admits a density). $\endgroup$
    – dohmatob
    Commented Feb 3, 2021 at 22:45

0

Reset to default

You must log in to answer this question.