How to actually compute the statistical distance? I have an algorithm for discrete sampling that I've defined. This is to say that $A$, upon input some pdf $p(x)$, outputs samples from the pdf $p(x)$. There are some nuances (you have to make the support of $p$ finite, so you're really only sampling from some distribution within some statistical distance $SD$ of the distribution of $p$), but nothing too complicated.
By statistical distance I imean the "Total Variation Distance":


  $$d(D_1,D_2) = \sum_{x\in\mathsf{supp}(D_1)\cup\mathsf{supp}(D_2)}\lvert \Pr[D_1 =x] - \Pr[D_2 = x]\rvert$$


Imagine I can (theoretically) prove that this process truly does sample from a distribution that's within $SD$ of the true distribution, and I want to implement this sampler. What are the typical ways to show that $A$ produces the distribution that it theoretically should? Given a perfect implementation, this wouldn't be an issue, but I'm hoping to use this to catch bugs.

There are easy naive things to do --- for example, draw some number of samples $(x_1,\dots,x_n)$, treat this as an empirical distribution, and compute the statistical distance between that and the (true) pdf $p(x)$. My worry about this is that the Statistical Distance problem is complete for the complexity class Statistical Zero Knowledge (see chapter 4 of Vadhan's thesis for a survey), which might hint that this is a poor method of finding bugs. 

Of course:


It could be that my instance of the problem is easy
My problem is presented in a slightly different form (SZK is a circuit class I believe)


Still, this makes me worry that checking the statistical distance of $A$ from $p(x)$ is an intractable problem. Is this true? Are there better algorithms for it than the naive one I mentioned above?
Prove your method correct.
Factor your code into a nondeterministic uniform bit sampler and deterministic logic.


You can use the full suite of standard software testing techniques for to test deterministic part.
You can use automated formal verification tools to prove the deterministic part is correctly implemented.
You can use well-studied cryptography—also with deterministic known-answer test vectors—seeded by observations from well-studied unpredictable physical models for the uniform bit sampler.





‘OK,’ you say, ‘but Shirley, you should be able to also use empirical hypothesis tests of random samples—after all, the goal is to test that a random sampler for a distribution is correct, so why not run it and apply a standard empirical hypothesis test of distribution to the samples?  Specifically, we can consider the null hypothesis that the software correctly samples from the intended distribution, and apply a hypothesis test with a specified statistical significance level for that null hypothesis!’

This is not wrong.  But there are several issues with it.


Empirical hypothesis tests of distributions are qualitatively different from the normal kinds of automatic tests you might be familiar with in software engineering, because they necessarily have false alarms:


A test for deterministic software properties rejects certain samples, because correct software cannot yield them—thus it is a bug if you encounter them.
A random test for the distribution of a null hypothesis rejects certain samples, even though correct software can yield them—the conceit, of course, is that buggy software will yield these rejected samples with much higher probability than correct software.


What do you do, then, when your test suite rejects the null hypothesis and raises an alarm?  Well, it might be a bug, or it might just be a fluke!  Better run it repeatedly to make sure that the rate of alarms is exactly what the significance level was set to—so maybe we should run a hypothesis test for the null hypothesis of iid Bernoulli trials weighted by the significance level, but what do you do if that test fails?  Well, it might be a bug, or it might just be a fluke…
For these empirical tests to be useful, they need high statistical power to detect the bugs that might be in your program.  So you need to hypothesize plausible bugs, and confirm that the tests have high statistical power to detect those bugs.


You could hypothesize specific bugs that occurred during development, and relatively easily make tests for them.

But, you could also just test those in the deterministic part of your program.
You could hypothesize bounds on statistical distances: null hypothesis, $D(P \mathbin\| Q) \leq \varepsilon$; alternative hypothesis, $D(P \mathbin\| Q) \geq \varepsilon + \delta$.  Then you can choose hypothesis tests that are guaranteed to have certain false alarm rates and statistical power for those alternative hypotheses.  You could even choose the two bounds to use different statistical distances, e.g. the null hypothesis might be bounded KL divergence while the alternative hypothesis is a bug of excess Hellinger distance.

But, the numbers of samples required for these tests to attain prescribed false alarm rates and statistical power are usually superlinear in $1/\varepsilon$ and $1/\delta$—if they exist at all with such guarantees, which for some statistical distances $D$ they do not!
You could just apply standard hypothesis tests and blindly hope they'll catch bugs.  Actually in practice this works quite well during development to catch obvious bugs early on.

But, it doesn't get you very far.

As your system gets bigger, you will be tempted to expand the tests you do.


With deterministic property tests, adding a test case to a test suite just means each run of the test suite takes a little more time.
With $n$ random hypothesis tests, if each test case has a false alarm rate $\alpha$, the test suite has a false alarm rate $1 - (1 - \alpha)^n$ which rapidly approaches $1$—i.e., false alarms nearly all the time—as $n$ increases.  What can you do when you add a new test?


Leave the false alarm rate of the test cases alone.

But, then if you had calibrated the test cases so that the test suite has a prescribed false alarm rate, that rate will go up as you add more tests—even if the software is working perfectly!
Whenever you add a test case, recalibate all the test cases to have false alarm rate $\alpha' &lt; \alpha$ so that $1 - (1 - \alpha)^n = 1 - (1 - \alpha')^{n + 1}$, i.e. choose $\alpha' = 1 - (1 - \alpha)^{n/(n + 1)}$.

But, the number of samples needed in each test case to maintain the same statistical power at lower false alarm rates tends to grow rapidly with $n$.
Give up on a notion of ‘tests passing’, and instead record a detailed history of test case runs on which you can do meta-analyses later.

But, software people don't like it when the answer from a test suite isn't just PASSED or FAILED, and none of the standard tools like Jenkins are designed to cope with such nonbinary fluidity of notions of test results, as is typical for the white cismale culture in Silicon Valley that dominates software engineering tooling.


My name is Squeamish, not Shirley.
If we're talking about cryptography, the statistical distances are generally going to be so small you don't have a snowball's chance in a Manhattan trash can on a summer day of detecting them anyway.  So go back to step 1: prove your method correct.


Of course, all of this depends on more details about what you're doing.  Maybe, for your application and your distribution and your sampler and your type of statistical distance and your bound $\varepsilon$ on magnitude of statistical distance and your tolerance $\delta$ on magnitude of statistical distance and your development process and your toolchain, you can actually address all these concerns, in which case, great!  Go for it!