2
$\begingroup$

Pick a random number (evenly distributed) between $0$ and $1$. Continue picking random numbers as long as they keep decreasing; stop picking when you obtain a number that is greater than the previous one you picked. What is the expected number of numbers you pick?

  • 1
    @JulianKuelshammer thank you...ne$x$t time I'll give more informative title..2012-11-24

2 Answers 2

2

There're $n!$ ways of arranging $n$ numbers, supposing that there're $n$ picks, then the first $(n-1)$ picks are in descending order, there are $(n-1)$ ways of choosing the first $(n-1)$ numbers and thus the probability of picking just $n$ nimbers is $\cfrac {n-1}{n!}$ and the expected value is $E=\sum^{\infty}_{n=2} n\cdot\cfrac {n-1}{n!}= \sum^{\infty}_{n=2} \cfrac {1}{(n-2)!}=\sum^{\infty}_{n=0} \cfrac {1}{n!}=e=2.718281828459...$

  • 0
    thank you my friend for tried to help,I just post ans. in comment see that :)2012-11-24
2

The following solutions uses indicator random variables.

Fix an $n$, and imagine doing the experiment only $n$ times. For $i\le n$, let $X_j=1$ if $X_1\gt X_2 \gt \cdots >X_j$, and let $X_j=0$ otherwise. Then $\Pr(X_j=1)=\frac{1}{j!}$ and therefore $E(X_j)=\frac{1}{j!}$.

If $Y_n$ is the length of the longest monotone decreasing sequence that starts with the first number chosen the beginning, then $Y_n=X_1 +X_2+\cdots +X_n$. Thus, by the linearity of expectation, $E(Y_n)=E(X_1)+E(X_2)+E(X_3)+\cdots+E(X_n)= 1+\frac{1}{2!}+\frac{1}{3!}+\cdots +\frac{1}{n!}.$ As $n\to \infty$, this approaches $e-1$.

But your random variable counts all the picks up to and including the first pick that breaks the monotonicity. So your random variable has expectation $(e-1)+1=e$.