login
a(r) is the maximum number of secretaries for which the first r should be rejected, if selecting the one with the highest or lowest ranking are both considered a success.
1

%I #32 Feb 24 2017 02:52:06

%S 3,8,13,18,23,27,32,37,42,47,52,57,62,67,72,77,82,86,91,96,101,106,

%T 111,116,121,126,131,136,141,146,150,155,160,165,170,175,180,185,190,

%U 195,200,205,210,214,219,224,229,234,239,244,249,254,259,264,269,273,278,283

%N a(r) is the maximum number of secretaries for which the first r should be rejected, if selecting the one with the highest or lowest ranking are both considered a success.

%C According to Bayon et al, the probability P(n,r) = 2*r*((r/n-1)+sum_{i=r..n-1} 1/i)/n of success in a generalized Secretary problem for a given number n of applicants has a maximum at some value of r, 1<=r<n. These best values are r=1 for n<=8, r=2 for n<=13, r=3 for n<=18 and so on.

%C The Beatty sequence of A106533, b(n) = floor(n*A106533), is a good approximation to r for large n. So the indices n-1 of the steps where b(n) = b(n+1)-1 are an approximation to this sequence.

%C We added numbers 27, 86 and 91 that are apparently missing in the preprint. _R. J. Mathar_, Feb 22 2017

%H Vincenzo Librandi, <a href="/A282025/b282025.txt">Table of n, a(n) for n = 0..202</a>

%H L. Bayon, J. Grau, A. M. Oller-Marcen, M. Ruiz, P. M. Suarez, <a href="https://arxiv.org/abs/1603.03928">A variant of the Secretary Problem: the Best or the Worst</a>, arXiv preprint arXiv:1603.03928 [math.PR], 2016.

%p P := proc(n,

%p option remember;

%p local i;

%p 2*r/n*((r/n-1)+add(1/i,i=r..n-1)) ;

%p end proc:

%p Pmax := proc(n)

%p option remember;

%p local r;

%p for r from 1 to n-1 do

%p if P(n,r+1) < P(n,r) then

%p return r ;

%p end if;

%p end do:

%p end proc:

%p A282025 := proc(r)

%p local n ;

%p if r = 0 then

%p return 3;

%p end if;

%p for n from r+1 do

%p if Pmax(n+1) = r+1 then

%p return n;

%p end if;

%p end do:

%p return -1 ;

%p end proc:

%p seq(A282025(r),r=0..80) ; # _R. J. Mathar_, Feb 22 2017

%t P[n_, r_] := 2 r ((r/n - 1) + Sum[ 1/i, {i, r, n - 1}])/n; Function[s, {3}~Join~Map[-1 + Position[s, #][[1, 1]] &, Range@ Max@ s]]@ Map[Length@ TakeWhile[#, # == 0 &] &, Table[If[P[n, k + 1] < P[n, k], k, 0], {n, 300}, {k, n - 1}]] (* _Michael De Vlieger_, Feb 22 2017, after Maple *)

%Y Cf. A106533, A054404.

%K nonn

%O 0,1

%A _N. J. A. Sloane_, Feb 11 2017