# A sequence of order statistics from an iid sequence

Note: This question was asked in stats.stackexchange.com and math.stackexchange.com, with expired bounties on both sites.

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).

Another way to describe this sequence of random vectors is that you have an unordered set of $k$ points, initially sampled independently, and at each step you add a point and then with probability $p$ remove the minimum, and with probability $1-p$ remove the maximum.

Given $x \in (0,1)$, the number of points in the $n$th set lower than $x$ follows a random walk on the set $\{0,1,...,k\}$ whose initial distribution is binomial (and unimportant) and whose transitions occur with the following probabilities except at the edges:

• $-1$ with probability $(1-x)p$: Add a point greater than $x$ and delete the minimum.

• $+1$ with probability $x(1-p)$: Add a point smaller than $x$ and delete the maximum.

• $0$ with the complementary probability $(1-x)(1-p) + xp$: Add a point greater than $x$ and delete the maximum or add a point smaller than $x$ and delete the minimum.

The boundary cases are that when there are no points smaller than $x$, this will still increase to $1$ with probability $x(1-p)$, but the chance to stay $0$ is $1-x(1-p)$, and when all $k$ points are smaller than $x$, this will decrease to $k-1$ with probability $(1-x)p$ and stay $k$ with probability $1-(1-x)p$.

The limiting distribution is the same as if you eliminate the chance to pick a new point lower than $x$ and then delete the minimum or to pick a point greater than $x$ and then delete the maximum.

The initial distribution doesn't matter. The limiting distribution of this random walk gives the limiting distributions for the coordinates, since the probability that the $\ell$th point is at most $x$ is the sum of the probabilities that there are exactly $\ell$, $\ell+1$, ... or $k$ points less than $x$. It does not say the joint distribution.

• It is possible to extract the joint distribution from the stable distribution of a similar but more complicated random walk. I may do this explicitly for $k=2$. – Douglas Zare Apr 29 '11 at 13:34
• @Douglas, thank you very much for the answer. I am sorry to comment 3 weeks after the answer, but in my defense this was not my question originally and although I was curious about answer, I did not find time to take in your answer properly. Your solution is pretty elegant, but I still have one question. The original question says that $X_i\sim U(0,1)$ without loss of generality, but your answer uses this. Am I right that for general distribution of $X$ the instead of $x$, $F(q)$ should be used where $q$ is the $x$-th quantile? – mpiktas May 16 '11 at 18:57