0
$\begingroup$

Given a set of $n\in\Bbb N$ integers $\mathcal S$, suppose we choose two sets:

$$\mathcal S_{\mathsf{small}}\subseteq\mathcal S$$ $$\mathcal S_{\mathsf{big}}\subseteq\mathcal S$$ with cardinalities $$|\mathcal S_{\mathsf{small}}|\approx n^s$$ $$|\mathcal S_{\mathsf{big}}|\approx n^{1-s}$$where $s\in\big(0,\frac12\big]$ independently with uniform distribution what is the asymptotic probability (Stirling or appropriate approximation) that we will have $$\mathcal S_{\mathsf{small}}\subseteq\mathcal S_{\mathsf{big}}\mathsf?$$

What if we replace $n^s$ by $(\log n)^s$ and $n^{1-s}$ by $\frac{n}{(\log n)^s}$ where now $s\in(0,1)$?

$\endgroup$
3
  • $\begingroup$ I think the answer is zero(!) Presumably $\mathcal S$ is meant to be of size $n$ and the elements of the two subsets are selected at random. The probability that a given element belongs to $S_\text{big}$ is then $n^{-s}$, so that the probability that $S_\text{small}\subset S_\text{big}$ is $\left(n^{-s}\right)^{n^s}$. That is, zero. $\endgroup$ Oct 25, 2015 at 21:44
  • $\begingroup$ I posted there but there were no takers.. I was getting summation of binomial coeffs so I thought there may be a precise expression $\endgroup$
    – user76479
    Oct 26, 2015 at 0:45
  • $\begingroup$ @ChristianRemling how did you get exp(-s/(1-2s))? $\endgroup$
    – user76479
    Oct 26, 2015 at 0:46

1 Answer 1

0
$\begingroup$

Intuitively, it should approach zero fast as soon as $|\mathcal S_{\mathsf{big}}|$ is at all smaller than $n$ (even like $n/2$) because virtually all subsets $\mathcal S_{\mathsf{small}}$ will contain some element not in $\mathcal S_{\mathsf{big}}$.

(Quick edit: I am assuming that $\mathcal S_{\mathsf{big}}$ and $\mathcal S_{\mathsf{small}}$ are each drawn indpendently and uniformly at random from the set of all subsets of $\mathcal S$ having the specified size.)

Let $a = |\mathcal S_{\mathsf{big}}|$ and $b = |\mathcal S_{\mathsf{small}}|$. For any realization of $\mathcal S_{\mathsf{big}}$, there are ${a \choose b}$ possible realizations of $\mathcal S_{\mathsf{small}}$ contained in $\mathcal S_{\mathsf{big}}$. There are ${n \choose b}$ total possible realizations of $\mathcal S_{\mathsf{small}}$. Hence the probability of containment is exactly \begin{align} \frac{{a \choose b}}{{n \choose b}} &= \frac{a!}{(a-b)!} \frac{(n-b)!}{n!} \\ &= \frac{a(a-1)\cdots(a-b+1)}{n(n-1)\cdots(n-b+1)}. \end{align} For $b$ small compared to $n$, this is essentially $\left(\frac{a}{n}\right)^b$. That is exactly the answer you'd get if you had fixed $\mathcal S_{\mathsf{big}}$ and picked $\mathcal S_{\mathsf{small}}$ by drawing $b$ elements independently (although this method would create duplicates). More precisely, $\left(\frac{a}{n}\right)^b$ is an upper bound on $\Pr[\mathcal S_{\mathsf{small}} \subseteq \mathcal S_{\mathsf{big}}]$, and a lower bound is $\left(\frac{a-b}{n-b}\right)^b$.

For your examples, we get probabilities upper-bounded by $\left(\frac{n^{1-s}}{n}\right)^{n^s} = n^{-s n^s}$ and by $(\log n)^{-s(\log n)^s}$. Of course both of these approach zero fast.

A necessary condition for a limit of $\delta > 0$ as $n,a,b \to \infty$ is that $\left(\frac{a}{n}\right)^b \geq \delta$. I think this implies something like $a = n\left(1 - \frac{O(1)}{b}\right)$.

$\endgroup$
8
  • $\begingroup$ you mean $(\log n)^{-s(\log n)^s}$? $\endgroup$
    – user76479
    Oct 26, 2015 at 0:47
  • $\begingroup$ So $\lim_{s\rightarrow0}f(n,s)=1$ for where $f=n^{-sn^s}$ or $f=(\log n)^{-s(\log n)^s}$ and if $n^s\rightarrow c$ or $(\log n)^s\rightarrow c$, we get $\Theta(1)$ $\endgroup$
    – user76479
    Oct 26, 2015 at 0:49
  • $\begingroup$ @Arul, sure, but that limit is a bit weird to me: For a fixed $n$, the limit as $s \to 0$ just is the case where $s=0$, so $S_{big} = S$ and $S_{small} = \emptyset$, so the probability is $1$. $\endgroup$
    – usul
    Oct 26, 2015 at 0:52
  • $\begingroup$ yah but you could shrink $s$ when $n$ goes up and fix $n^s=c$ or $(\log n)^s=c$ or for that matter if we replace $c$ by something that grows only slightly fast we get probability $0$ and so in that sense we have $\mathcal S_{big}\neq \mathcal S$ as $s\rightarrow0$. $\endgroup$
    – user76479
    Oct 26, 2015 at 0:53
  • $\begingroup$ Agreed, I am trying to get at a similar idea in the last line as well. For instance, if you want $b = \log n$, then you should have $a$ be at least something like $n - n/\log(n)$. $\endgroup$
    – usul
    Oct 26, 2015 at 0:55