# A sequence of order statistics from an iid sequence

Given a sequence of iid random variables $X_i$ (without loss of generality from $U(0,1)$), an integer $k \ge 1$ and some $p \in (0,1)$, construct the sequence of random vectors $Z^{(j)}$, $j=0,1,...$ in the following way. Let

$$Z^{(0)}=(X_{(1)},...,X_{(k)}),$$

where $X_{(l)}$ is the $l$-order statistic of sample $\{X_1,...,X_k\}$. Introduce notations

\begin{align} Z^{(j)}&=(Z_{j,1},...,Z_{j,k}),\\ m_j&=\min(Z_{j-1,1},...,Z_{j-1,k},X_{k+j}),\\ M_j&=\max(Z_{j-1,1},...,Z_{j-1,k},X_{k+j}) \end{align}

Then

$$Z^{(j)}=(Y_{(1)},...,Y_{(k)})$$

where $Y_{(l)}$ is the $l$-order statistic of the following set which is

1. The set $\{Z_{j-1,1},...,Z_{j-1,k},X_{k+j}\}\backslash m_j$ with probability $p$
2. The set $\{Z_{j-1,1},...,Z_{j-1,k},X_{k+j}\}\backslash M_j$ with probability $1-p$

The decision between cases 1. and 2. is made independently from the $X_i$ (and hence from the $Z^{(i)}$).

The $Z^{(j)}$ are supported on the $k$-dimensional simplex $S_k = \{(x_1, \dots, x_k) \in \mathbb{R}^k \, | \, 0 \le x_1 \le x_2 \le \dots \le x_k \le 1 \}$.

It appears that the $Z^{(j)}$ converge in distribution. Is this known? Is anything known about the limiting distribution?

For the case $k=1$, the answer is the following. Denote the cdf of $Z^{(j)}$ by $F_j$.

The cdf of $\min(X_{n+1},Z^{(n)})$ (for $U(0,1)$ case) is

$$x+F_n(x)−xF_n(x)$$ and the cdf of $\max(X_{n+1},Z^{(n)})$ is

$$xF_n(x)$$.

Hence

\begin{align} F_{n+1}(x)&=p(x+F_n(x)−xF_n(x))+(1−p)xF_n(x)\\ &=px+(p(1-x)+(1-p)x)F_n(x) \end{align}

Since $p(1-x)+(1-p)x\in(0,1)$ we have that

$$\lim F_{n}(x)=\frac{px}{1-p(1-x)-(1-p)x}$$

I am looking for general results (case $k>1$) either for the limiting distribution of the whole vector $Z^{(j)}$ or of some of its components (marginal distributions).

-

## migrated from stats.stackexchange.comApr 18 '11 at 10:44

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

Cleaned up old, no-longer relevant comments. Said comments are still on display in the original posting at Stats.SE. –  Willie Wong Apr 18 '11 at 11:44

I've asked this question in mathoverflow. It has one answer, which I do not find time to check, so I am giving the link as an answer here.

-
The answer given there is very useful, thank you for posting it there. –  Hans Engler Nov 23 '12 at 17:07

EDIT I actually had a different answer for this question referring to markov chains, but then I saw a different and better way of solving the problem. So I changed my answer - can post the old one back if people want it

Now $Z^{(m)}$ will be a function of $X_1,\dots,X_{k+m-1}$. In particular it will be a function of the order statistics of this set.

For a uniformly distributed variable $X_i$, if we take a collection of $k+m-1$ of them, the rth order statistic has a beta distribution:

$$X_{(r)}\sim Beta(r,k+m-r)$$

Now what will the process have done by the mth step? It will have removed the top $n_t$ order statistics and the bottom $n_b$, with the constraint that $n_t+n_b=m-1$. Stated this way the probability of any such set occurring is given by the binomial distribution:

$$Pr(n_t)={m-1 \choose n_t}p^{n_t}(1-p)^{m-1-n_t}$$

Now given $n_t$ is the number chosen, we have $Z^{(m)}=(X_{(m-n_t)},\dots,X_{(k+m-1-n_t)})$ Now the joint distribution of $Z^{(m)}$ which looks like:

$$P(Z^{(m)}|n_t)=\frac{(k+m-1)!X_{(m-n_t)}^{m-1-n_t}(1-X_{(k+m-1-n_t)})^{n_t}}{(m-1-n_t)!(n_t)!}dX_{(m-n_t)}\dots dX_{(k+m-1-n_t)}$$

Which is a Dirichlet distribution with parameters $(m-n_t,1,1,\dots,1,n_t+1)$ with $k-2$ 1's in the middle (which is a general result for the joint distribution of order stats - not sure if its known).

Now we need to sum out $n_t$ with respect to its probability:

$$P(Z^{(m)})=\sum_{n_t=0}^{m-1}P(n_t)P(Z^{(m)}|n_t)$$ $$=\frac{(k+m-1)!}{(m-1)!}\sum_{n_t=0}^{m-1}{m-1 \choose n_t}^{2}\left[(1-X_{(k+m-1-n_t)})p\right]^{n_t}\left[X_{(m-n_t)}(1-p)\right]^{m-1-n_t}$$

Which looks tantalizingly close to a binomial distribution, if it wasn't for that annoying squared term in the summation. I don't know an exact solution for this summation. This is a far as I could get. You would likely require numerical work for this.

-
+1, good idea, Markov is probably the way to go, but still there is a lot of details to fill in to get to the final answer. –  mpiktas Apr 7 '11 at 14:01
@mpiktas - you should prob remove the +1 unless you think my new answer is still good. This is allowed right? or should I have posted a second answer? –  probabilityislogic Apr 7 '11 at 14:57
@probabilityislogic maybe I'm not following your argument, but consider the $k=2$ case where the first four observations are 0.5, 0.4, 0.6, and 0.2. Assume the coin flips are such that we discard the min at step 3 and discard the max at step 4. This leaves the set $\{0.2, 0.5\}$ which does not match your description, i.e., it has a "hole" in the middle of the order statistics of the four observations. –  cardinal Apr 7 '11 at 15:18
@probabilityislogic - the point that cardinal observed is that the $Z^{(m)}$ is not necessarily of the form $(X_{(m-n_t)}, \dots, X_{(m-n_t+k-1)})$. It's not formed by deleting the $n_t$ largest and $(m-1-n_t)$ smallest entries from $(X_{(1)}, \dots, X_{(m+k-1)})$, where $n_t \sim B(m-1,p)$. –  Hans Engler Apr 7 '11 at 15:58
@cardinal - yeah, I'm thinking I should remove this answer –  probabilityislogic Apr 18 '11 at 12:58