Help with one interview question --expected length of numbers drawn [closed]

Question

Randomly draw numbers from 1 to n without replacement and $x(n)$ is the nth number you draw. Continue drawing numbers if $x(n) > x(n-1)$ and stop if $x(n) < x(n-1)$.

Calculate the expected length of numbers you draw.

Answer 1

I'm assuming that we're uniformly drawing numbers (without replacement), and stop when we explicitly see that the currently drawn number is smaller than the previously drawn number. That means, if we draw $N$ first, we still draw another number and see if it is smaller than $N$, which is going to happen for sure. With this setup, it's certain that we'll draw numbers at least $2$ times. This way, the problem has a beautiful answer, however the OP should still clarify the question to help other readers who can benefit.

Let $X$ be the number of draws in this experiment. Since $X$ is nonnegative and integer we can express the expected value as $$E[X]=\sum_{k=0}^{N-1} P(X>k)$$ Here, $P(X>k)=\frac{1}{k!}$ because for number of draws to be bigger than $k$, the first $k$ draws must be sorted, which happens with $\frac{1}{k!}$ probability no matter what $N$ is. Expanding the sum yields: $$E[X]=1+1+\frac{1}{2!}+\frac{1}{3!}+\cdots+\frac{1}{(N-1)!}$$

Notice that this converges to $e$ as $N\rightarrow\infty$