# How to calculate this probability?

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]$.

-

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}}$$

-

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.

-
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