TITLE: A conditional probability involving order statistic
QUESTION [1 upvotes]: Here is the original question:

Let $X_1,X_2,\cdots$ be i.i.d. random variables uniform on $[0,1]$. Let $N$ be the smallest integer such that $X_N$ is smaller than exactly one of its predecessors $X_1,X_2,\cdots,X_{N-1}$. Find the cumulative distribution function of $N$.

I saw that the key trick is to realize $\mathbb{P}\left\{ N = n \mid N > n-1\right\} = \frac{1}{n}$. But how to rigorously prove it?
I attempted to write that
$$\mathbb{P}\left\{N = n\mid N > n-1\right\} = \mathbb{P}\left\{X_N=X_{(N-1)}\mid N>n-1 \right\}$$
But I don't know how to proceed. I know that all orderings of $X_1,\cdots,X_N$ are equally probable, but I don't know how that would be helpful. Intuitively, I am thinking that once we fix $X_1,\cdots,X_{n-1}$, then there are $n$ possible "slots" that we can "insert" $X_N$, so that gives us $\frac{1}{N}$.

REPLY [0 votes]: Let $X^{(i)}$ be the $i$-th order statistic from $n$ draws of the uniform distribution. (To be clear, $X^{(1)}$ is the smallest draw while $X^{(n)}$ is the largest. I chose slightly different notation than the linked Wikipedia article to avoid confusion with the notation you've chosen.)
Conditioning on $\{N>n\}$, $N=n+1$ whenever $X_{n+1}$ is larger than all but the largest of $n$ draws from the uniform distribution. That is, we must have that $$ \left\{ X^{(n-1)} \le X_{n+1} < X^{(n)} \right\}.$$
In other words,
$$ \Pr(N=n+1 \vert N>n) = \Pr \left( X^{(n-1)} \le X_{n+1} < X^{(n)} \right).$$
Using the joint density of $\left( X^{(n-1)} ,  X^{(n)} \right)$, we have that
\begin{align*}
\Pr \left( X^{(n-1)} \le X_{n+1} < X^{(n)} \right) &= n(n-1) \int_{0}^1\int_{0}^v u^{n-2}(v-u)\,\mathrm du\,\mathrm dv \\
&= \int_0^1 v^n \, \mathrm dv \\
&= \frac{1}{n+1}.
\end{align*}
Hence, $$ \Pr(N=n+1 \vert N>n) = \frac{1}{n+1}. $$
{"set_name": "stack_exchange", "score": 1, "question_id": 2872398}