0
$\begingroup$

Okay so I have a function in the shape of a black box that I'd like to test. It's characteristics are:

  • It gives either 0, 1 or -1 as output.
  • I can query it easily, producing tens of thousands of samples in short time.
  • I have no other prior information. I don't know the mean nor the variance.

My hypothesis is this: I want to test that it is "unbiased", in the sense that its mean is 0.

But I want to bias my testing in this way:

  • False positives (i.e. Type II errors) must be minimized.

For this p-value testing (at least as I understand it) won't work, since it tries to minimize false negatives. My project needs to reject my implementation of this function every time that it truly has a bias: if it's biased I should reject it, but if it isn't then it's okay to reject it with a low-ish probability.

What should I be doing? The textbook I'm using (Ang & Tang for Engineering) explicitly skips over Type II error mitigation, so I have no idea on how to proceed.


Edit: more details on the problem, since it seems I can't quite explain it myself.

My function receives a point in N dimensions, and generates the gradients of a Noise function that belongs to the family of Perlin Noise. These gradients are unitary, and are built in such a way that the values of every coordinate are either α or -α (at "random"), and then one of them is chosen at "random" as well and made 0. α depends on the number of dimensions, but suffice to say that it's built to make the gradient unitary.

By "random" I mean a deterministic process that for any given point, always produces the same results. This is an important property of the Noise functions. But it also must seem random, and that's where things get complicated. The process is as follows:

  1. Point gets feed into a hash function.
  2. Hash of the point is used as the seed for a pseudorandom generator.
  3. Generator is used to produce all "random" actions.

I can, and am, using now a cryptographic hash function and a cryptographic pseudorandom generator. Those should have no bias I could measure (at least in polynomial time), and therefore I'm more or less certain that my function is indeed unbiased if I give it random input (for which I'm also using a cryptographic pseudorandom generator). But for sanity, and in case I then decide to try faster hashers or generators, I want a test that can check if the unbiasedness holds (with a certain probability of failure).

To finalize: I'm more interested in rejecting biased functions than in accepting unbiased ones. That's what I don't know how to do.

$\endgroup$
1
$\begingroup$

You will need to accept some probability of accepting a biased box. (Otherwise, you will need to keep querying ad infinitum to be certain, because, who knows, the bias might only manifest with at least $10^{12}$ samples.)

And then you are squarely in the realm of testing. Indeed, you might want to look into and calculations, where you prespecify an $\alpha$ level (the probability of rejecting an unbiased box, could be the classical 0.05), a $\beta$ level for power (one minus the probability of not rejecting a biased box - in your situation, $\beta$ should probably be rather high) and an effect size that gives "practical bias" (is a bias of $10^{-2}$ relevant? $10^{-6}$? $10^{-28}$?). A power calculator, or a simple simulation, will then give you the required sample size for your experiment.

$\endgroup$
  • $\begingroup$ > You will need to accept some probability of accepting a biased box Of course! I know that I need infinite samples otherwise. I'm fine with, idk, 99% chance of rejecting a biased box. $\endgroup$ – felix91gr Jul 26 '18 at 6:39
  • $\begingroup$ Very good. Then the approach I outline should work. (And I don't understand why you write that p-value testing wouldn't work.) $\endgroup$ – S. Kolassa - Reinstate Monica Jul 26 '18 at 6:44
  • $\begingroup$ Sorry, tried to edit my comment but got cut off by the timer! Here's what I was trying to write: (Regarding the rest of your answer:) I'm sorry, I really don't understand most of that. Most importantly: - Where can I learn about power? - What tools allow me to calculate the effect size? And what is an effect in this context? Yes, I'm a noob on statistics. Sorry about that, but uni's course was pretty lame on statistical inference and I'm picking it back up after some years. $\endgroup$ – felix91gr Jul 26 '18 at 6:47
  • $\begingroup$ (I also realize that comment formatting doesn't allow for line breaks. Ouch, my last comment is kind of a pain to read) $\endgroup$ – felix91gr Jul 26 '18 at 6:50
  • $\begingroup$ No problem. Wikipedia is actually pretty good at power analysis. Essentially, you have four factors playing together: (1) your sample size $n$, (2) an effect size you are interested in which I called "practical bias", (3) the probability of rejecting an unbiased box which you will accept, which is the $\alpha$ level, and (4) the probability of detecting a "practically biased" box, which is $\beta$. Power analysis analyses the interplay between these four (always in the context of a specified experimental setup and analysis). ... $\endgroup$ – S. Kolassa - Reinstate Monica Jul 26 '18 at 7:08
1
$\begingroup$

Let me try to rephrase Stephan's answer: You will need to accept a box with some bias as unbiased, otherwise the procedure that you want does not exist.

Here is why: as you sample more and more points from your box, you narrow the range where it's mean is likely to be. Say, for illustration, after 100 points you know that the mean is $0 \pm 0.1$, and after 10000 points you know that the mean is $0 \pm 0.01$. The more you draw, the narrower the range, but it is always a range. At no point you will be able to say "yep, that's a zero mean box".

The solution is to call a box with mean in some interval, for example $(-0.01, 0.01)$, unbiased, and otherwise biased. Then you can do statistics with power, sample size, etc.

$\endgroup$
  • $\begingroup$ Mm, that seems very reasonable. I guess I didn't try to formalize the alternative hypothesis as something that wasn't "mean is not 0", which would need infinite samples. I think I can come up with a reasonable "unbiased range" for the number of dimensions I'm working on, and based on that build the inference scheme. $\endgroup$ – felix91gr Jul 26 '18 at 7:22

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.