# Runs-Up/Down RNG test question.

There is not much relevant information to be found about Runs-Up/Down test on the great web. All I find is more or less just recycling the info than can be found in Knuth, The Art of Computer Programming Volume 2, 1998, pp. 66.

The Runs-Up/Down test should be run on a sample that has no ties between adjacent numbers (see Algorithm AS 157 on JSTOR or Knuth Vol.2). But what to do when I have ties between adjacent elements? My testing samples are random Integer numbers on interval from 0 to as low as 20 (usually the upper limit is around 150). In such sample there will be a lot of ties. The Algorithm AS 157 checks the sample and returns an error if ties are detected. But why should the Runs-Up test be limited to sample without ties?

To avoid ties I decided to check the sample and remove the ties (this lowers the sample size, but it is still well above the recommended minimum of 4000 elements). But then we noticed that the test will Fail badly for RNG on small interval (ex. 0 - 50), but Pass for larger intervals (ex. 0 - 300). Smaller RNG interval will produce more ties than larger interval, so this may be the cause of failed tests. Can anyone explain why?

Anyhow, the removing of ties is not OK because I should not alter the RNG output.

Another idea we had, was to let the ties and just re-define what an Up-Run is. We could say that the up run continues until the next number in a sequence is bigger or equal to previous number. But than what should I do with the length of run that contains ties. Should the run length be increased on a tie or not. Another problem is that I do not know if the matrix used in the algorithm remains the same (probably not).

So the question is: How can Runs-Up/Down test be used on a RNG sample of integers that have ties between adjacent numbers.

Note: The RNG is not causing the failed tests. Also the scaling of RNG output is not the cause (RNG usually outputs Integer from 0 to MAX_INT, this is than scaled to the desired interval). It has been tested on different "known to be good" RNG-s many many times.

Note2: When RNG is used only to produce shuffled arrays it will pass the test. For example, array [0,1,2...,14,15] is shuffled 1000 times to produce the output of length 15000 elements. Of course there can be ties between adjacent elements, but they are much rarer as the tie can occur only where two shuffled arrays "touch".

In the runs test, the mean and variance of the number of runs, which Google tells me are $$\mu = \frac{2N-1}{3} , \qquad \sigma^2 = \frac{16N - 29}{90},$$ are assuming that there will be no ties. So the correct thing to do to fix the test is to compute the mean and variance of the number of runs when ties are possible, and use these new values for seeing if the sample passes or fails.

To do this, imagine that all ties between adjacent values are arbitrarily broken: e.g. the run $1, 3, 5, 5, 8, 9$ is turned into $1, 3, 5, 5.1, 8, 9$ and $1, 3, 5.1, 5, 8, 9$ with equal probability. In that case, the single run is equally likely to remain a single run or to turn into three runs.

So we see that all ties contribute $1$ to the number of runs in expected value. (I'm ignoring the case of three or more equal elements in a row, which would have a different contribution but are much less likely.) Therefore the correct test statistic to use should be the number of runs plus the number of ties between adjacent values, and this will also have mean $\frac{2N-1}{3}$.

However, to apply the test, we also need to know the variance of this test statistic, which might be different from the $\sigma^2$ computed above.

Let $\mathbf R$ be the number of runs, $\mathbf T$ be the number of adjacent ties, and $\mathbf X = \mathbf R + \mathbf T$ be the test statistic. If there are $k$ possible values for the random numbers, then $\mathbf T$ has the $\text{Binomial}(N-1, \frac1k)$ distribution: there are $N-1$ chances for a tie to occur, and they occur independently with probability $\frac1k$. In particular, $\text{E}[\mathbf T] = \frac{N-1}{k}$ and $\text{Var}(\mathbf T) = (N-1)(\frac1k)(1 -\frac1k)$.

By the law of total variance, $$\text{Var}(\mathbf X) = \text{E}[\text{Var}(\mathbf X \mid \mathbf T)] + \text{Var}(\text{E}[\mathbf X \mid \mathbf T]).$$ For the first term, we have $\text{Var}(\mathbf X \mid \mathbf T) = \text{Var}(\mathbf R \mid \mathbf T)$. The distribution of $(\mathbf R \mid \mathbf T=t)$ - the number of runs, given that there are $t$ adjacent ties - is the same as the distribution of the number of runs in a sample of size $N - t$. So its variance is $\frac{16(N-t)-29}{90}$, and $\text{Var}(\mathbf X \mid \mathbf T) = \frac{16(N-\mathbf T)-29}{90}$. Finally, since $\text{E}[\mathbf T] = \frac{N-1}{k}$, the first term simplifies to $$\text{E}[\text{Var}(\mathbf X \mid \mathbf T)] = \frac{16(N-\frac{N-1}{k})-29}{90}$$ For the second term, we have $\text{E}[\mathbf X \mid \mathbf T=k] = \text{E}[\mathbf R \mid \mathbf T=t] + t$, and by the same argument as above, $\text{E}[\mathbf R \mid \mathbf T=t] = \frac{2(N-t)-1}{3}$. Therefore $\text{E}[\mathbf X \mid \mathbf T] = \frac{2(N-\mathbf T)-1}{3} + \mathbf T = \frac{2N-1}{3} + \frac{\mathbf T}{3}$. For the variance, the constant is irrelevant, and we just get $\text{Var}(\frac{\mathbf T}{3}) = \frac{N-1}{9} \cdot \frac1k \cdot (1 - \frac1k)$.

So, to summarize: the correct way to adjust for ties is to let $\mathbf X$ be the number of runs plus the number of ties, and compare it to a normal random variable with $$\mu = \frac{2N-1}{3},\quad \sigma^2 = \frac{16(N-\frac{N-1}{k})-29}{90} + \frac{N-1}{9} \cdot \frac1k \cdot \left(1 - \frac1k\right)$$ where $k$ is the number of possible values the random numbers can take on.

The variance is exactly correct, the mean is an approximation up to an order $\frac{N}{k^2}$ error term because I didn't take into account the number of triple ties: three consecutive elements, all equal.

• Thank you for answering, but what you presented here is very simplified runs test. Runs test (as described by Knuth) is not about average run length but about number of runs of length 1, 2, 3, 4, 5 and length 6 or more (look at both references in my question). – NonStandardModel Dec 5 '17 at 9:07
• Here I am also not measuring run length but number of runs. I am not breaking them down by length but that is a more straightforward adjustment: we should just figure out what is $\mu$ and $\sigma^2$ for number of runs of length $k$ for $k=1, 2, 3, 4, 5$. Unfortunately, I don't have access to your references... – Misha Lavrov Dec 5 '17 at 16:02
• Problematic part of this approach is that runs are not independent. Long runs have bigger probability to be followed by short run than being followed by another long run. – NonStandardModel Dec 5 '17 at 17:25
• The general approach should probably still work - see how breaking ties at random affects the number of runs, and adjust accordingly - but it's nontrivial to modify for the fancier version of the algorithm. – Misha Lavrov Dec 5 '17 at 20:46