Given a random permutation of $1$ to $N$, let the sequence be $a_1,a_2,\cdots,a_N$.

Erase the first $k$ items, and find out the item (let it be $a_I$) which is first item greater than the fist $k$ items.

I already know that $$P(a_I = N)=\frac{k}{n}\sum_{i=k+1}^{N}\frac{1}{i-1}.$$

But what is the probability of $a_I=N-1$?

Furthermore, what is the expected value of $a_I$?

  • 1
    $\begingroup$ I'm assuming this is related somehow to the secretary problem/sultan's dowry problem/etc.? $\endgroup$ – Brian Tung Aug 10 '18 at 17:21
  • 2
    $\begingroup$ I think you should use $a_I$ where $I$ is a random index. Of course, you would also need to define what happens if number $N$ lies in the first $k$ items, since then there would be no "first item greater than [all of?] the first $k$ items." $\endgroup$ – Michael Aug 10 '18 at 17:35
  • $\begingroup$ Also, your expression for $P(a_i=N)$ isn't a probability; e.g., if $k=\frac n2$ and $n$ is sufficiently large, you're summing several terms near $\frac12$, so the result is greater than $1$. $\endgroup$ – joriki Aug 10 '18 at 19:02
  • $\begingroup$ It seems you've edited the question to address one of three issues but not the other two? $\endgroup$ – joriki Aug 11 '18 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.