# Given a random permutation of 1 to N, what is probability to get $N-1$ with a certain strategy?

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$?

• I'm assuming this is related somehow to the secretary problem/sultan's dowry problem/etc.? – Brian Tung Aug 10 '18 at 17:21
• 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." – Michael Aug 10 '18 at 17:35
• 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$. – joriki Aug 10 '18 at 19:02
• It seems you've edited the question to address one of three issues but not the other two? – joriki Aug 11 '18 at 6:55