Runs test based on the median intuition The following document http://www.ifp.illinois.edu/~ywang11/paper/ECE461Proj.pdf contains a very nice summary of some nonparametric tests for randomness. My question concerns the popular Runs test based on the median. In this test, under the null hypothesis of randomness, every arrangement of "+" and "-"  signs is supposedly equiprobable.
According to this document, assume that the ordered sequence has $n$
samples, $n_{1}$ of +, $n_{2}$ of - and $n=n_{1}+n_{2}.$
Also, we denote the total number of runs of ``+'' as $R_{1}$ ,
and the number of runs of $"-"$ as $R_{2}$ ,and the total number
of runs as $R=R_{1}+R_{2}$. The author derives, for an even number
of runs $r$, the pdf of $R$ is
$$
f_{R}\left(r\right)=\left(_{n_{1}-1}C_{r/2-1}\right)\left(_{n_{2}-1}C_{r/2-1}\right)/_{n_{1}+n_{2}}C_{n_{1}}
$$
where $_nC_k = {{n}\choose{k}}$.
I have two questions:

*

*Why are $n_{1}$ and $n_{2}$ allowed to take on any values, and still
be compatible with randmoness? For instance, imagine that $n=n_{1}+1$
such that there is only one $n_{2}$ , and every other position is
occupied by an $n_{1}$. This does not seem random to me. In other
words, shouldnt a null distribution of randomness imply values of
$n_{1}$ and $n_{2}$ as well.



*How is the pdf derived? Why do we subtract $1$ from $n_{1},n_{2}$
and $r/2$ ?

Any guidance of this is much appreciated.
 A: Let us suppose we are interested in an even number of runs that can be written as $x$. The first thing to note is that under the null hypothesis we want any possible process of "+"s and "-"s to be equiprobable.
So then, how do we derive,
$$\Pr[R=x]=\frac{{{n_1-1}\choose{x/2-1}}{{n_2-1}\choose{x/2-1}}}{{n_1+n_2}\choose{n_1}}$$
First, since we want every potential sequence to be equiprobable what we need to do is find all the ways we could get a sequence with $R_1$ "+" runs and $R_2$ "-" runs and divide this by every possible way we can get a sequence of length $n_1+n_2$ with $n_1$ +'s. Essentially, we are just figuring out how many ways we could get the observed sequence and dividing it by the number of all the possible sequences we could have observed.
Now with that intuition all we need to do is find a mathematical way to express this. Let's start by defining our sequence.
Let $r_{-j}$ be the number of elements of "-" in the $j$-th run and let $r_{+j}$ be the number of elements of "+" in the $j$-th run. Then we must have that,
$$\sum^{R_1}_{j=1} r_{+j}=n_1$$
$$\sum^{R_2}_{j=1} r_{-j}=n_2$$
This is simply true from our observation of the sequence, and how we define runs, and the number of "+" and "-" elements.
Let us begin with the denominator. Recall that ${n}\choose{k}$ gives you all the possible ways (without considering order) that $k$ objects can be chosen from a collection of $n$ objects. Well in this case we just want to count how many possible sequences we can get. Since we have a sequence with $n_1$ "+"s (and we want to preserve that structure under the null) we can simply find this count from ${n_1+n_2}\choose{n_1}$.
Next, we can consider the numerator. Remember, for this value we want to figure out how likely it was we saw the number of runs of "+"s and "-"s that we observed. That is how many could the sums above hold.
First, since $x$ is even and "+" and "-" are equiprobable we expect $x/2$ "+" runs and $x/2$ "-" runs. In particular, we expect under the null that,
$$R_1=R_2=x/2$$
Intuitively, given $n_1$ "+" values how many ways can we get $x/2$ runs and $n_1$ "-" values how many ways can we get $x/2$ runs for both values. Well, we can just multiply these amounts to see how many ways we can $x/2$ "+" runs and $x/2$ "-" runs.
More formally, we want to know how many sequences $r_{+1},\dots,r_{+R_1}$ will satisfy the first sum. And how many sequences $r_{-1},\dots,r_{-R_2}$ will satisfy the second sum. This value is given by the number of compositions (also see the aside at the bottom). The composition tells us that there are,
$${{n_1-1}\choose{R_1-1}}={{n_1-1}\choose{x/2-1}}$$
sequences of ${r_+i}_i\in\mathbb{N}$ that satisfy this sum.
We have the exact same composition for $r_{-1},\dots,r_{-R_2}$ yielding,
$${{n_2-1}\choose{R_2-1}}={{n_2-1}\choose{x/2-1}}$$
possible sequences satisfying the second sum.
Since we are interested in how many times both of these events occur we multiply the two values together to get exactly our numerator in the pdf under the null for the case that $x$ is even.
So putting every thing together we get the pdf given in the notes,
$$\Pr[R=x]=\frac{{{n_1-1}\choose{x/2-1}}{{n_2-1}\choose{x/2-1}}}{{n_1+n_2}\choose{n_1}}$$
Finally you might be interested in reading the original paper by Wald and Wolfowitz from 1940: https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-11/issue-2/On-a-Test-Whether-Two-Samples-are-from-the-Same/10.1214/aoms/1177731909.full
A brief aside about the number of compositions: Essentially we want to build a number $n$ with $k$ numbers. So we want to know all the ways you can pick ${c_i}$ (the $k$ summands) so that $\sum_i^k c_i = n$. You can consider building a sequence [1_1_1..._1] which consists of $n$ ones. Then in each blank you can place either a "+" or a ",". So you have a total number of choices of $2^{n-1}$ since there are $n-1$ blanks and $2$ choices for each blank. And, since you want to find $k$ different $c_i$s you have to choose $k-1$ commas (to build each $c_i$) out of the $n-1$ blanks. And there is exactly ${n-1}\choose{k-1}$ ways to do this.
