3
$\begingroup$

I know of ways to test "whether" two data sets come from the same distribution, in the sense that I can treat the hypothesis that they are from the same distribution as the null hypothesis. However, I want evidence that the hypothesis of sameness is correct.

For example, if I get a small p-value from a Kolmogorov-Smirnov test, that means that I can reject the hypothesis that the two data sets come from the same distribution, because it's very improbable that I would get this data if they were. However, as I understand the logic of null hypothesis testing, if my p-value is not small, this does (EDIT: not) justify the claim that the data comes from the same distribution.

If I'm misunderstanding p-values and null hypothesis testing, feel free to answer with an explanation. I'm also open to Bayesian methods.

There are a large number of stats.SE questions that are similar to mine, stated using "whether", "if", "compare", and the like, which makes it difficult to search for an answer to my question. So far, all of the answers I've found treat the hypothesis of sameness as the null, except for this one which doesn't have full answers. A pointer to good existing answers would be fine!

(My data is generated by two computer simulations that use methods that are clearly different in one small way--we wrote them--but that under some settings, produce distributions that look very similar. I am trying to show that under those settings, for all practical purposes we can treat the distributions as the same. I'm getting p-values around 0.225 from a Kolmogorov-Smirnov test.)

$\endgroup$
  • $\begingroup$ can you assume they have the same known parameteric form ? $\endgroup$ – peuhp Mar 29 '16 at 14:44
  • $\begingroup$ @peuhp, thanks. i.e. can I assume that the distributions are similar but for some differences in the parameters that describe them? No, I don't think I can do that. I just added a note explaining that the data is generated by computer simulations. The code's not complicated, but trying to work out the form of the distributions would be very difficult. $\endgroup$ – Mars Mar 29 '16 at 14:46
2
$\begingroup$

It's impossible to say with confidence that the two distributions are exactly the same, without making some fairly strong restrictions about what the two distributions could look like. Imagine a case where you want to compare a distribution $P$ to a distribution $Q = (1 - \varepsilon) P + \varepsilon Z$, where $\varepsilon$ is say $10^{-6}$. You probably won't even have any samples from $Z$ until you take about $10^{6}$ samples; even then, if the handful of samples you got from $Z$ are even vaguely plausible under $P$, it'll look fine.

What you can do is test this: "$P$ and $Q$ are almost the same." This sounds like what you want ("I am trying to show that under those settings, for all practical purposes we can treat the distributions as the same"). The problem is, what does "almost the same" mean? You'll need to specify some kind of distance between $P$ and $Q$.

The thing that makes this somewhat more complicated than the usual KS test-style setup is that we often can only easily derive the (asymptotic) distribution of whatever handy test statistic under the case when $P = Q$, but if we want our null distribution to be $P \ne Q$, then that doesn't help.


One natural distance is the total variation distance, which can be defined as $$ \operatorname{TV}(P, Q) = \sup_{f : \sup_x \lvert f(x) \rvert \le 1} \operatorname{\mathbb E}_{X \sim P}[ f(X) ] - \operatorname{\mathbb E}_{Y \sim Q}[ f(Y) ] = \sup_{\mathcal E} \lvert P(\mathcal E) - Q(\mathcal E) \rvert .$$ The total variation is the most that the two distributions can disagree on the probability of two events; equivalently, if you apply a function $f$ to the two distributions that is never large, it's the most that function $f$ can differ between the two distributions.

For discrete distributions, the following paper did something like what you want:

Chan, Diakonikolas, G. Valiant, and P. Valiant. Optimal Algorithms for Testing Closeness of Discrete Distributions. SODA 2013. (arXiv)

This paper gives a rate-optimal algorithm which distinguishes the case $P = Q$ from the case $\operatorname{TV}(P, Q) \ge \varepsilon$. That is, if you give it samples from two $P$ and $Q$ supported on an $\ell$-element discrete set which are at least $\varepsilon$ apart in total variation, then it'll correctly tell you that they're apart with high probability if you give it at least $\Omega(\max\{ n^{2/3} \varepsilon^{-4/3}, \ell^{1/2} \varepsilon^{-2} \})$ samples; likewise, if you give it two samples that are the same, it'll tell you with high probability that they're the same with enough samples. But if you give it distributions which are $\varepsilon/2$ apart in total variation, it might give you either answer (until you give it enough samples to distinguish with $\varepsilon/2$).

Unfortunately, as this is a theory paper, one of the inputs to the algorithm is "a suitable constant $C$." I'm not super familiar with this subarea, but I don't know if there is an implementable version of this algorithm that gives you something usable as a classical statistical test.


Another nice distance is the maximum mean discrepancy (MMD). This distance can be defined as $$ \operatorname{MMD}(P, Q) = \sup_{f : \lVert f \rVert_{\mathcal H} \le 1} \operatorname{\mathbb E}_{X \sim P}[ f(X) ] - \operatorname{\mathbb E}_{Y \sim Q}[ f(Y) ] ,$$ where $\lVert f \rVert_{\mathcal H}$ is the norm in a reproducing kernel Hilbert space. This means that if the MMD is small, applying any "smooth" function to the two distributions (where "smooth" is defined in terms of the RKHS kernel) will get you similar answers. MMD testing is usually done with the classic null hypothesis of $P = Q$; the standard reference is

Gretton, Borgwardt, Rasch, Schölkopf, and Smola. A Kernel Two-Sample Test. JMLR 13(Mar):723–773, 2012. (publisher page)

But, since I know more about MMD testing than I do about total variation on discrete distributions, let's figure out a test for the hypotheses \begin{gather} H_0 : \operatorname{MMD}(P, Q) > \varepsilon \qquad H_1 : \operatorname{MMD}(P, Q) < \varepsilon \tag{1} .\end{gather}

From Gretton et al. (2012), we know that the following is a simple estimator of the MMD: let $k$ be the kernel of the RKHS $\mathcal H$, and suppose we have $\{X_i\}_{i=1}^m \sim P^m$, $\{Y_i\}_{i=1}^n \sim Q^n$. Then the following is a reasonable estimator for $\operatorname{MMD}$: $$ \operatorname{MMD}_b^2(X, Y) = \frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m k(X_i, X_j) + \frac{1}{n^2} \sum_{i=1}^m \sum_{j=1}^n k(Y_i, Y_j) - \frac{2}{mn} \sum_{i=1}^m \sum_{j=1}^n k(X_i, Y_j) .$$ In particular, a one-sided analogue to their Theorem 7 tells us (via McDiarmid's inequality) that, when $0 \le k(x, y) \le K$ for all $x, y$, $$ \Pr\left( \operatorname{MMD}(P, Q) - \operatorname{MMD}_b(X, Y) > 2 \left( \sqrt{\frac{K}{m}} + \sqrt{\frac{K}{n}} \right) + t \right) \le \exp\left( \frac{- t^2 m n}{2 K (m + n)} \right) \tag{2} .$$ Thus we can say, with no assumptions about $P$ or $Q$ and holding exactly for all $m$ and $n$, with probability at most $\delta$ the true value of $\operatorname{MMD}(P, Q)$ is at most $$ \operatorname{MMD}_b(X, Y) + 2 \sqrt{K} \left( \frac{1}{\sqrt{m}} + \frac{1}{\sqrt{n}} \right) + \sqrt{2 K \left( \frac{1}{m} + \frac{1}{n} \right) \log\frac1\delta} ;$$ this tells you how "almost-the-same" you can confidently say the two distributions are.

If you'd prefer the hypothesis testing setup (1), you can easily manipulate (2) into giving you that as well: your $p$-value is just $$ \exp\left( \frac{- \left( \max\left\{ 0, \varepsilon - \operatorname{MMD}_b(X, Y) - 2 \sqrt{K} \left( \frac{1}{\sqrt{m}} + \frac{1}{\sqrt{n}} \right) \right\} \right)^2}{2 K \left( \frac1m + \frac1n \right)} \right) .$$

You could also probably use the asymptotic normal distribution of the MMD estimator to get a less-conservative asympotically-valid test. But I just noticed that this question is two years old, and so I won't write that out unless someone asks. :)

$\endgroup$
  • 1
    $\begingroup$ Thanks Dougal! I admit thhat don't know enough to understand all of that, but you've provided references, and study will get me close enough for safe usage, I believe. The immediate need that prompted the question has passed, but similar needs are likely to arise in the future. $\endgroup$ – Mars Feb 10 '18 at 5:27

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.