# Expectation of $R$ in runs up and down test

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$$

gives

$$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

$$\frac{R-\frac{2n-1}{3}}{\sqrt{\frac{16n-29}{90}}}$$

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

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+1})=\mathbb P(y_{i-1}>y_i

and so

$$\mathbb E(\mathbb I_i)=\mathbb P(y_{i-1}y_{i+1})+\mathbb P(y_{i-1}>y_i

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}$$