<p>Ok, I think I have figured it out.</p>

<p>Define <span class="math-container">$I=\{\lambda\in [k] : \phi(N_\lambda) &lt; \frac{1}{4k}\}$</span> and <span class="math-container">$J=[k]\setminus I$</span>. Both the size of <span class="math-container">$I$</span> and <span class="math-container">$J$</span> is at most k.</p>

<p>Define the event <span class="math-container">$\mathcal{E}_{(\lambda)}=\exists$</span> and index <span class="math-container">$s_\lambda$</span> such that <span class="math-container">$r_{s_\lambda}\in N_\lambda$</span>. Clearly <span class="math-container">$\mathcal{E_s} = \cap_{\lambda\in[k]} \mathcal{E}_{(\lambda)}$</span>.</p>

<p>Hence </p>

<p><span class="math-container">$Pr[\mathcal{E_s}] = Pr[\cap_{\lambda\in[k]} \mathcal{E}_{(\lambda)}] = 1- Pr[\cup_{\lambda\in[k]} \bar{\mathcal{E}}_{(\lambda)}] \geq 1 - \sum_{\lambda\in[k]}Pr[\bar{\mathcal{E}}_{(\lambda)}] = 1 - \sum_{\lambda\in I}Pr[\bar{\mathcal{E}}_{(\lambda)}] - \sum_{\lambda\in J}Pr[\bar{\mathcal{E}}_{(\lambda)}]$</span>. </p>

<p>The second to last inequality is due to union bound. Now we do case analysis. Note that the event <span class="math-container">$\bar{\mathcal{E}}_{(\lambda)}$</span> is equivalent to saying that <span class="math-container">$R$</span> does not contain any point from <span class="math-container">$N_\lambda$</span>.</p>

<p><strong>Case I : <span class="math-container">$\lambda\in I$</span></strong></p>

<p>In this case <span class="math-container">$Pr[\bar{\mathcal{E}}_{(\lambda)}] = (1-\phi(N_\lambda))^s\leq exp(-s\phi(N_\lambda))$</span>.
So if <span class="math-container">$s\geq \frac{1}{\phi(N_\lambda)}\ln(\frac{2m_1}{\delta})\geq 4k\ln(\frac{2}{\delta})$</span>, we have <span class="math-container">$Pr[\bar{\mathcal{E}}_{(\lambda)}] \leq \frac{\delta}{2m_1}$</span>. Note that we can assume that <span class="math-container">$m_1\geq 1$</span>, otherwise this case does not occur.</p>

<p><strong>Case II: <span class="math-container">$\lambda\in J$</span></strong></p>

<p>In this case <span class="math-container">$Pr[\bar{\mathcal{E}}_{(\lambda)}]\leq (1-\frac{1}{4k})^s \leq exp(-\frac{s}{4k})$</span>. Hence</p>

<p><span class="math-container">$\sum_{\lambda\in J}Pr[\bar{\mathcal{E}}_{(\lambda)}]\leq m_2.exp(-\frac{s}{4k})\leq k.exp(-\frac{s}{4k})\leq \frac{\delta}{2}$</span> if <span class="math-container">$s\geq 4k\ln(\frac{2k}{\delta})$</span>.</p>

<p>Combining the two cases, we have if <span class="math-container">$s=Ck\ln(\frac{2k}{\delta})$</span>, for some sufficiently large contant <span class="math-container">$C&gt;0$</span>, we have <span class="math-container">$Pr[\mathcal{E}_s]\geq 1-\delta$</span>.</p>

<p>Please if anybody goes through the proof, mention any error that may have incurred.</p>

<p>Thank you.</p>

<p><strong>P.S.</strong> A thousand apologies for poor formatting. </p>

CC BY-SA 4.0
2020-07-01T01:08:45.933Z
Doesn't Case 1 have an error?  Note that $\phi(N_\lambda) \ln(2m_1/\delta)$ can be arbitrarily large (even infinite), so it's not enough to have $s\ge 4k\ln(2/\delta)$.  Aren't you using the inequality in the wrong direction?  (Also, minor comment: what is $m_1$?)
Neal Young
CC BY-SA 4.0
2020-07-01T04:58:37.313Z
@NealYoung, yes I think that might be the problem with this arguement. $m_1$ and $m_1$ be the size of $I$and $J$. Can this even be done so that the sample size if indepenedent of $n$ and $d$? The point is that it works for $k=1$.
Sudipta Roy
CC BY-SA 4.0
2020-07-01T12:20:51.460Z
I don't think so, see my comment above following your post.
Neal Young
CC BY-SA 4.0
2020-05-31T18:07:31.743Z
2020-05-31T18:07:31.743Z
Sudipta Roy
<p>Suppose <span class="math-container">$X$</span> is a set of <span class="math-container">$n$</span> points in <span class="math-container">$\mathbb{R}^d$</span> and <span class="math-container">$N_1,\cdots,N_k$</span> are k disjoint (unknown)subsets of <span class="math-container">$X$</span>. There is a probability distribution <span class="math-container">$\phi$</span> on <span class="math-container">$X$</span> defined as <span class="math-container">$\phi(p) = \frac{\lvert\lvert p\rvert\rvert}{\sum_{q\in X}\lvert\lvert q\rvert\rvert}$</span>. We sample points from <span class="math-container">$X$</span> according to this distribution. Moreover we also asume that <span class="math-container">$\phi(\cup_{i=1}^k N_i) &gt; 1/2$</span>. So a point sampled from <span class="math-container">$X$</span> would likely to be in <span class="math-container">$\cup_{i=1}^k N_i$</span>. Suppose we sample <span class="math-container">$s$</span> points from <span class="math-container">$X$</span> according to <span class="math-container">$\phi$</span>. Let <span class="math-container">$R=\{ r_1,\cdots,r_s\}$</span> be the sample. Define the event <span class="math-container">$\mathcal{E}_s\equiv \forall\lambda\in[k],\exists s_\lambda\in[s] s.t. r_{s_\lambda}\in N_\lambda$</span>. So if the event <span class="math-container">$\mathcal{E}_s$</span> occurs, the sample has at least one point from every subset.</p>

<p>What is the required sample size <span class="math-container">$s$</span> so that <span class="math-container">$\mathcal{E}_s$</span> occurs with failure probability at most <span class="math-container">$\delta$</span>?</p>

<p>Note that if <span class="math-container">$k=1$</span>, then the situation is quite simple. We need roughly <span class="math-container">$\log(\frac{1}{\delta})$</span> samples so that the sample contains at least one point from <span class="math-container">$N_1$</span> with probability at least <span class="math-container">$1-\delta$</span>.</p>

<p>This seems like an instance of hitting set problem. The motivation comes from <a href="https://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.53" rel="nofollow noreferrer">this</a> paper, section 5.
Are there any general procedure that can be applied to this problem.</p>

<p>Thank you.</p>

CC BY-SA 4.0
2020-05-30T13:40:34.633Z
Do you have some particular asymptotics in mind? It sounds like you're happy with the approximation $\log(1/\delta)$ for $k=1$. If you are letting $\delta\to0$ and keeping everything else fixed, then the answer is still $\log(1/\delta)$ for any given $k$ (by the union bound, it's enough to reduce the probability of missing each $N_i$ to $\delta/k$). If you want to consider $k\to\infty$ and $\delta\to0$ at the same time, or something similar, the answer can get more complicated. "Coupon collector with unequal probabilities" gets quite a few google hits, that could be a good place to start.
James Martin
CC BY-SA 4.0
2020-05-30T15:48:57.037Z
My hope is that the required sample size is independent of size of $X$, and polynomial in $k$ and $1/\delta$. By my assumption, there is a subset $N_\lambda$ such that $\phi(N_\lambda)>1/2k$. So roughly $k\log(1/\delta)$ samples are required to pick a point from $N_\lambda$. The problem is that there may be subsets with low probability mass.
Sudipta Roy
CC BY-SA 4.0
2020-07-01T00:57:41.743Z
It's not bounded, is it?  The probability of choosing a point in the union of the $N_i$'s is at least one half, but that doesn't preclude the probability of choosing a point in a given $N_i$ from being very small.  E.g. consider $d=1$, $n=k=2$ and $N_1 = \{0\}$, $N_2 = \{1\}$, $X=\{0,1\}$, so $\phi(0) = 0$ and $\phi(1) = 1$.  Even if you sample forever you will never hit $N_1$.  What am I missing?  (Or what do you mean "occurs with failure probability at most $\delta$"?  I assume you mean, "occurs with probability at least $1-\delta$.")
Neal Young
CC BY-SA 4.0
2020-07-01T04:56:09.173Z
@NealYoung , thanks for pointing that out. Yes the probability can be arbitrarily small. But suppose that none the probabilty is zero. In that case can there be a bound on the sample size that is indepenedent of $n$ and $d$?
Sudipta Roy
CC BY-SA 4.0
2020-07-01T12:19:45.573Z
Consider replacing 0 and 1 with $\epsilon$ and $1-\epsilon$ for an arbitrarily small $\epsilon>0$ in the previous example.  Then $\phi(\epsilon)=\epsilon$ and $\phi(1-\epsilon)=1-\epsilon$.  Then you need about $k$ rounds where $(1-\epsilon)^k \approx 1-\delta$, i.e. $k\approx \delta/\epsilon$.  So you can't have an upper bound that's independent of $\min_i \phi(N_i)$.
Neal Young
<ds.algorithms><pr.probability><randomized-algorithms>
Required sample size to hit certain subset of a ground set
Sudipta Roy
# Required sample size to hit certain subset of a ground set

(Asked by: username_0 on 2020-05-30)

Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N\_1,\cdots,N\_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\lvert p\rvert\rvert}{\sum\_{q\in X}\lvert\lvert q\rvert\rvert}$. We sample points from $X$ according to this distribution. Moreover we also asume that $\phi(\cup\_{i=1}^k N\_i) > 1/2$. So a point sampled from $X$ would likely to be in $\cup\_{i=1}^k N\_i$. Suppose we sample $s$ points from $X$ according to $\phi$. Let $R=\{ r\_1,\cdots,r\_s\}$ be the sample. Define the event $\mathcal{E}\_s\equiv \forall\lambda\in[k],\exists s\_\lambda\in[s] s.t. r\_{s\_\lambda}\in N\_\lambda$. So if the event $\mathcal{E}\_s$ occurs, the sample has at least one point from every subset.

What is the required sample size $s$ so that $\mathcal{E}\_s$ occurs with failure probability at most $\delta$?

Note that if $k=1$, then the situation is quite simple. We need roughly $\log(\frac{1}{\delta})$ samples so that the sample contains at least one point from $N\_1$ with probability at least $1-\delta$.

This seems like an instance of hitting set problem. The motivation comes from [this](https://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.53) paper, section 5.
Are there any general procedure that can be applied to this problem.

Thank you.

**Tags:** ds.algorithms, pr.probability, randomized-algorithms

> **Comments:**
> **username_1**: Do you have some particular asymptotics in mind? It sounds like you're happy with the approximation $\log(1/\delta)$ for $k=1$. If you are letting $\delta\to0$ and keeping everything else fixed, then the answer is still $\log(1/\delta)$ for any given $k$ (by the union bound, it's enough to reduce the probability of missing each $N_i$ to $\delta/k$). If you want to consider $k\to\infty$ and $\delta\to0$ at the same time, or something similar, the answer can get more complicated. "Coupon collector with unequal probabilities" gets quite a few google hits, that could be a good place to start.  
> **username_0**: My hope is that the required sample size is independent of size of $X$, and polynomial in $k$ and $1/\delta$. By my assumption, there is a subset $N_\lambda$ such that $\phi(N_\lambda)>1/2k$. So roughly $k\log(1/\delta)$ samples are required to pick a point from $N_\lambda$. The problem is that there may be subsets with low probability mass.  
> **username_2**: It's not bounded, is it?  The probability of choosing a point in the union of the $N_i$'s is at least one half, but that doesn't preclude the probability of choosing a point in a given $N_i$ from being very small.  E.g. consider $d=1$, $n=k=2$ and $N_1 = \{0\}$, $N_2 = \{1\}$, $X=\{0,1\}$, so $\phi(0) = 0$ and $\phi(1) = 1$.  Even if you sample forever you will never hit $N_1$.  What am I missing?  (Or what do you mean "occurs with failure probability at most $\delta$"?  I assume you mean, "occurs with probability at least $1-\delta$.")  
> **username_0**: @NealYoung , thanks for pointing that out. Yes the probability can be arbitrarily small. But suppose that none the probabilty is zero. In that case can there be a bound on the sample size that is indepenedent of $n$ and $d$?  
> **username_2**: Consider replacing 0 and 1 with $\epsilon$ and $1-\epsilon$ for an arbitrarily small $\epsilon>0$ in the previous example.  Then $\phi(\epsilon)=\epsilon$ and $\phi(1-\epsilon)=1-\epsilon$.  Then you need about $k$ rounds where $(1-\epsilon)^k \approx 1-\delta$, i.e. $k\approx \delta/\epsilon$.  So you can't have an upper bound that's independent of $\min_i \phi(N_i)$.  

---

## 1 answers

### Answer by username_0 on 2020-05-31. Score: 0

Ok, I think I have figured it out.

Define $I=\{\lambda\in [k] : \phi(N\_\lambda) < \frac{1}{4k}\}$ and $J=[k]\setminus I$. Both the size of $I$ and $J$ is at most k.

Define the event $\mathcal{E}\_{(\lambda)}=\exists$ and index $s\_\lambda$ such that $r\_{s\_\lambda}\in N\_\lambda$. Clearly $\mathcal{E\_s} = \cap\_{\lambda\in[k]} \mathcal{E}\_{(\lambda)}$.

Hence

$Pr[\mathcal{E\_s}] = Pr[\cap\_{\lambda\in[k]} \mathcal{E}\_{(\lambda)}] = 1- Pr[\cup\_{\lambda\in[k]} \bar{\mathcal{E}}\_{(\lambda)}] \geq 1 - \sum\_{\lambda\in[k]}Pr[\bar{\mathcal{E}}\_{(\lambda)}] = 1 - \sum\_{\lambda\in I}Pr[\bar{\mathcal{E}}\_{(\lambda)}] - \sum\_{\lambda\in J}Pr[\bar{\mathcal{E}}\_{(\lambda)}]$.

The second to last inequality is due to union bound. Now we do case analysis. Note that the event $\bar{\mathcal{E}}\_{(\lambda)}$ is equivalent to saying that $R$ does not contain any point from $N\_\lambda$.

**Case I : $\lambda\in I$**

In this case $Pr[\bar{\mathcal{E}}\_{(\lambda)}] = (1-\phi(N\_\lambda))^s\leq exp(-s\phi(N\_\lambda))$.
So if $s\geq \frac{1}{\phi(N\_\lambda)}\ln(\frac{2m\_1}{\delta})\geq 4k\ln(\frac{2}{\delta})$, we have $Pr[\bar{\mathcal{E}}\_{(\lambda)}] \leq \frac{\delta}{2m\_1}$. Note that we can assume that $m\_1\geq 1$, otherwise this case does not occur.

**Case II: $\lambda\in J$**

In this case $Pr[\bar{\mathcal{E}}\_{(\lambda)}]\leq (1-\frac{1}{4k})^s \leq exp(-\frac{s}{4k})$. Hence

$\sum\_{\lambda\in J}Pr[\bar{\mathcal{E}}\_{(\lambda)}]\leq m\_2.exp(-\frac{s}{4k})\leq k.exp(-\frac{s}{4k})\leq \frac{\delta}{2}$ if $s\geq 4k\ln(\frac{2k}{\delta})$.

Combining the two cases, we have if $s=Ck\ln(\frac{2k}{\delta})$, for some sufficiently large contant $C>0$, we have $Pr[\mathcal{E}\_s]\geq 1-\delta$.

Please if anybody goes through the proof, mention any error that may have incurred.

Thank you.

**P.S.** A thousand apologies for poor formatting.

> **Comments:**
> **username_2**: Doesn't Case 1 have an error?  Note that $\phi(N_\lambda) \ln(2m_1/\delta)$ can be arbitrarily large (even infinite), so it's not enough to have $s\ge 4k\ln(2/\delta)$.  Aren't you using the inequality in the wrong direction?  (Also, minor comment: what is $m_1$?)  
> **username_0**: @NealYoung, yes I think that might be the problem with this arguement. $m_1$ and $m_1$ be the size of $I$and $J$. Can this even be done so that the sample size if indepenedent of $n$ and $d$? The point is that it works for $k=1$.  
> **username_2**: I don't think so, see my comment above following your post.  

---

