3
$\begingroup$

Taking into consideration the runs test proposed by Knuth given a sample of pseudo-random numbers to test independence, and looking at this example:

X = (5,4,1,7,2,3,6), which yields
S = (0,0,1,0,1,1)

I'm a bit confused if:

X = (5,4,1,**1**,2,3,6), would yield 
S = (0,0,1,**1**,1,1) ... call it option #1 or yield
S = (0,0,1,**0**,1,1) ... call it option #2

...and for the case of:

X = (5,**5**,1,7,2,3,6), should it yield
S = (**0**,0,1,0,1,1) ...call it option #1 or
S = (**1**,0,1,0,1,1) ...call it option #2

So what is it in the first and second cases and why?

$\endgroup$
1
  • $\begingroup$ For the record, Donald Knuth did not propose this test. He attributes it to an 1875 paper by J. Bienayme and its rigorous development finally to Levene and Wolfowitz (1944). He remarks explicitly that "the run test ... depends ... only on the fact that [ties do not occur]" [TAoCP Vol. II 3.3.2(M)]. $\endgroup$
    – whuber
    May 16, 2019 at 18:06

1 Answer 1

0
$\begingroup$

I believe the answer is that Knuth's run test is undefined for subsequent duplicates, and he intends such cases to be ignored during testing. That may sound strange, but there are reasons to think it's plausible.

(a) The description of the run test in TAOCP 3d ed doesn't clearly specify what to do when there are duplicates. The short example that Knuth gives contains no duplicates. Knuth is pretty careful about specifying such things, usually. The fact that he doesn't give instructions for cases in which there are adjacent duplicates suggests that the omission is intentional. (The sentence below about monotone runs is almost the same in the first and third editions, but the punctuation is different. If it didn't say what Knuth intended, it seems likely that he would have changed it.)

(b) Knuth's language is consistent with this assumption, if we interpret "increasing" as "strictly increasing":

"This means that we examine the length of monotone portions of the original sequence (segments that are increasing or decreasing)" (TAOCP 3d v2 p. 66, italics in original).

That is, we are only told to examine the (strictly) increasing or decreasing runs.

Exercise 12 on page 76, which concerns the run test, starts

"Let $U_0, U_1, . . . , U_{n−1}$ be $n$ distinct numbers."

i.e. we assume that there are no duplicates in the sequence.

(c) Knuth focused a great deal on linear congruent generators of the form $$x_{n+1}=(ax + c) \mod m$$ (All of the non-empirical tests assume that the generator is of this form.) These cannot produce duplicates until the full period is reached and the generator starts with the original value again. The only way to have adjacent duplicates is for the period to be 1, which would be useless.

Knuth definitely considered other generators, as @whuber emphasized in a comment, but it appears to me that most of the other generators that Knuth considered had relatively short periods. Knuth mainly focused on generators in which the number of bits in a result are not larger than the word size. So with a 32-bit word, for example, the maximum number of distinct numbers is $2^{32}$. If a generator is not a bad generator, then there should be adjacent duplicates very rarely, and it would be difficult to find duplicates unless the period was much greater than the the number of possible integers. I don't think Knuth considered such generators. (In the comments, @whuber gives an example of finding duplicates with runif() in R. This probably used a MersenneTwister RNG with period $2^{19937}-1$. The Mersenne Twister was introduced in 1997, just a year before Knuth published the 3rd edition of volume 2 of TAOCP.)

(My guess was that the statistical part of the run test would be have to be different if duplicates were allowed, and @whuber confirmed that in a comment.)

$\endgroup$
6
  • $\begingroup$ Yes, the statistical part of the test would be different if ties could occur with any appreciable frequency. Your argument at the outset confuses seeding a PRNG with running it: they are not the same thing! Internally, many PRNGs are short vectors of numbers. The PRNG deterministically converts a vector $x_n$ into another one $x_{n+1}$ and outputs a value $f_n=f(x_{n}).$ Seeding it, on the other hand, is a function from an integer (or string or whatever the seed might be) whose value is a vector $x_{0}.$ The fact that $x_n \ne x_{n+1}$ does not imply $f_n\ne f_{n+1}$! $\endgroup$
    – whuber
    May 16, 2019 at 18:12
  • $\begingroup$ BTW, in R I generated a million values with its uniform RNG runif after issuing a set.seed(68) instruction and found a pair of identical values of 0.62850067485123873 in succession (starting with the 893,593rd value). $\endgroup$
    – whuber
    May 16, 2019 at 18:23
  • $\begingroup$ @whuber, ah, that's very nice that you actually found successive duplicates. Cool. I believe that R's default PRNG is a Mersenne Twister; with its long period, I am not completely surprised, but I didn't now if that actually occurred. Yes, I made that mistake at first, but I think I have corrected it in the edit. It's still true that the LCGs that were Knuth's primary focus can't produce ties because they have no internal state. $\endgroup$
    – Mars
    May 17, 2019 at 1:11
  • $\begingroup$ As I recall, Knuth was discussing arbitrary sequences of numbers, not just linear congruential generators. See his section 3.2.2, "Other methods" and the introduction to section 3.3. $\endgroup$
    – whuber
    May 17, 2019 at 14:20
  • 1
    $\begingroup$ @whuber, maybe I should add that last point about other PRNGs considered by Knuth to my answer, and regardless, you have convinced me that the wording of the first half of my answer is misleading and I should revise it. $\endgroup$
    – Mars
    May 17, 2019 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.