1

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.

smci
  • 1,456
  • 1
  • 13
  • 20
Vickyfish
  • 11
  • 1
  • from what distribution? – user158565 Jul 28 '19 at 19:33
  • 1
    The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$? – Semoi Jul 28 '19 at 19:57
  • Possible duplicate of [Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform \[0,1\] distribution?](https://stats.stackexchange.com/questions/350923/brain-teaser-what-is-the-expected-length-of-an-iid-sequence-that-is-monotonical) – Ben Jul 29 '19 at 02:37

1 Answers1

5

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$

Michael Hardy
  • 7,094
  • 1
  • 20
  • 38
gunes
  • 49,700
  • 3
  • 39
  • 75
  • The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence. – Glen_b Jul 28 '19 at 23:15
  • Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back. – gunes Jul 29 '19 at 03:52