Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X_i \stackrel{\mathcal L}{=} i \times U_i$ where $U_i$ are iid uniform $[0,1]$ time stamps $\sum$. (I don't quite get what time stamps means here, but I guess it means $U_i$ are uniformly distributed on $[0,1]$

The question is, for a certain $i$, would it be possible to calculate this probability:

$$ \Pr \{\cap_{j < i} (X_j < X_i) \} $$

In other words, what's the probability that $X_i$ is greater than any $X_j, j \in [1, i -1]$.

share|cite|improve this question
up vote 3 down vote accepted

Let $M_i = \max \{ X_j: j \le i-1\}$. If $k \le t \le k+1$ with $0 \le k \le i-1$, $P(M_i \le t) = \prod_{j=k+1}^{i-1} \frac{t}{j} = \frac{t^{i-1-k} k!}{(i-1)!}$. Thus $$P(M_i \le X_i) = \sum_{k=0}^{i-1} \frac{1}{i} \int_{k}^{k+1} \frac{t^{i-1-k} k!}{(i-1)!}\, dt = \sum_{k=0}^{i-1} \frac{k!}{i!} \frac{(k+1)^{i-k} - k^{i-k}}{i-k}$$ I don't think there's a closed form for this. The first few values (for $i$ from 1 to 10) are $$ 1,\frac{3}{4},{\frac {23}{36}},{\frac {163}{288}},{\frac {3697}{7200}},{ \frac {5113}{10800}},{\frac {38947}{88200}},{\frac {14070953}{33868800 }},{\frac {359861221}{914457600}},{\frac {1713552101}{4572288000}}$$

share|cite|improve this answer

Since $X_i$ and $X_j$ are independent for $i \not= j$:

$$ \mathbb{P}\left( \cap_{j<i} (X_j <X_i) \right) = \mathbb{E}_{X_i} \left( \prod_{j<i} \mathbb{P}(X_j < X_i \vert X_i ) \right) = \mathbb{E}_{U} \left( \prod_{j=1}^{i-1} \min\left(1, \frac{i}{j} U \right) \right). $$ where $\mathbb{E}_{X_i}$ denote expectation with respect to $X_i$, and $U$ follows $\mathcal{U}([0,1))$. Let $u_k = \frac{k}{i}$ for $0 \le k \le i$ : $$ \begin{eqnarray} \mathbb{E}_{U} \left( \prod_{j=1}^{i-1} \min\left(1, \frac{i}{j} U \right) \right) &=& \sum_{k=0}^{i-1} \mathbb{E}_{U} \left( \left. \prod_{j=1}^{i-1} \min\left(1, \frac{i}{j} U \right) \right\vert u_k \le U < u_{k+1} \right) \mathbb{P}( u_k \le U < u_{k+1}) \\ &=& \sum_{k=0}^{i-1} \mathbb{E}\left( \left. \prod_{j=k}^{i-1} \frac{i}{j} U \right\vert u_k \le U < u_{k+1} \right) \frac{1}{i} \\ &=& \sum_{k=0}^{i-1} \mathbb{E}\left( \left. u^{i-k-1} \frac{k! i^{i-k-1}}{(i-1)!} \right\vert u_k \le U < u_{k+1} \right) \frac{1}{i} \\ &=& \sum_{k=0}^{i-1} \frac{k! i^{i-k-1}}{(i-1)!} \mathbb{E}\left( \left. u^{i-k-1} \right\vert u_k \le U < u_{k+1} \right) \frac{1}{i} \end{eqnarray} $$ The r-th moment of $\mathcal{U}((a,b))$ is $\frac{b^{r+1}-a^{r+1}}{(b-a)(r+1)}$, so $\mathbb{E}( \left. u^r \right\vert u_k \le U < u_{k+1}) = \frac{u_{k+1}^{r+1} - u_k^{r+1}}{(u_{k+1}-u_k)(r+1)}$.

This reproduces Robert's result.

share|cite|improve this answer
What is $\mathbb{E}_{X_i}$? Expectation? – ablmf Sep 21 '11 at 22:25
Also what does $\mathbb{P}(X_j < X_i \vert X_i )$ mean? It looks like conditional probability, but what's the condition? – ablmf Sep 21 '11 at 22:28
Careful, $P(X_j<X_i|X_i)$ is $\min(1,X_i/j)$ and $X_i>j$ with positive probability since $j<i$. – Did Sep 21 '11 at 22:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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