Why does l'Ecuyer reject p-values close to 1?

Question

When applying several tests to a given generator, p-values smaller than 0.01 or larger than 0.99 are often obtained by chance even if the RNG behaves correctly with respect to these tests (such values should normally appear approximately 2% of the time). In this case, suspicious values would not reappear systematically (unless we are extremely unlucky). (Source, page 6.)

Here's result where the test MaxOft AD produces a p-value close to 1 and so the RNG fails that test.

========= Summary results of SmallCrush =========
[...]
The following tests gave p-values outside [0.001, 0.9990]:
[...]
Test p-value
----------------------------------------------
[...]
6 MaxOft AD 1 - 3.6e-06
[...]
----------------------------------------------
All other tests were passed
[...]

NIST SP 800-22 calls such values "perfect randomness" (page 1-4, that is, PDF-page 16).

If a P-value for a test is determined to be equal to 1, then the sequence appears to have perfect randomness. A P-value of zero indicates that the sequence appears to be completely non-random.

So, what's wrong with a p-value close to 1?

Answer 1

So, what's wrong with a p-value close to 1?

Because random sequences don't look 'perfectly random' (or, rather, they have a low probability of doing so). We're checking if this sequence quacks [1] like a perfectly random sequence; acting 'too uniform' is evidence that it is not.

---

[1]: from the proverb "if it acts like a duck, and it quacks like a duck, then it is a duck". Fairly common where I am; however you never know how regional sayings like this are..