Mixing
Probability of choosing the second best candidate in the secretary problem
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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$.
calculus probability sequences-and-series limits game-theory
asked Jul 28 at 15:41
Tolstoyevsky
134
add a comment |Â
up vote
2
down vote
favorite
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$.
calculus probability sequences-and-series limits game-theory
asked Jul 28 at 15:41
Tolstoyevsky
134
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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$.
calculus probability sequences-and-series limits game-theory
asked Jul 28 at 15:41
Tolstoyevsky
134
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$.
calculus probability sequences-and-series limits game-theory
asked Jul 28 at 15:41
Tolstoyevsky
134
edited Aug 1 at 15:56
asked Jul 28 at 15:41
Tolstoyevsky
134
asked Jul 28 at 15:41
Tolstoyevsky
134
asked Jul 28 at 15:41
Tolstoyevsky
134
134
add a comment |Â
add a comment |Â
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$
answered Jul 29 at 15:08
M4g1ch
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
add a comment |Â
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$
answered Jul 29 at 15:08
M4g1ch
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
add a comment |Â
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$
answered Jul 29 at 15:08
M4g1ch
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
add a comment |Â
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$
answered Jul 29 at 15:08
M4g1ch
19617
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$
answered Jul 29 at 15:08
M4g1ch
19617
answered Jul 29 at 15:08
M4g1ch
19617
answered Jul 29 at 15:08
M4g1ch
19617
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
add a comment |Â
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
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password