Given a set of real numbers $X$ and a subset $Y \subset X$, I would like to demonstrate that $Y$ is not a result of a uniform sampling from $X$.

One solution that I thought recall this, that is:

  1. Perform a uniform random sampling from $X$ to produce a subset $X_{unif} \subset X$ such that $|X_{unif}| = |Y|$.
  2. Perform a Kolgomorov-Smirnov test on $X_{unif}$ and $Y$ to assess that they come from two different distributions.

By the way I think that since I have the original set $X$ is somewhat useless/wrong to perform an additional random sampling.

Do anyone know something that could solve this problem?

  • 1
    $\begingroup$ in my opinion probability to sample a subset $Y_0$ is equal to probability of sampling any other set $Y_i$. In general you can not prove that this particular subset $Y$ was selected non-randomly - unless you have a prior knowledge of what type of bias was used during subsampling. If you have such knowledge - construct test statistic based on this knowledge, take 1000 subsamples of size |Y| and check how many test statistics from these 1000 subsamples exceed (or equal) to yours. This will be your p-value. $\endgroup$ – German Demidov Apr 10 '19 at 13:18
  • $\begingroup$ I am not sure to have understood, you are proposing to use the solution I show in the question? $\endgroup$ – BalrogOfMoria Apr 10 '19 at 13:25
  • $\begingroup$ If you change "produce a subset" to "produce subsets" - I would say yes, and Kolmogorov-Smirnov test looks like terribly bad choice if you want to use p-values from it - but even if you use just W I doubt if it is a good choice of statistic especially if |Y| is small and |X| is quite complex. $\endgroup$ – German Demidov Apr 10 '19 at 13:31
  • 1
    $\begingroup$ Why not just perform a K-S test to compare $Y$ directly to the uniform distribution on $X$? There's no need to construct a sample from $X$ in order to analyze your data! $\endgroup$ – whuber Apr 10 '19 at 13:32
  • 1
    $\begingroup$ @German I would just like to remark that the subtleties you were alluding to in earlier comments derive from the fact that under the null, every subset (of a given size) of $X$ has equal chances of being sampled. Thus, there's absolutely no way to distinguish this $Y$ from any other subset $Y^\prime.$ One makes progress by specifying an alternative to the null hypothesis: that is, exactly how could uniform sampling be violated? Might it consist, for instance, of unusually large or small gaps between the values of $Y$? Until the OP tells us this, it will be hard to justify any answer. $\endgroup$ – whuber Apr 10 '19 at 14:34

I would combine your idea of the KS-test and the answer below your question, if the size of the $X$ and/or $Y$ is small:

Sample (uniformly) $B$ times (e.g. $B=1000$) a subset $X_b$ of $X$ of size $|Y|$ and calculate the Kolmogorov-Smirnov statistic $D_b$ from $X_b$ and $X$. This gives you an empirical distribution of the values $D_b$.

Calculate $D^{\ast}$ as the Kolmogorov-Smirnov statistic from $Y$ and $X$ and assess how many of your $D_b$, $b=1,\ldots,B$ are larger than or equal to your $D^{\ast}$, this gives you the approximate $p$-value: $p=\#\lbrace D_b\geq D^{\ast} \rbrace/B$.

If $p$ is smaller than a pre-defined $\alpha$, you can reject the null hypothesis that $Y$ was sampled uniformly with error $\alpha$.

If $|X|$ and $|Y|$ are large, you can calculate the KS-statistic $D^{\ast}$ directly and use tabellarized values to assess significance.

  • $\begingroup$ $|X| \sim 3k$ and $|Y| \sim 6M$. Do you think that the two sizes allow to directly perform KS-test between $X$ and $Y$? $\endgroup$ – BalrogOfMoria Apr 10 '19 at 13:47
  • $\begingroup$ I guess it is the other way around, $|X|\approx6\cdot10^6$ and $|Y|\approx3\cdot10^3$? Yes, 3000 data points should be enough. $\endgroup$ – Edgar Apr 10 '19 at 14:54
  • $\begingroup$ Yes sorry, it is as you say. Thanks for the clarifications. $\endgroup$ – BalrogOfMoria Apr 10 '19 at 14:57

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.