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 paper, section 5. Are there any general procedure that can be applied to this problem.

Thank you.

  • $\begingroup$ 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. $\endgroup$ – James Martin May 30 at 13:40
  • $\begingroup$ 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. $\endgroup$ – Sudipta Roy May 30 at 15:48
  • $\begingroup$ 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$.") $\endgroup$ – Neal Young Jul 1 at 0:57
  • $\begingroup$ @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$? $\endgroup$ – Sudipta Roy Jul 1 at 4:56
  • $\begingroup$ 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)$. $\endgroup$ – Neal Young Jul 1 at 12:19

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)}$.


$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.

| cite | improve this answer | |
  • $\begingroup$ 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$?) $\endgroup$ – Neal Young Jul 1 at 1:08
  • $\begingroup$ @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$. $\endgroup$ – Sudipta Roy Jul 1 at 4:58
  • $\begingroup$ I don't think so, see my comment above following your post. $\endgroup$ – Neal Young Jul 1 at 12:20

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.