Re: [math-fun] secretary problem
Brent Meeker: The version of this problem that I've heard is that there are N pieces of paper, each with a positive integer written on its face. They are lying face down on the table. You chose and discard them one at a time until you decide to keep the most recently one chosen. Your objective is to end up with the biggest number possible. Note that the range of numbers is not specified. WDS: Asimov tried to formulate it where the numbers are chosen from some arbitrary distribution over the reals he called "F" and goal was to maximize expected value. Meeker goal as hereby interpreted by me, is to minimize expected rank (counting from the greatest, with rank=1, down, with rank=2,3,...,N). The Asimov formulation sucks in the sense that for arbitrary F there may not exist any expectation at all. E.g. Cauchy distribution has no expectation value. So for now let me just consider the rank formulation. If you've seen n numbers so far, 0<=n<N, the only question facing you is "should I stop now (getting as my reward, the rank of the last number seen, among the full set of N numbers)?" The answer is: Stop if the expected rank of the present number, is less than the expected rank you will get by continuing play. Let E(m) = expected rank if stop after >=m numbers revealed, using optimal play from m onward. Let E(m,k) = expected rank if stop after revealing exactly m numbers, and the last one is ranked k among those m, 1<=k<=m. E(N) = (1+N)/2. E(m,k) = Sum[ r * Binomial[r-1, k-1] * Binomial[N-r, m-k] / Binomial[N, m-1] , {r, k, N+k-m} ] in the notation of mathics.net . Except mathics.net crashed when I asked it to evaluate this sum. I presume E(m,k) = 1 + N*k/(m-1) at least approximately. Presumably best play is to stop when m=N (since you have to) or stop if, earlier, E(m,k)<E(m+1). Presumably when 0<=m<N E(m) obeys the recurrence E(m) = (1/m) * Sum[ min( E(m+1), E(m,k) ), {k, 1, m} ]
A proper formulation of this problem must include the cost of picking up another piece of paper. Otherwise, since there are only finitely many pieces of paper, if there's no cost, just pick up all of them. -- Gene
________________________________ From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Sent: Wednesday, June 18, 2014 4:44 PM Subject: Re: [math-fun] secretary problem
Brent Meeker: The version of this problem that I've heard is that there are N pieces of paper, each with a positive integer written on its face. They are lying face down on the table. You chose and discard them one at a time until you decide to keep the most recently one chosen. Your objective is to end up with the biggest number possible. Note that the range of numbers is not specified.
WDS: Asimov tried to formulate it where the numbers are chosen from some arbitrary distribution over the reals he called "F" and goal was to maximize expected value. Meeker goal as hereby interpreted by me, is to minimize expected rank (counting from the greatest, with rank=1, down, with rank=2,3,...,N).
The Asimov formulation sucks in the sense that for arbitrary F there may not exist any expectation at all. E.g. Cauchy distribution has no expectation value. So for now let me just consider the rank formulation.
If you've seen n numbers so far, 0<=n<N, the only question facing you is "should I stop now (getting as my reward, the rank of the last number seen, among the full set of N numbers)?" The answer is: Stop if the expected rank of the present number, is less than the expected rank you will get by continuing play.
Let E(m) = expected rank if stop after >=m numbers revealed, using optimal play from m onward.
Let E(m,k) = expected rank if stop after revealing exactly m numbers, and the last one is ranked k among those m, 1<=k<=m.
E(N) = (1+N)/2.
E(m,k) = Sum[ r * Binomial[r-1, k-1] * Binomial[N-r, m-k] / Binomial[N, m-1] , {r, k, N+k-m} ] in the notation of mathics.net . Except mathics.net crashed when I asked it to evaluate this sum. I presume E(m,k) = 1 + N*k/(m-1) at least approximately.
Presumably best play is to stop when m=N (since you have to) or stop if, earlier, E(m,k)<E(m+1).
Presumably when 0<=m<N E(m) obeys the recurrence
E(m) = (1/m) * Sum[ min( E(m+1), E(m,k) ), {k, 1, m} ]
Just to be clear, I didn't formulate any problem, just stated some facts about distributions. --Dan
participants (3)
-
Dan Asimov -
Eugene Salamin -
Warren D Smith