Consider $a_1,\ldots, a_n$ to be $n$ unequal numbers and suppose these numbers are randomly permuted to obtain the sequence $h_1,\ldots, h_n$. Consider a new sequence $S$ whose $i^{th}$ element is the sign of $h_{i+1}-h_i$ $(i=1,\ldots, n-1)$. As an example, the sequence

$$2, 8, 13, 1, 3, 4, 7$$


$$S=+, +, -, +, +, +$$

which consists of $R=3$ runs. The mean and variance of $R$ is given by $\frac{2n-1}{3}$ and $\frac{16n-29}{90}$ and so the asymptotic normality of


can be used as a test of randomness in our sequence. It's not clear to me why $\mathbb E(R)=\frac{2n-1}{3}$. If we let

$$\mathbb 1_k= \begin{cases} 1&\text{ if the }k^{th}\text{ element of }S\text{ starts a new run}\\ 0&\text{ otherwise} \end{cases}$$

then it would seem to me that $\mathbb E(\mathbb 1_k)_{k\neq1}=\frac{1}{2}$ since we'd just need the $k^{th}$ sign to differ from the $(k-1)^{th}$ sign. And since $\mathbb 1_1=1$ then

$$\mathbb E(R)=1+\sum_{i=2}^{n-1}\mathbb E(\mathbb 1_k)=1+\frac{n-2}{2}=\frac{n}{2}$$

What is wrong with my logic?


1 Answer 1


Suppose we have observations $y_1,\ldots, y_n$ which are iid (or randomly permuted). Let

$$\mathbb{I}_i= \begin{cases} 1&\text{ if }y_i\text{ is an } ``\text{initial turning point"}\\ 0&\text{ otherwise} \end{cases}$$

We have that

$$\mathbb P(y_{i-1}<y_i>y_{i+1})=\mathbb P(y_{i-1}>y_i<y_{i+1})=\frac{1}{3}$$

and so

$$\mathbb E(\mathbb I_i)=\mathbb P(y_{i-1}<y_i>y_{i+1})+\mathbb P(y_{i-1}>y_i<y_{i+1})=\frac{2}{3}\quad(i=2,3,\ldots, n-1)$$

Also we have that $\mathbb E(\mathbb I_1)=1$ and $\mathbb E(\mathbb I_n)=0$. Altogether we have

$$\mathbb E(R) = \sum_{i=1}^n \mathbb E(\mathbb{I}_i) = 1+ \sum_{i=2}^{n-1} \mathbb E(\mathbb I_i)=1+\frac{2}{3}(n-2)=\frac{2n-1}{3}$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .