Probability of choosing the second best candidate in the secretary problem

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite
1












I'm trying to research unexplored properties of the secretary problem, specifically the probability of choosing the k'th best candidate instead of the best one. Could be thought of as trying to calculate the PDF of the result of the optimal policy of skipping $n/e$.



I've come up with the following infinite sum which represents the probability of choosing $k=2$, in a method very similar to the original problem's proof. There is also a slightly longer and more algebra-heavy proof for a general k.



Using a Riemann approximation of an integral doesn't seem to work in this case, due to the $n-i$ expression stuck inside the sum. By running this calculation, I see that it does in fact converge to $e^-2 sim 0.135$, which does in fact match the empirical results. But how do I go about proving it?



$$r=n/e$$
$$lim_nrightarrowinfty fracr-1n(n-1) cdot sum_i=r^n-1fracn-ii-1 approx e^-2$$



EDIT: Maybe the following simplification can help?
$$ = lim_nrightarrowinfty frac1e ( frac1n cdot sum_i=r^n-1fracn-ii-1) approx e^-2 Leftrightarrow lim_nrightarrowinfty frac1n cdot sum_i=r^n-1fracn-ii-1 approx e^-1$$



Screenshot of how the sum is arrived at



P.S. The formula for a general k, if anyone's interested:
$$lim_nrightarrowinfty fracr-1n cdot sum_i=r^n-k+1frac1i-1 cdot prod_j=0^k-2fracn-i-jn-j-1$$
If anyone can help me find what the general k converges to, I will be much obliged. I suspect it converges to $e^-k$.







share|cite|improve this question

























    up vote
    2
    down vote

    favorite
    1












    I'm trying to research unexplored properties of the secretary problem, specifically the probability of choosing the k'th best candidate instead of the best one. Could be thought of as trying to calculate the PDF of the result of the optimal policy of skipping $n/e$.



    I've come up with the following infinite sum which represents the probability of choosing $k=2$, in a method very similar to the original problem's proof. There is also a slightly longer and more algebra-heavy proof for a general k.



    Using a Riemann approximation of an integral doesn't seem to work in this case, due to the $n-i$ expression stuck inside the sum. By running this calculation, I see that it does in fact converge to $e^-2 sim 0.135$, which does in fact match the empirical results. But how do I go about proving it?



    $$r=n/e$$
    $$lim_nrightarrowinfty fracr-1n(n-1) cdot sum_i=r^n-1fracn-ii-1 approx e^-2$$



    EDIT: Maybe the following simplification can help?
    $$ = lim_nrightarrowinfty frac1e ( frac1n cdot sum_i=r^n-1fracn-ii-1) approx e^-2 Leftrightarrow lim_nrightarrowinfty frac1n cdot sum_i=r^n-1fracn-ii-1 approx e^-1$$



    Screenshot of how the sum is arrived at



    P.S. The formula for a general k, if anyone's interested:
    $$lim_nrightarrowinfty fracr-1n cdot sum_i=r^n-k+1frac1i-1 cdot prod_j=0^k-2fracn-i-jn-j-1$$
    If anyone can help me find what the general k converges to, I will be much obliged. I suspect it converges to $e^-k$.







    share|cite|improve this question























      up vote
      2
      down vote

      favorite
      1









      up vote
      2
      down vote

      favorite
      1






      1





      I'm trying to research unexplored properties of the secretary problem, specifically the probability of choosing the k'th best candidate instead of the best one. Could be thought of as trying to calculate the PDF of the result of the optimal policy of skipping $n/e$.



      I've come up with the following infinite sum which represents the probability of choosing $k=2$, in a method very similar to the original problem's proof. There is also a slightly longer and more algebra-heavy proof for a general k.



      Using a Riemann approximation of an integral doesn't seem to work in this case, due to the $n-i$ expression stuck inside the sum. By running this calculation, I see that it does in fact converge to $e^-2 sim 0.135$, which does in fact match the empirical results. But how do I go about proving it?



      $$r=n/e$$
      $$lim_nrightarrowinfty fracr-1n(n-1) cdot sum_i=r^n-1fracn-ii-1 approx e^-2$$



      EDIT: Maybe the following simplification can help?
      $$ = lim_nrightarrowinfty frac1e ( frac1n cdot sum_i=r^n-1fracn-ii-1) approx e^-2 Leftrightarrow lim_nrightarrowinfty frac1n cdot sum_i=r^n-1fracn-ii-1 approx e^-1$$



      Screenshot of how the sum is arrived at



      P.S. The formula for a general k, if anyone's interested:
      $$lim_nrightarrowinfty fracr-1n cdot sum_i=r^n-k+1frac1i-1 cdot prod_j=0^k-2fracn-i-jn-j-1$$
      If anyone can help me find what the general k converges to, I will be much obliged. I suspect it converges to $e^-k$.







      share|cite|improve this question













      I'm trying to research unexplored properties of the secretary problem, specifically the probability of choosing the k'th best candidate instead of the best one. Could be thought of as trying to calculate the PDF of the result of the optimal policy of skipping $n/e$.



      I've come up with the following infinite sum which represents the probability of choosing $k=2$, in a method very similar to the original problem's proof. There is also a slightly longer and more algebra-heavy proof for a general k.



      Using a Riemann approximation of an integral doesn't seem to work in this case, due to the $n-i$ expression stuck inside the sum. By running this calculation, I see that it does in fact converge to $e^-2 sim 0.135$, which does in fact match the empirical results. But how do I go about proving it?



      $$r=n/e$$
      $$lim_nrightarrowinfty fracr-1n(n-1) cdot sum_i=r^n-1fracn-ii-1 approx e^-2$$



      EDIT: Maybe the following simplification can help?
      $$ = lim_nrightarrowinfty frac1e ( frac1n cdot sum_i=r^n-1fracn-ii-1) approx e^-2 Leftrightarrow lim_nrightarrowinfty frac1n cdot sum_i=r^n-1fracn-ii-1 approx e^-1$$



      Screenshot of how the sum is arrived at



      P.S. The formula for a general k, if anyone's interested:
      $$lim_nrightarrowinfty fracr-1n cdot sum_i=r^n-k+1frac1i-1 cdot prod_j=0^k-2fracn-i-jn-j-1$$
      If anyone can help me find what the general k converges to, I will be much obliged. I suspect it converges to $e^-k$.









      share|cite|improve this question












      share|cite|improve this question




      share|cite|improve this question








      edited Aug 1 at 15:56
























      asked Jul 28 at 15:41









      Tolstoyevsky

      134




      134




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          0
          down vote



          accepted










          I got to prove the case $k=2$, here it is:
          $$lim_ntoinfty fracr-1n(n-1)sum_i=r^n-1fracn-ii-1 = lim_ntoinfty fracr-1n(n-1)left(fracn-rr-1 + fracn-(r+1)r+fracn-(r+2)r+1+dotsright) = lim_ntoinfty fracr-1nleft(left(frac1r-1 - frac1n-1right) + left(frac1r - frac1n-1right) + left(frac1r+1 - frac1n-1right) + dotsright) = lim_ntoinfty fracr-1nleft(sum_k=r-1^n-2 frac1k - fracn-rn-1right) approx lim_ntoinfty fracr-1nleft(1 - fracn-rn-1right) = lim_ntoinfty frac(r-1)^2n(n-1) = frac1e^2.$$
          In the approximation step I used the following result:
          $$sum_k=a^b frac1k approx logleft(frac2b+12a-1right),$$
          which I found here:
          Summing Finitely Many Terms of Harmonic Series: $sum_k=a^b frac1k$






          share|cite|improve this answer





















          • Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
            – Tolstoyevsky
            Jul 30 at 10:21










          • Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
            – Tolstoyevsky
            Jul 30 at 10:25










          • You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
            – M4g1ch
            Jul 31 at 16:34










          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );








           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865350%2fprobability-of-choosing-the-second-best-candidate-in-the-secretary-problem%23new-answer', 'question_page');

          );

          Post as a guest






























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          0
          down vote



          accepted










          I got to prove the case $k=2$, here it is:
          $$lim_ntoinfty fracr-1n(n-1)sum_i=r^n-1fracn-ii-1 = lim_ntoinfty fracr-1n(n-1)left(fracn-rr-1 + fracn-(r+1)r+fracn-(r+2)r+1+dotsright) = lim_ntoinfty fracr-1nleft(left(frac1r-1 - frac1n-1right) + left(frac1r - frac1n-1right) + left(frac1r+1 - frac1n-1right) + dotsright) = lim_ntoinfty fracr-1nleft(sum_k=r-1^n-2 frac1k - fracn-rn-1right) approx lim_ntoinfty fracr-1nleft(1 - fracn-rn-1right) = lim_ntoinfty frac(r-1)^2n(n-1) = frac1e^2.$$
          In the approximation step I used the following result:
          $$sum_k=a^b frac1k approx logleft(frac2b+12a-1right),$$
          which I found here:
          Summing Finitely Many Terms of Harmonic Series: $sum_k=a^b frac1k$






          share|cite|improve this answer





















          • Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
            – Tolstoyevsky
            Jul 30 at 10:21










          • Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
            – Tolstoyevsky
            Jul 30 at 10:25










          • You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
            – M4g1ch
            Jul 31 at 16:34














          up vote
          0
          down vote



          accepted










          I got to prove the case $k=2$, here it is:
          $$lim_ntoinfty fracr-1n(n-1)sum_i=r^n-1fracn-ii-1 = lim_ntoinfty fracr-1n(n-1)left(fracn-rr-1 + fracn-(r+1)r+fracn-(r+2)r+1+dotsright) = lim_ntoinfty fracr-1nleft(left(frac1r-1 - frac1n-1right) + left(frac1r - frac1n-1right) + left(frac1r+1 - frac1n-1right) + dotsright) = lim_ntoinfty fracr-1nleft(sum_k=r-1^n-2 frac1k - fracn-rn-1right) approx lim_ntoinfty fracr-1nleft(1 - fracn-rn-1right) = lim_ntoinfty frac(r-1)^2n(n-1) = frac1e^2.$$
          In the approximation step I used the following result:
          $$sum_k=a^b frac1k approx logleft(frac2b+12a-1right),$$
          which I found here:
          Summing Finitely Many Terms of Harmonic Series: $sum_k=a^b frac1k$






          share|cite|improve this answer





















          • Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
            – Tolstoyevsky
            Jul 30 at 10:21










          • Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
            – Tolstoyevsky
            Jul 30 at 10:25










          • You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
            – M4g1ch
            Jul 31 at 16:34












          up vote
          0
          down vote



          accepted







          up vote
          0
          down vote



          accepted






          I got to prove the case $k=2$, here it is:
          $$lim_ntoinfty fracr-1n(n-1)sum_i=r^n-1fracn-ii-1 = lim_ntoinfty fracr-1n(n-1)left(fracn-rr-1 + fracn-(r+1)r+fracn-(r+2)r+1+dotsright) = lim_ntoinfty fracr-1nleft(left(frac1r-1 - frac1n-1right) + left(frac1r - frac1n-1right) + left(frac1r+1 - frac1n-1right) + dotsright) = lim_ntoinfty fracr-1nleft(sum_k=r-1^n-2 frac1k - fracn-rn-1right) approx lim_ntoinfty fracr-1nleft(1 - fracn-rn-1right) = lim_ntoinfty frac(r-1)^2n(n-1) = frac1e^2.$$
          In the approximation step I used the following result:
          $$sum_k=a^b frac1k approx logleft(frac2b+12a-1right),$$
          which I found here:
          Summing Finitely Many Terms of Harmonic Series: $sum_k=a^b frac1k$






          share|cite|improve this answer













          I got to prove the case $k=2$, here it is:
          $$lim_ntoinfty fracr-1n(n-1)sum_i=r^n-1fracn-ii-1 = lim_ntoinfty fracr-1n(n-1)left(fracn-rr-1 + fracn-(r+1)r+fracn-(r+2)r+1+dotsright) = lim_ntoinfty fracr-1nleft(left(frac1r-1 - frac1n-1right) + left(frac1r - frac1n-1right) + left(frac1r+1 - frac1n-1right) + dotsright) = lim_ntoinfty fracr-1nleft(sum_k=r-1^n-2 frac1k - fracn-rn-1right) approx lim_ntoinfty fracr-1nleft(1 - fracn-rn-1right) = lim_ntoinfty frac(r-1)^2n(n-1) = frac1e^2.$$
          In the approximation step I used the following result:
          $$sum_k=a^b frac1k approx logleft(frac2b+12a-1right),$$
          which I found here:
          Summing Finitely Many Terms of Harmonic Series: $sum_k=a^b frac1k$







          share|cite|improve this answer













          share|cite|improve this answer



          share|cite|improve this answer











          answered Jul 29 at 15:08









          M4g1ch

          19617




          19617











          • Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
            – Tolstoyevsky
            Jul 30 at 10:21










          • Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
            – Tolstoyevsky
            Jul 30 at 10:25










          • You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
            – M4g1ch
            Jul 31 at 16:34
















          • Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
            – Tolstoyevsky
            Jul 30 at 10:21










          • Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
            – Tolstoyevsky
            Jul 30 at 10:25










          • You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
            – M4g1ch
            Jul 31 at 16:34















          Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
          – Tolstoyevsky
          Jul 30 at 10:21




          Thanks, clever simplification of the sum there. But isn't it a problem that you use a formula for summing finitely many terms of the harmonic series, while $nrightarrow infty$?
          – Tolstoyevsky
          Jul 30 at 10:21












          Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
          – Tolstoyevsky
          Jul 30 at 10:25




          Or is it not a problem due to $a$ being a function of $b$ rather than being a constant?
          – Tolstoyevsky
          Jul 30 at 10:25












          You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
          – M4g1ch
          Jul 31 at 16:34




          You are right, I was kind of stuck in that step and I found that link which gave me some light, but now that you say it... I'm going to think about it and see if I come up with something else. If you figure it out (or anyone else), please tell me
          – M4g1ch
          Jul 31 at 16:34












           

          draft saved


          draft discarded


























           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865350%2fprobability-of-choosing-the-second-best-candidate-in-the-secretary-problem%23new-answer', 'question_page');

          );

          Post as a guest













































































          Comments

          Popular posts from this blog

          What is the equation of a 3D cone with generalised tilt?

          Relationship between determinant of matrix and determinant of adjoint?

          Color the edges and diagonals of a regular polygon