Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|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
1  
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
add comment

Your Answer

 
discard

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.