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, i \geq 1,$ be independent uniform (0, 1) random variables, and define $N$ by $$N=\min\{n:X_n < X_{n-1}\}$$. I need to prove that $$P\{N \geq k \mid X_0=x\} = \frac{(1-x)^{k-1}}{(k-1)!}$$. I understand that $N$ is a geometric random variable. I am stuck when finding the quantities like $P(X_i \geq X_{i-1} \mid X_{j} \geq X_{j-1}, \forall j\lt i)$.

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

$\mathrm{P}\{N\ge k\mid X_0=x\}$ is the probability that at least the first $k$ entries are in non-decreasing order when the first entry is $x$. I think there is a simpler approach.

Since the entries are uniformly distributed in $[0,1]$, the probability of two entries being equal is $0$. So we will assume that none are equal.

Given that $x_0=x$, the probability that the next $k-1$ entries are at least $x$ is $(1-x)^{k-1}$. In only one of the $(k-1)!$ permutations of those $k-1$ elements are they in non-decreasing order. Thus, $$ \mathrm{P}\{N\ge k\mid X_0=x\}=\frac{(1-x)^{k-1}}{(k-1)!} $$

share|cite|improve this answer

Here is another approach to the question (although I think that robjohn's answer is the best). Conditionning with respect to $X_1$, we have that $$ \begin{align} P(N \geq k \mid X_0 = x) &= \int_0^1 P(N \geq k \mid X_0=x,X_1=y)\,dy \\ & = \int_x^1P(N \geq k \mid X_1 = y)\,dy\\ & = \int_x^1P(N \geq k-1\mid X_0=y)\,dy \end{align} $$ for all integer $k \geq 1$. The result then follows by induction.

share|cite|improve this answer

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.