Transcript The Marriage Problem

The Marriage Problem
Finding an Optimal Stopping
Procedure
Examples of Optimal Stopping Procedures
• There are many legitimate real life applications where we
may want to find an optimal stopping procedure…
• Selling a house: Given a series of offers, how many
should you consider before accepting an offer?
• Computer Chess: How many positions should the
computer consider before making a move?
• Finance: How long do you wait to exercise a financial
option between the time of purchase and the expiration
date.
Examples of Optimal Stopping Procedures
• What you are about to see is not really a
legitimate application of an optimal stopping
procedure!
• It’s just simpler to state this problem, it’s kind of
fun in a sort of perverse way, its mathematically
interesting, and it has a simple and surprising
answer.
Statement of the Problem
• You will meet many people in your life and suppose you are looking
for the “best” mate.
• Assume you know you will meet n potential mates and could
actually rank them after you have met them all, on a scale from 1 to
n, where 1 is the best.
• This is an extreme oversimplification –obviously not very realistic –
please do not try this at home –
but it does lead to an interesting mathematical question…
• How do you pick the best one?
Statement of the Problem
• Suppose that you can’t wait to see them
all.
• Suppose that you have to make a decision
at some point, not knowing whether the
ones you see in the future may get a
higher rating than those you have seen so
far.
Example with 3 potential mates
• For example, suppose you will meet 3 potential mates in your life.
• You don’t know what order they will enter your life, suppose any
order is equally likely.
• Further, assume you will meet them one at a time, and if you let
them go, you can not call them back.
• There are 3! = 3*2*1 = 6 different possible permutations:
123
132
213
231
312
321
Suppose your selection rule is to pick the first person you meet.
This rule would work on the first 2 possible permutations, meaning
your probability of success would be 2/6 = 1/3 = 33%
Example with 3 potential mates
And if your rule was simply to pick the second person, you would have
the same probability of selecting the best one, which is 1/3.
Again, your probability of selecting the best person would be 1/3 if you
used the rule “pick the third person you meet”.
How about a new rule to improve your chances?
123
132
213
231
312
321
Consider this rule:
“Let the first one go and pick the first one you see better than the
one you let go.” What are your chances now?
If there are 6 different possible permutations, in which of those 6 possibilities
does this rule lead you to pick the best mate?
It doesn’t work in the first two permutations listed above, but it would work in the
cases 213, 231, and 312.
Why won’t it work in the last case 321?
Example with 3 potential mates
The rule (called a stopping rule in decision theory)
“Let the first one go and pick the first one you see better than the one
you let go”
would lead us to successfully pick the best potential mate in the cases
213, 231, and 312.
123
132
213
231
312
321
However, the rule fails to select the best mate in the first two cases 123 and 132,
obviously, because the best choice was the first one in the list.
The rule also leads you to miss the best mate in the last case because, after
letting the first person go, and then picking the next person better than the one
who had already passed, would lead you to pick the very next person, since
according to the final ranking 321, the second one is better than the first.
Remember, when you see the second person you would not know they will
eventually be ranked as a “2”. For all you know at the time, that second person
could be the best one, since you have not yet seen the last one. After seeing all
three, you could then rank them, in the order you met them, as 3, then 2, then 1.
Example with 3 potential mates
In conclusion, using this rule:
“Let the first one go and pick the first one you see better than the
one you let go.”
it would lead us to successfully pick the best potential mate half
the time, in cases 213, 231, and 312.
And therefore the probability of selecting the best mate using
this rule is 3/6 = 50%.
This rule has a higher probability of leading to the choice of the
best mate compared to a simpler rule such as “pick the second
person” which worked on 33% of the time.
123
132
213
231
312
321
Suppose you will meet 4 potential mates
• Suppose you will meet 4 potential mates and after you have met all 4
you could then rank them 1 to 4 with 1 being the best (and no ties).
• Suppose you meet them one at a time and if you let one go, you can
only wait until you meet the next one, and you can not go back.
• Also, just as before, assume that you can only make a relative
ranking of the ones you have met so far. In other words, as you meet
each one, you can say for sure which is better than which, but you
can not say, out of all 4, which is best and worst, and in between, until
you have seen them all.
Example with 4 potential mates
• With 4 potential mates, there are 4! = 24 possible permutations, as
listed below.
1234
1243
1324
1342
1432
1423
2134
2143
2341
2314
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
Suppose you use the same stopping rule: “Let the first person go
and then select the next person who is better than the one you let
go.”
In which permutations would this rule lead you to select the best
person? What is the probability that this rule would lead to a
selection of the best person?
Example with 4 potential mates
• With 4 potential mates, there are 4! = 24 possible permutations, as
listed below.
1234
1243
1324
1342
1432
1423
2134
2143
2341
2314
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
Now consider a modification to the rule: Let the first two people go
and then select the first person who is better than both of the first two.
In which permutations would this rule lead you to select the best
person? What is the probability that this rule would lead to a selection
of the best person?
The general case
• Now let’s consider the more general situation.
• Suppose you know ahead of time that you will meet n people total
that would be potential mates. Suppose that after you meet them all
you could rank them on a scale from 1 to n, where 1 is best.
• Suppose you meet them one after another and, if you let one go,
you can not go back to that person.
• If all possible permutations of these people are equally likely, what
procedure would improve your chances of selecting the best one in
the list?
• One procedure is to simply pick one person somewhere along the
way. What are your chances of getting the best person using this
method?
The general case
• If you just pick one person from the list, because there are n people
total, the chances that person is the best is 1/n.
• We have seen a decision procedure that improves this probability:
• Just like in the cases for n=3 and n=4, the optimal stopping rule has
the form: Let the first m people pass and then select the next
person better than any of those first m people.
• To calculate the probability of selecting the best person using this
method we need to understand how it can fail.
• There are two ways this method can fail:
– 1. The best person was in the group of the first m people.
– 2. The best person comes after a person who is better than all of those
in the first group of m people.
Deriving the Formula
• However, this method will be successful if, after letting the first m
people go, it is successful in selecting the best person when
considering person “m+1”, or person “m+2” or person “m+3”, all the
way up to person “n”.
• Suppose you let the first m people go and consider person “m+1”
We must ask, what is the probability that person m+1 is best and if that
person were the best, what is the probability this method would pick that
person?
The probability that person m+1 is best is 1/n and this method would surely
pick that person (probability 1) because that person would clearly be
better than any of the previous m people.
Therefore, if person m+1 were best, the probability this method leads to
the selection of that person is 1/n.
Deriving the Formula
•
But the best person may not appear right after the first m people pass. The
best could be person m+1 or m+2 or m+3 or so on, up until the nth person.
•
So we add the probability that the best person is the second person
considered, and is selected, after the first m people are passed over. In
other words, suppose you let the first m people go and consider person
“m+2”
We now ask, what is the probability that person m+2 is best and if that
person were the best, what is the probability this method would pick
that person?
The probability that person m+2 is best is also 1/n and this method will
select that person only if there wasn’t someone better than the first m
that came before person m+2. In other words, the procedure would be
successful if the best of the first m+1 people is in the group of the first
m people. And the probability of that is m/(m+1).
Therefore, the probability that the procedure successfully selects person
m+2 if that were in fact the best person in the list is (1/n)*(m/(m+1)).
A General Pattern
• Notice a pattern that will develop here mathematically…
• Given the rule that the first m are skipped, the probability
that person m + k is best and is selected is
 1  m 
 

 n  m  k 
for k = 0, 1, 2, … (n – m)
because 1/n is the probability that any person is best overall and in order for
this procedure to pick that person, the best of first m+k people had to be
among for the first m people. And the probability of that is m/(m+k).
A Formula for the Probability and an Example
• Therefore, to get the final probability that this method is successful,
we will add the probabilities of each of the mutually exclusive
events that the best was selected with the (m+1)st person or
(m+2)nd or (m+3)rd or … so on, up to the nth person.
• That is, given n people to choose from, the probability of selecting
the best by letting the first m go by and then selecting the next
person better than any in the first group of m people is given by…
P(m) 
 1  m 
 


i  m 1  n  i  1 
n
For example, suppose that you will meet 10 people, what is the probability
that this procedure leads to the selection of the best one if you let the first 3
go by and then select the first one better than all of the first 3?
 1  3   3  10 1  3  1 1 1 1 1 1 1 1 
P(3)    
           .4287
   
 10  i 4 i  1  10  3 4 5 6 7 8 9 10 
i 31 10  i  1 
10
Optimizing the Probability
• An interesting mathematical question to ask is this:
• Does the probability improve if, instead, you let the first 4 people go
by and then select the next person better than any of the first 4?
• Another interesting question is this:
• For any value n, the total number of people met, what is the value m
to first skip over, that will then lead to the highest probability of
selecting the best person in the list?
• Realize that as n grows larger, if we simply picked any person
randomly in the list, the probability of selecting the best person
would approach zero.
• Can we do better than just randomly guessing? What is the optimal
stopping procedure? Is there a general answer?
Optimizing the Probability
• To find an optimal value for m, we consider the formula for the
probability of selecting the best person after letting the first m people
pass,
 1  m 
P(m)    

i  m 1  n  i  1 
n
=
 m  n 1  1 
   
 n  i m  i 
1
1
1
1 
 m  1
   




n  2 n 1 
 n  m m  1 m  2
n 1
n 1
n 1
n 1
 m  n 1
    
 
 
 
 
n  2 n n 1 n 
 n  m n m  1 n m  2 n
Optimizing the Probability
To find this sum, in the case that n is very large, let x = m/n, we have,
n 1
n 1
n 1
n 1
 m  n 1
 
 
 
 
   
n  2 n n 1 n 
 n  m n m  1 n m  2 n
 1  1
n 1
 


 x 
1
 . Now, assuming n  , then

i
n
n
i m
n


 1 
1
 is theevaluation
and considering f (t )  , then thefactor
 i 
t
 n 
1
of f (t ) at theleft - endpointsof subintervals of width in a Riemann
n
sum.
n 1
 
 
Optimizing the Probability
T herefore,subst it ut ing, we have...
1
 1  1
n 1
1
 


x
   x   f (ti )t  x   dt   x ln x

i n
t
im
i m
x
 n 
n 1
 
Now we can find the value of x that will maximize this probability because we
have the probability as a function of x.
The only critical point of –xlnx occurs when its derivative f’(x) = –lnx-1 is equal
to 0 which occurs when x = 1/e.
The second derivative of –xlnx is -2 and, because it’s negative, we know the
critical point x=1/e is a maximum of the function.
Therefore the maximum probability occurs when x = 1/e.
Conclusion
• The maximum probability occurs when x = 1/e
m
1 n
and because x 
thenm  nx  n   .
n
e e
• The conclusion is that as n increases, the optimal value of m is n/e.
• In other words, no matter how many people you will meet, the optimal strategy
is to let the fraction 1/e pass and select the first one better than any of those in
that first group.
• The fraction 1/e is approximately .368 meaning that the optimal strategy is to
let the first 36.8% pass without selecting one and then select the first one better
than all of those in that first group of 36.8%.
Conclusion
• Finally, notice that because –xlnx gives an approximation to the
probability that the procedure will actually work in selecting the best
person from the whole group of n people and we know that probability
will be largest when x = 1/e, by plugging 1/e into this function we get
the result of 1/e.
• This means that as n gets larger and larger, the probability of
selecting the best person by using this procedure will approach 1/e or
36.8%.
• In other words, by guessing randomly, the probability of selecting the
best person would approach zero as n grew larger, however, by using
this optimal stopping procedure, the probability of selecting the best
person will approach approximately 36.8%.