Stopped sequence with Uniform distribution

Question

let $U_1,U_2,...$ be independent uniform $U(0,1)$ random variables, and let $N$ be the first $n\ge2$ such that $U_n>U_{n-1}$

I'm trying to find $P(U_1\le{u} \text{ and }N=n)$ for $0\le u\le 1$ and $n\ge2$

I'm not sure what topic covers this problem (order statistics?) so I'm unable to work on it with the little information I have.

Answer 1

This is a neat problem, with a neat solution. The sequence stops at $N$ terms as soon as the $n^{\text{th}}$ value is larger than the preceding $(n-1)^{\text{th}}$ term. The number of terms $N=n$ is thus also a random variable with pmf:

• $P(N=2) \; = \; P(U_2>U_1) = \frac12$

• $P(N=3) \; = \; P(U_2 < U_1) \; \centerdot \; P(U_3 > U_2 \; \mid \; U_2 < U_1) = \frac12 \centerdot \frac23$

• $P(N=4) \; = \; P(U_2 < U_1) \; \centerdot \; P(U_3 < U_2 \; \mid \; U_2 < U_1) \; \centerdot \; P(U_4 > U_3 \; \mid \; U_3 < U_2 < U_1) \quad \quad \quad \quad \quad = \frac12 \centerdot \frac13 \centerdot \frac34$

• $\dots$ and by induction, the general solution for the pmf of $N$ is:

$$P(N=n) \; = \; \frac{n-1}{n!} \quad \quad \text{ for } n \ge 2$$

To derive the probabilities above intuitively, consider for instance:

$$P(U_4 > U_3 \; \mid \; U_3 < U_2 < U_1)$$

Since the $U_i$ are iid and Uniform, the condition ${U_3 < U_2 < U_1}$ breaks the unit line into 4 equally likely segments:

and the probability that $U_4$ will fall into the first segment is thus $\frac14$ (or $\frac34$ that it will land in any of the other 3 segments.

Here is a plot of the pmf $P(N=n)$:

The cdf $P(N \le n)$, for integer valued $n$ is: $\quad 1 - \frac{1}{n!}$

Answer 2

So that's the probability that $u\ge U_1\ge U_2\ge\cdots \ge U_{N-1}<U_N$. That will be $P_{N-1}(u)-P_{N}(u)$ where $P_N(u)$ is the probability that $u\ge U_1\ge U_2\ge\cdots\ge U_N$. There's surely a simple relation between $P_N(u)$ and the probability that all of $U_1,\ldots,U_N$ are $\le u$?