# Distribution for first time when the value is less than the previous one

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

-
From your expression, $N\mid X_0=x$ does not have a geometric distribution. Compare: en.wikipedia.org/wiki/Geometric_distribution – 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$.

-
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