Ytukyg

We have a hall with $N$ secretaries. We choose randomly one secretary at a time and interview them. After the interview either we hire the secretary (and all others go home) or move to the next one (we can't go back and hire them later).

The interviewer wants to hire either the best or second best secretary with the highest probability

My approach:

I know we should use this strategy: after we interview the first $aN$ candidates (which we don't hire), then we choose the first one that's better than the previous $aN$ candidates. I am just stuck knowing what is the value of $a$. What is the probability of this value? and how we get to it?

I have seen the "Secretary Problem" where we want to choose the best one, the difference here is that we are satisfied with the best or second best one equally

I'd started preparing a response, but the OP seems to have lost interest. In any case for the benefit of future Readers here are my initial thoughts. If there are Comments I'll be glad to fill in more details.

The variant of the Secretary Problem considered here appears in the literature as early as 1966 with publications by:

• Gusein-Zade, S. M. "The problem of choice and the optimal stopping rule for a sequence of random trials," Teor. Veroyatnost. i Primenen., 1966, [Vol. 11,Issue 3 (1966), pp. 534-537] (English version: Theory of Probability and its Applications, 1966, 11:3, 472–476)


• Gilbert, John P. and Mosteller, Frederick "Recognizing the Maximum of a Sequence," Journal of the American Statistical Association Vol. 61, No. 313 (Mar., 1966), pp. 35-73
  

Although both of these links lead to papers behind paywalls, as far as I can tell, a good summary of the results by Gusein-Zade can be gleaned from this open access technical report by Frank and Samuels (1979) . In particular as the number of secretaries $N to infty$, the asymptotic chance of success for the classic problem $1/e approx 0.3679$ rises to roughly $0.5736$ when choosing either the best or second-best candidate counts as a success.

The general rule that maximizes the chance of getting one of the $b$-best secretaries is shown by Gusein-Zade to have the form of $b+1$ consecutive intervals subdividing the interviews $1,ldots,N$.

In the present case $b=2$ and there are three phases of the rule. In the first phase the interviews $1 le i le Ncdot m_1(N)$ are conducted and the relative rankings observed without stopping, In the second phase the interviews $Ncdot m_1(N) lt i le Ncdot m_2(N)$ are conducted and only stop if one interview results in a relative "top" ranking (better than all previous interviews) happens, in which event the interviews are ended with a job offer being made. If the second phase finishes without a job offer, the third and final phase of interviews $Ncdot m_2(N) lt i le N$ applies the rule that a job offer is made if and only if an interview results in a relative ranking of "top" or "next to top" (better than all but at most one of the previous interviews).

It is useful to express the boundaries between phases as coefficients $m_1(N),m_2(N)$ because these multipliers have fairly simple limits as $Nto infty$, namely as Gusein-Zade showed:

$$ lim_{Nto infty} m_2(N) = frac{2}{3} $$

and:

$$ lim_{Nto infty} m_1(N) = varphi $$

where $varphi$ is the unique solution in $(0,1)$ of:

$$ varphi - ln varphi = 1 - ln(2/3) $$

Now $varphi approx 0.3470$, and the exact limiting probability of success for large $N$ is $varphi (2-varphi)$, whose approximate value $0.5736$ was mentioned before.