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


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}



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



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

  • $\begingroup$ 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$. $\endgroup$ – Douglas Zare Apr 29 '11 at 13:34
  • $\begingroup$ @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? $\endgroup$ – mpiktas May 16 '11 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.