Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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: en.wikipedia.org/wiki/Geometric_distribution –  Zen Mar 6 '13 at 4:14
1  
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
add comment

1 Answer

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:X_n<X_{n-1}\} \, . $$

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 property, 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} \, . $$

Therefore, we have constructed a stochastic method that, in principle, allows us to compute Euler's number $e$ using simulations of uniform random variables, and these two things -- uniforms and $e$ -- were not obviously related from the start.

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
    
Added. Don't forget to check the answer as such. This is important for future visitors of SE. –  Zen Mar 6 '13 at 12:10
    
Also: ask the moderators at Math.SE to migrate the question. –  Zen Mar 6 '13 at 12:18
    
One more: the title is misleading: there is no geometric random variable here. –  Zen Mar 6 '13 at 13:28
2  
By the way, I don't like the way you ask things: "Why are you doing this when I'm asking that?". Be more polite. –  Zen Mar 6 '13 at 15:00
show 5 more comments

Your Answer

 
discard

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.