Find the quantity: $P \left(\bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \} \right)$

Question

Let $U_1,...,U_n$ be i.i.d. $U(0,1)$ and $U_{(1)},...,U_{(n)}$ be their order statistics. For $n=1,2,...$, find the quantity: $$ P \left(\bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \} \right) $$ where $0 \le \alpha \le 1$.

My approach:

We can write $$ \begin{align*} P \left(\bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \} \right) & = E \left[ I_{\bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \}} \right] \\ & = E \left[ \prod_{j=1}^{n} I_{\bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \}} \right] \\ & = E \left[ E \left [ \prod_{j=1}^{n} I_{\bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \}} | U_{(n)} \right ] \right ] \\ & = E \left[ E \left [ \prod_{j=1}^{n} I_{\bigcap_{j=1}^{n} \left \{\frac{U_{(j)}}{U_{(n)}} > \frac{\alpha j}{nt} \right \}} | U_{(n)}=t \right ] \right ] \\ & = E \left[ \prod_{j=1}^{n} P \left \{ \frac{U_{(j)}}{U_{(n)}} > \frac{\alpha j}{nt} \right \} \right ] \ \text{using Basu's Theorem} \\ \end{align*} $$

I am not sure if I am doing this the right way. I used the fact that $\left \{ \frac{U_{(1)}}{U_{(n)}},...,\frac{U_{(n-1)}}{U_{(n)}} \right \}$ and $U_{(n)}$ are independent. Even if this is correct, how should I compute the probability in the last step? Is there an easier way out?

Thanks.

Answer 1

Probability of the complementary event is $$P\left[\bigcup_{j=1}^n\left\{\frac{nU_{(j)}}{j}\le \alpha\right\}\right]=P\left[\min_{1\le j\le n}\left\{\frac{nU_{(j)}}{j}\right\}\le \alpha\right]$$

Using induction we can show that $T_n=\min\limits_{1\le j\le n}\left\{\frac{nU_{(j)}}{j}\right\}$ has a uniform distribution on $(0,1)$.

For $n=1$, clearly $T_1=U_1 \sim U(0,1)$. Now suppose $T_{k-1}\sim U(0,1)$.

Then for $x\in [0,1]$,

\begin{align} P(T_k \le x)&=\int_0^1 P(T_k\le x \mid U_{(k)}=t)f_{U_{(k)}}(t)\,dt \\&=\int_0^x f_{U_{(k)}}(t)\,dt + \int_x^1 P(T_k\le x \mid U_{(k)}=t)f_{U_{(k)}}(t)\,dt \\&=\int_0^x k t^{k-1}\,dt + \int_x^1 P\left(T_{k-1}\le \left(\frac{k-1}{kt}\right)x \mid U_{(k)}=t \right)kt^{k-1}\,dt \tag{1} \\&= x^k + \int_x^1 \left(\frac{k-1}{kt}\right) x\cdot kt^{k-1}\,dt \tag{2} \\&= x \end{align}

---

In $(1)$, we used

\begin{align} T_k \le x &\iff \min_{1\le j\le k-1}\left\{\frac{k U_{(j)}}{j}\right\} \le x \qquad \left[\because\, x<t<1 \right] \\& \iff \min_{1\le j\le k-1}\left\{\frac{(k-1) U_{(j)}}{jt}\right\} \le \left(\frac{k-1}{kt}\right) x \\& \iff T_{k-1} \le \left(\frac{k-1}{kt}\right) x \end{align}

And $(2)$ follows from $(1)$ using the independence of $\left(\frac{U_{(1)}}{U_{(k)}},\frac{U_{(2)}}{U_{(k)}},\ldots,\frac{U_{(k-1)}}{U_{(k)}}\right)$ and $U_{(k)}$.

---

So, $T_k \sim U(0,1)$ whenever $T_{k-1}\sim U(0,1)$.

Hence $T_n \sim U(0,1)$ for every $n$ and your desired probability is $1-\alpha$.

Reference:

An improved Bonferroni procedure for multiple tests of significance by R.J. Simes.

Answer 2

Let $X$ be the count of the number of uniform RVs less than or equal to $\alpha$. We have $$P(X = x) = \binom{n}{x} \alpha^x (1 - \alpha)^{n-x}.$$ Let $$Z = \bigcap_{j=1}^{n} \left \{U_{(j)} > \frac{\alpha j}{n} \right \}$$ be the event in question. Then $$P(Z) = \sum_{x = 0}^{n - 1}P(Z \mid X = x) P(X = x),$$ where I sum to $n - 1$ because if $X = n$ then $U_{(n)} \leq \alpha$ so $Z$ is not possible.

Given that $X = x$, the $n - x$ uniforms that are greater than $\alpha$ clearly satisfy the requirement in $Z$. And also given $X = x$ we have $V_1, \dots, V_x$ i.i.d. $U(0, \alpha)$. If we represent the $n - 1$ thresholds $\alpha/n, 2\alpha/n, \dots, (n-1)\alpha/n$ with the letter $A$, and the $x$ uniforms $V_1, \dots, V_x$ with the letter $B$, we can create a sequence of $A$'s and $B$'s based on the ordering of the thresholds and uniforms. E.g. if $n = 3, x = 1$, and $V_1 > 2\alpha/n$ then the sequence would be AAB. Condition $Z$ is satisfied if the number of observed $B$'s never exceeds the number of observed $A$'s as we read the sequence from left to right (e.g. if the sequence starts with a $B$ then $Z$ is not satisfied because $V_{(1)} = U_{(1)} < \alpha/n$). Since the thresholds are evenly spread through the interval $(0, \alpha)$, and the $V_j$'s are uniform on $(0, \alpha)$, the probability that a particular sequence of $A$'s and $B$'s occurs is the same as the probability that that sequence was drawn without replacement from an urn containing $n - 1$ balls labelled $A$ and $x$ balls labelled $B$. Let $P(n - 1, x)$ be the probability that the number of observed $B$'s never exceeds the number of observed $A$'s.

So far we have $$P(Z) = \sum_{x = 0}^{n - 1}P(n - 1, x) P(X = x).$$

By the variant of Bertrand's Ballot theorem with ties allowed, we have $$P(n - 1, x) = \frac{n - 1 + 1 - x}{n - 1 + 1} = \frac{n - x}{n}.$$

Putting this together we have $$P(Z) = \sum_{x = 0}^{n - 1} \frac{x}{n} \binom{n}{x} \alpha^x (1 - \alpha)^{n-x} = (1 - \alpha) \sum_{x = 0}^{n - 1} \binom{n - 1}{x} \alpha^x (1 - \alpha)^{n-1-x}.$$ The sum covers all the probabilities of a binomial distribution with parameters $n - 1, \alpha$, so it equals $1$, hence $P(Z) = 1-\alpha$.

(Thank you Hart!)