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?
Picking random numbers as long as they keep decreasing. 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
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...$
-
0thank you my friend for tried to help,I just post ans. in comment see that :) – 2012-11-24
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$.