Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

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 | X_0=x\} = \frac{(1-x)^{k-1}}{(k-1)!}$$. I am stuck when finding the quantities like $P(X_i \geq X_{i-1} | X_{j} \geq X_{j-1}, \forall j\lt i)$. I have also posted this in math exchange, but not convinced with the answer posted there.

Another question is how to calculate $E[N]$ using conditioning on $X_1$.

share|improve this question
From your expression, $N\mid X_0=x$ does not have a geometric distribution. Compare: – Zen Mar 6 '13 at 4:14
Cross-posting on multiple Stack Exchange sites is not recommended. (It appears that you also cross-posted several questions on MathOverflow and math.SE.) I will close this question as a duplicate then. For future reference, you can ask math.SE moderators to migrate your questions for you. – chl Mar 6 '13 at 10:01
I got some "wrong" answers in math exchange. Thats why I posted here. – aaaaaa Mar 6 '13 at 10:09
@Prasenjit That's not the way to proceed. You should first leave comment on the site where you posted your question (ask for further clarification, or point toward possible misinterpretation or error in current replies), and if you think stats.SE would be a better fit ask a moderator to coordinate migration for you. I've informed math.SE moderators of the situation; let's wait for their feedback. – chl Mar 6 '13 at 10:14

You know that $X_0=x_0$ with probability 1, for $0<x_0<1$, and you have a sequence $\{X_i\}_{i\geq 1}$ of independent $\mathrm{U}[0,1]$ random variables. Let $N$ be the first time the sequence decreases, which means $$ N=\min\,\{n\geq 1:X_{n-1}>X_n\} \, . $$

The key point is that $N\geq k$ if and only if $X_{k-1}\geq X_{k-2}\geq \dots \geq X_1\geq X_0$. Convince yourself checking both implications.

The joint density of $X_1,\dots,X_{k-1}$ is just $$ f_{X_1,\dots,X_{k-1}}(x_1,\dots,x_{k-1}) = \prod_{i=1}^{k-1} f_{X_i}(x_i) = \prod_{i=1}^{k-1} I_{[0,1]}(x_i) \, . $$

Hence, $$ P(N\geq k\mid X_0=x_0)=P(X_{k-1}\geq X_{k-2}\geq \dots \geq X_1\geq x_0) $$ $$ = \int_{x_0}^1 \int_{x_1}^1 \dots \int_{x_{k-2}}^1 f_{X_1,\dots,X_{k-1}}(x_1,\dots,x_{k-1}) \, dx_{k-1} \dots dx_2\,dx_1 $$ $$ = \int_{x_0}^1 \int_{x_1}^1 \dots \int_{x_{k-2}}^1 dx_{k-1} \dots dx_2\,dx_1 = \frac{(1-x_0)^{k-1}}{(k-1)!} \, . $$

(Note that, contradicting the original title of the question, $N\mid X_0=x_0$ is not a geometric random variable.)

Since $N$ is a nonnegative random variable, using this result, we have $$ \mathrm{E}[N\mid X_0=x_0] = \sum_{k=1}^\infty P(N\geq k\mid X_0=x_0) $$ $$ = \sum_{k=1}^\infty \frac{(1-x_0)^{k-1}}{(k-1)!} = \sum_{i=0}^\infty \frac{(1-x_0)^i}{i!} =e^{1-x_0} \, . $$

It follows that $\mathrm{E}[N\mid X_0] = e^{1-X_0}$ almost surely. If $X_0$ has density $f_{X_0}$, we can use the tower property to compute $$ \mathrm{E}[N] = \mathrm{E}[\mathrm{E}[N\mid X_0]] = \int_0^1 e^{1-x_0} f_{X_0}(x_0)\,dx_0 \, . $$

For example, if $X_0\sim\mathrm{U}[0,1]$, then $\mathrm{E}[N] = e-1$.

share|improve this answer
Thanks for the answer. How to calculate $E[N]$ without using probability distribution for $N$ and using conditioning on $x_1$ – aaaaaa Mar 6 '13 at 10:07
Why are you conditioning on $X_0$ ? $X_0 = x$ with probability 1. I was asking for $X_1$ – aaaaaa Mar 6 '13 at 13:53
I can see from the answer that $f'(x)=-f(x)$ if we assume that $f(x)=E[N|X_0=x]$. So, I want to express $f(x)$ i.e. $E[N | X_0=x]$ using conditional expectation with respect to $X_1$ and then differentiate both sides to get $f'(x)=-f(x)$ – aaaaaa Mar 6 '13 at 14:29
Sorry for my poor english. I did not mean like that. – aaaaaa Mar 6 '13 at 16:55
OK, no problem. – Zen Mar 6 '13 at 17:45

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.